O primeiro exemplo de um grafo aleatório é o modelo GN,p3ou modelo de Gilbert
que definimos como segue. Dado um número N de nós rotulados, digamos i= 1, 2, 3, ..., N, temos que cada par de nós está presente com probabilidade p e ausente com probabilidade 1−p. Como exemplo, consideremos um grafo com N = 3. Neste caso, existem oito configu- rações possíveis com a probabilidade de realização mostrada na figura 2.8. Este modelo,
3A notação G
N,pindica que este é um ensemble estatistico de redes, G, com dois parâmetros fixos: Um dado número de nós em cada membro do ensemble e uma dada probabilidade p que dois nós têm de se ligarem.
GN,p, foi introduzido pelos matemáticos Ray J. Solomonoff e Anatol Rapaport quando
publicaram uma série de artigos no ”Bulletin of Mathematical Biophysics“ entre 1951 e 1952 [44, 45]. Na época, esses artigos não atrairam a atenção de estudiosos do assunto, permanecendo esquecido por algum tempo, sendo redescobertos pelo matemático E. N. Gilbert apenas em 1959 [46]. (a) (1 − p)3 (b) p(1 − p)2 (c) p2 (1 − p) (d) p(1 − p)2 (e) p2 (1 − p) (f) p(1 − p)2 (g) p2 (1 − p) (h) p3
Figura 2.8: Modelo de Gilbert de um grafo aleatório para N = 3 com todas as configurações possíveis representadas. Para um grafo que contenha N nós e L ligações, podemos expressar a probabilidade de ligação entre os pares por pL(1 − p)M−L, onde M = N(N − 1)/2 é o número máximo de ligações. As figuras (b),(d) e (f), e (c), (e) e (g) são isomórfas, isto é, uma configuração pode ser transformada em outra re-rotulando seus nós.
Na final dos anos 50, como mencionado na seção 2.1 , Paul Erdös e Alfréd Rényi introduziram um outro modelo de grafos aleatórios. O grafo aleatório de Erdös-Rényi é um ensemble estatístico cujos membros são todos os grafos possíveis rotulados de um dado número N de nós e L ligações escolhidas ao acaso entre as N(N − 1)/2 conexões possíveis. Ou seja, existem um total de CL
N(N−1)/2 grafos possíveis, formando um espaço
de probabilidades onde cada grafo possui o mesmo peso estatístico. Este grafo aleatório também é conhecido como modelo GN,Lque significa que temos um ensemble estatístico,
G, de grafos com dois parâmetros fixos para cada membro do ensemble, ou seja, um dado número N de nós e um dado número L de ligações. Este é um caso especial de uma cons- trução geral extensivamente explorada em ciência de redes. A ideia consiste na construção de um ensemble cujos membros são todos os grafos possíveis satisfazendo algumas restri- ções estabelecidas, onde todos os membros são realizados com probabilidades iguais. A figura 2.9, mostra um exemplo de grafo de Erdös-Rényi de 3 nós e 1 ligação. Comparando este ensemble com o G3,p, mostrado na figura 2.8, é possível ver que esses dois ensembles
são diferentes. Entretanto, esta diferença é desprezível para redes esparsas4grandes.
Muitas vezes, como é conhecido da comunidade de físicos, analisar o ensemble grande canônico é tecnicamente mais fácil que analisar o canônico. Partindo desse prin- cípio, o modelo de Gilbert leva vantagem. Assim, o estudo de grafos aleatórios é mais simples a partir desse modelo, permitindo a determinação de muitas das propriedades dessas redes como a conectividade, a presença de circuitos, o diametro da rede, entre ou- tros.
Figura 2.9: Grafo aleatório de Erdös-Rényi de 3 nós e 1 ligação, ou seja, GN=3,L=1. Todas os seis grafos têm o mesmo peso estatístico.
a) Distribuição de conectividade em um grafo aleatório clássico
Em um grafo aleatório, constituído de N nós, um nó particular pode se ligar aos outros N− 1 nós presentes na rede com probabilidade p. Assim, esta combinação resulta imediatamente na forma binomial da probabilidade que k destas N− 1 ligações estejam presentes, ou seja,
P(k) = Ck
N−1pk(1 − p)N−1−k. (2.4)
P(k), neste caso, é a distribuição de um grafo finito. Aqui o primeiro termo do lado direito da equação, Ck
N−1, informa o número de maneiras diferentes em que as ligações
podem estar distribuídas. O segundo termo, pk, representa a probabilidade de existência
de k ligações e, por último, o termo(1 − p)N−1−k expressa a ausência das N− 1 − k ligações.
4Uma rede esparsa é aquela que possui o número de ligações muito menor que o número de nós em um
grafo completo: LȂ N2
No limite quando a rede é muito grande (N→ ∞) e ܂k܂ finito (p → const/N), a distribuição binomial (2.4) tende para a distribuição de Poisson, ou seja,
P(k) = e−܂k܂܂k܂k1
k!, (2.5)
com a conectividade média܂k܂ = p(N − 1). Neste limite, os modelos de Gilbert e Erdös- Rényi são equivalentes e, então, a distribuição de Poisson é válida para todos os grafos aleatórios clássicos [8]. É importante mencionar que esta distribuição decresce muito ra- pidamente para valores distantes da conectividade média, sendo o responsável por este decaimento, o denominador fatorial. As redes geradas a partir deste modelo são, razoa- velmente, homogêneas e apresentam escala característica governada, aproximadamente, pela conectividade média܂k܂, como mostra a figura 2.10.
Figura 2.10: Distribuição de conectividade do modelo de Erdös-Rényi para N = 104, p
= 0.0006 (círculo), p= 0.001 (quadrado) e p = 0.0015 (diamante). Figura retirada da referência [48].
b) Menor caminho em um grafo aleatório clássico
Em grafos aleatórios, o caminho entre dois nós escolhidos arbitrariamente, tende a ser pequeno. A razão disso, é que um grafo aleatório é igualmente distribuído com uma probabilidade definida previamente. Como exemplo, consideremos uma rede ale- atória onde cada nó possui um número característico ܂k܂ de ligações (ou número médio
de vizinhos). Em uma rede desse tipo, partindo de um nó qualquer i, podemos alcançar ܂k܂ outros nós afastados a uma distância de um passo. De cada um desses nós, podemos alcançar܂k܂ outros nós e, assim por diante, de modo que após um número l de passos po- demos alcançar܂k܂lnós. Em outras palavras, temos que os܂k܂lnós estão a uma distância
ldo nó i. Se a rede for constituída por N nós,܂k܂lnão pode exceder o tamanho N, ou seja,
N Ȃ ܂k܂l. Assim, para alcançar os N nós da rede são necessários, em média,
lrand Ȃ
ln(N)
ln(܂k܂) (2.6)
passos. Este resultado, mostra que, a partir de um dado nó, é possível chegar a outro em poucos passos. Dito de outra forma, temos que a distância média entre dois nós quais- quer é, consideravelmente, pequena mesmo para redes muito grandes. Este resultado também serviu de base para explicar o problema dos seis graus de separação estudado por Milgram em 1967 [24].
A figura 2.11, compara os menores caminhos médios obtidos para algumas redes reais com a previsão teórica proposta pela equação (2.6) para gráfos aleatórias, apresen- tando boa concordância entre o resultado teórico e aqueles obtidos empiricamente.
Figura 2.11: Comparação entre os menores caminhos médios de redes reais (símbolos) e gráfos aleatórias. A linha tracejada representa a previsão da equação (2.6). Figura retirada da referência [10].
c) Circuitos em um grafo aleatório clássico
Circuitos são frequentes em grafos aleatórios clássicos. Mas, o que isto significa? Em grafos dessa natureza, não é difícil determinar o coeficiente de agregação e, conse- quentemente, o número total de circuitos de ordem três presente na rede. Consideremos, por exemplo, um grafo constituído de N nós com uma conectividade média dada por ܂k܂. Lembremos que o coeficiente de agregação de um nó é a probabilidade de dois vizi- nhos próximos, deste nó, estarem conectados entre si. Em nosso caso, esta probabilidade é܂k܂/(N − 1) ≅ ܂k܂/N para N grande. Com isso, temos que o coeficiente de agregação é dado por
C= ܂k܂
N , (2.7)
sendo independente da conectividade do nó.
O número de circuitos de ordem três presentes em um gráfo aleatório clássico, pode ser determinado em função da equação (2.7), ou seja,
n3= 1 3[ 1 2N(܂k 2 ܂ − ܂k܂)]C = ܂k6܂3. (2.8)
O termo N(܂k2܂ − ܂k܂)/2, representa o número total de ordem 3. Generalizando, podemos
determinar o número de circuitos de um comprimento arbitrário L através da seguinte expressão: nL ≅ ܂k܂L/(2L). Esse número independe da ordem, desde que L seja menor
que o diâmetro da rede (da ordem de ln(N)).
Para um melhor entendimento, comparemos o coeficiente de uma rede real com aquele predito pela equação (2.7). Por exemplo, até 2009, o mapa dos roteadores da In- ternet continha cerca de mais da metade de um milhão de nós (roteadores). O número médio de conexões é da ordem de 10 e o coeficiente de agregação da ordem de 10−1. Para
um gráfo aleatório clássico do mesmo tamanho e com a mesma conectividade média, o coeficiente de agregação é da ordem de 10−5 que é cerca de quatro ordens de grandeza
menor que a Internet [8]. Através da figura 2.12, é possível ver que os valores dos coefi- cientes de agregação das redes reais e aleatórios são distintos. E que os gráfos aleatórias possuem coeficiente muito pequeno quando se considera o mesmo número de nós para ambas as redes. Ainda é possível observar que a razão C/܂k܂ não decai com 1/N. Em vez disso, parece independer do tamanho de N.
Figura 2.12: Comparação entre os coeficientes de agregação de redes reais e gráfos aleatórios. A linha tracejada representa a previsão da equação (2.7). Figura retirada da referência [10].