Distribuição do grau em redes GWS

Nos artigos anteriores, nós vimos como o modelo WS, e sua generalização GWS, geram redes complexas com alto coeficiente de aglomeração e distâncias curtas, tal como encontramos em redes reais. Portanto, uma pergunta natural é: e quanto à distribuição do grau? temos uma rede livre de escala? Neste último artigo da série sobre redes Small World, investigaremos estas questões.

Em primeiro lugar, deve-se observar que a distribuição do grau no modelo GWS depende fortemente do valor da probabilidade de redirecionamento. Quando $p=0$, a distribuição é centrada em um único valor $k$, já que temos uma rede k-regular e todos os nós tem o mesmo grau. Mas, quando $p \to 1$, a distribuição se assemelha a uma distribuição binomial com parâmetros $m$ e $\frac{2}{n}$, como ocorre em grafos aleatórios G(n,m). Assim, conforme $p$ aumenta, a tendência é que a distribuição do grau vá ficando mais achatada e espalhada. O grau médio, contudo, não depende de $p$, pois é sempre $\lambda=k$.

A Figura a seguir mostra a distribuição do grau em redes GWS com $n=1000$, $k=16$ e diferentes valores da probabilidade de redirecionamento. Primeiramente pode-se notar que quando nenhum dos enlaces é redirecionado ($p=0$) a rede é k-regular e todos os nós possuem grau igual a 16. Com o aumento do valor da probabilidade de redirecionamento, há uma diminuição do número de nós com grau igual à média, pois os redirecionamentos tendem a desequilibrar o grau dos nós ao remover os enlaces que se ligam a alguns nós e religá-los a outros nós.

Outro aspecto que a Figura acima mostra é que, quanto mais enlaces são redirecionados mais a distribuição do grau se assemelha a uma distribuição Binomial. Assim temos que o grau médio é sempre $k$ pois, se $P_{GWS}(d_i=k) \sim Binomial(n,\frac{2}{m})$, então temos que $\lambda = \frac{2m}{n}=k$.

Para demonstrar melhor esta aproximação da distribuição do grau com a distribuição Binomial, mostramos na figura abaixo gráficos quantil-quantil da distribuição do grau de redes GWS geradas com $n=1000$, $k=16$ e com diferentes probabilidades de redirecionamento. A linha tracejada no gráfico indica a aderência perfeita à distribuição Binomial.

Podemos notar que, conforme a probabilidade de redirecionamento se aproxima de 1, a distribuição do grau na rede GWS tende a se aproximar da distribuição binomial. Com $p=0,5$, por exemplo, a distribuição do grau das redes GWS já se encontra bem próxima da Binomial, tendo apenas uma leve divergência nas caudas da distribuição. Quando $p=1$ temos uma aderência perfeita, o que é esperado, já que o processo de criação da GWS reconfigurará todos os  enlaces da rede, o que equivale a criar uma rede G(n,m) com $m=\frac{kn}{2}$ enlaces e o mesmo número de nós.

Destes resultados, podemos perceber que as redes GWS são um híbrido, parte k-regular e parte aleatória. Assim, a sua topologia é um misto entre estes dois tipos de redes, conforme aponta a distribuição do grau. Para valores baixos de $p$ (que é a região de interesse mais comum nestes modelos) a distribuição do grau tem uma maior densidade em torno da média do que teria uma rede aleatória e por isso não podemos dizer que segue uma distribuição Binomial. Para uma expressão fechada da distribuição do grau em uma rede GWS verificar o trabalho On the properties of small-world network models de Barrat e Weigt, publicado em 2000.

A despeito da distribuição que escolhamos, certo é que a distribuição do grau em redes GWS não segue uma lei de potência, já que o grau dos nós se distribuem em torno de uma média e não ficam muito distante delas. Isso acontece por causa da natureza híbrida de que falamos: ou a rede tende a uma rede regular ou se assemelha a uma rede aleatória, e nenhuma destas redes são livres de escala. Este resultado parece indicar que a regularidade e aleatoriedade, presentes nas redes GWS, não são suficientes para que as redes geradas sejam livres de escala. Para isso precisaremos de outros componentes que veremos em outros modelos de redes.