Small Worlds: distâncias e aglomeração

Conformo vimos anteriormente, o coeficiente de aglomeração e o tamanho médio do caminho em redes WS tem um comportamento peculiar com o aumento de $p$. Neste artigo, veremos que este efeito é similar para redes GWS.

O tamanho médio do caminho na rede GWS se comporta de forma semelhante ao que ocorre nas redes WS padrão, isto é, o tamanho médio do caminho decresce exponencialmente com a probabilidade de redirecionamento $p$, conforme mostra o gráfico abaixo. Nesta figura temos o tamanho médio dos caminhos padronizado pelo valor do tamanho médio dos caminhos na rede GWS com $p=0$. O gráfico compara os resultados para redes GWS com $n=500$ e $k=4$ (círculos pretos) e para $k=10$ (cruzes vermelhas).

Além do decrescimento exponencial, outro aspecto a ser notado na figura acima é que o aumento de $k$ leva a uma diminuição do tamanho médio dos caminhos. Na realidade, este é um resultado conhecido das redes k-regulares, já que o aumento do número de arestas reduz os caminhos na rede. Também se observa no gráfico os seguintes resultados:

1. Quando $p \to 0$ o tamanho médio dos caminhos ($TMC$) pode ser estimado por $TMC = \frac{n}{2k}$, pois se trata de uma rede aproximadamente k-regular;
2. Com um pequeno aumento do valor de $p$, o tamanho médio dos caminhos diminui devido ao efeito da reconfiguração aleatória dos enlaces;
3. Conforme $p$ cresce o tamanho médio do caminho praticamente se estabiliza. Neste ponto a rede se torna praticamente aleatória e $TMC \sim \frac{\log(n)}{\log(\lambda)}$, conforme vimos para uma rede aleatória.

Já olhando para o $CC$, veremos que em redes GWS, assim como ocorre no modelo WS, a adição de aleatoriedade (aumento de $p$), leva a uma diminuição do coeficiente de aglomeração. O valor máximo do $CC$ em uma rede GWS ocorre quando $p=0$. Neste caso, temos que o coeficiente de aglomeração será o mesmo da rede k-regular, assim $CC(p=0)=CC(0)=\frac{3t-3}{4t-2}$, onde $t=\frac{k}{2}$. Para $k=4$ temos que $CC(0)=0,5$ e para $k \gg 2$ temos que $CC(0) \simeq \frac{3k}{4k}= \frac{3}{4}$. Assim, o CC na rede GWS com $p=0$ estará no intervalo [0,5;0,75].

A figura abaixo mostra o comportamento do coeficiente de aglomeração de redes GWS geradas com $n=100$ e $k=8$ com diferentes probabilidades de redirecionamento. Um modelo que aproxima o comportamento do coeficiente de aglomeração em redes GWS para $p$ pequeno é $CC(p) \simeq CC(0)(1-p)^3$, que é mostrado no gráfico por meio da linha tracejada. 

Esta aproximação aparece primeiramente no artigo On the properties of small-world network models de Barrat e Weigt publicado no periódico The European Physical Journal B - Condensed Matter and Complex Systems em Fevereiro de 2000. Ela tem a vantagem de permitir uma análise mais simples do coeficiente de aglomeração, o que não ocorria em propostas anteriores (veja o livro de Ted Lewis para esta discussão). 

Contudo, pode-se observar que, para probabilidades de redirecionamento maiores do que 0.1% o modelo proposto sofre um leve desvio superestimando o valor do coeficiente de aglomeração. Para valores altos de $p$ ($p>0,5$) o modelo proposto desvia completamente dos valores simulados, sendo fortemente contra-indicado para estes casos. O erro médio absoluto deste modelo é aproximadamente 4%.

Estas análises mostram que o modelo GWS permite gerar redes fictícias bem próximas das redes reais, dado que consegue aliar o efeito small world (fenômeno que diz que redes complexas reais possuem caminhos pequenos) com a alta aglomeração na rede (fenômeno de que há uma alta probabilidade de amigos estarem ligados entre si em uma rede complexa).

Ele também ajuda a explicar que a alta aglomeração das redes reais não é propriedade derivada do efeito small world. Pode-se perceber claramente que este efeito tem causa no processo aleatório de redirecionamento dos enlaces, enquanto que a aglomeração é característica da regularidade existente na rede inicial.

O resultado acima fica mais claro, se compararmos os coeficientes de aglomeração em redes aleatórias e redes GWS, conforme pode ser visto na tabela abaixo. A tabela compara o coeficiente de aglomeração de redes GWS e G(n,m) com diferentes parâmetros de $n$ e $k$. O valor de $m$ para a rede G(n,m) equivalente, em cada caso, é calculado por $\frac{kn}{2}$ e em todos os casos a rede GWS tem $p=0,04$. 

$n$	$k$	$CC_{GWS}$	$CC_{G(n,m)}$
100	2	0,003	0,020
100	4	0,380	0,040
100	8	0,510	0,080
100	16	0,560	0,160
100	32	0,600	0,320
200	2	0,001	0,010
200	4	0,380	0,020
200	8	0,500	0,040
200	16	0,550	0,080
200	32	0,580	0,160

Note que, em todos os casos, o coeficiente de aglomeração das redes GWS é muitas vezes maior do que o coeficiente de aglomeração das redes G(n,m) de mesma densidade, ou seja, a alta aglomeração é efeito da rede k-regular subjacente e não da aleatoriedade.

Para deixar isto ainda mais claro, considere a GWS com $k=2$. Neste caso a rede é um anel simples onde cada nó possui apenas dois enlaces para seus vizinhos imediatos, por isso a rede 2-regular inicial tem coeficiente de aglomeração zero, e a introdução da aleatoriedade faz com que este valor aumente apenas um pouco. O que faz com que até mesmo as redes G(n,m) tenham coeficiente de aglomeração maior. 

Assim, combinando regularidade e aleatoriedade, o modelo GWS ajuda a explicar alguns dos fenômenos que vimos em redes reais. Contudo, será que as redes GWS são livres de escala? Será que nelas encontramos o fenômeno de que poucos nós concentram um grande volume de vizinhos (em outras palavras, possuem grau muito alto) e a maioria dos nós possuem um pequeno baixo volume de vizinhos? Isto responderemos em nosso próximo artigo.