Grafo aleatório e Small World

Prévia do material em texto

O modelo de grafos aleatórios surge com Paul Erdos e Alfréd 
Rényi, a partir de seus estudos sobre grafos para tentar construir um 
modelo de uma rede. Desses estudos, criam-se os modelos para 
geração de grafos aleatórios, que consiste em, a partir de um número N 
de vértices conectar arestas em pares deles de forma única e aleatória. 
Conforme o processo for se repetindo, mais subgrafos vão se formando 
até o ponto em que será possível ter um caminho onde se poderá passar 
por todos os vértices, assim formando um único grafo conexo. 
 
 
 
 
 
 
 
Exemplos dados em aula 
 
 A partir da formação das conexões, sabe-se que o número de 
arestas é maior ou igual ao mínimo suficiente para formação de um grafo 
e menor ou igual o máximo, ou seja, n-1 <= arestas >= n * (n-1)/2. Além 
disso, é possível ver um único grafo se formando quando o grau médio 
dos vértices é maior que um. 
Da definição e geração de grafos aleatórios, entende-se a 
importância deles para estudos sobre redes do mundo real, onde pode-
se rastrear os vértices, entender como funcionam, como criam as 
conexões entre novos vértices, por exemplo: Transmissão de doenças, 
redes biológicas do corpo, redes sociais entre pessoas, disseminação de 
Fake News, entre outros. Fato é que todos esses tipos de redes citados e 
uma vastidão de várias outras, têm um comportamento imprevisível, 
fazendo com que sejam aleatórias. 
Redes mundo pequeno ou “small world” é um conceito de rede que 
foi se desenvolvendo pelo tempo, onde foram realizados diversos 
experimentos e visto, como resultado, que através de poucas pessoas, 
ou conexões, consegue-se chegar a praticamente qualquer outra pessoa, 
ou vértice. Como o experimento realizado nos Estados Unidos em que 
algumas pessoas foram selecionadas e deveriam mandar uma carta para 
uma outra pessoa não conhecida, e a carta deveria ser enviada através 
de conhecidos. Desse experimento viram uma média de 5,5 pessoas 
para a carta encontrar seu destino, e então se criou o conceito dos seis 
graus de separação que consiste em que todas pessoas do mundo estão 
separadas por seis graus, ou seja, seis pessoas. Outro experimento 
citado, foi uma pesquisa para em que se desejava saber como os 
entrevistados conseguiram seus empregos. O resultado é que grande 
maioria respondeu que conseguiu através de conhecidos ao invés de 
amigos. 
Do último experimento, surge-se a ideia de laços fortes e laços 
fracos. Esse conceito diz que os laços fortes tendem a ser mais fechado, 
reduzindo assim as oportunidades de contatos. Já os laços fracos, 
tendem a ser maiores e com mais oportunidades, criando redes maiores. 
Esse conceito é basicamente o principal da rede mundo pequeno, pois 
ele tende a ter conexões próximas entre os vértices e algumas mais 
afastadas, fazendo com que o grafo ou a rede tenha alguns caminhos 
mais “aleatórios”, aumentando a conectividade de alguns vértices dos 
grafos, como se fossem corta caminhos. 
 
 
 
 
 
 
 
 
Exemplo dado em aula 
 
 Outro conceito muito importante para os estudos de redes mundo 
pequeno, são os coeficientes de clusterização. Antes de explicar para 
que serve o coeficiente, temos a definição do conceito de clique, que é 
quando em um subconjunto do grafo, cada um dos vértices desse 
subconjunto está conectado com os outros, como na imagem abaixo: 
 
 
 
 
 
 
 
 
 
 
O coeficiente de clusterização calcula quanto um vértice está 
próximo de participar de um clique. Sendo que o coeficiente vai de 0 a 1, 
onde zero são pequenas chances e um, maiores. 
Fórmula do coeficiente 
 
A importância do coeficiente para analisar redes de mundo 
pequeno se dá ao ver que quantos mais vértices com cliques ou 
próximos de um, a rede tende ter caminhos mais curtos, ou seja, mais 
conexões. 
 
 
 
 
 
 
 
 
 
João Gabriel Fonseca Ahn 
11202021755