Generalizando as redes Small-World

No último artigo estudamos outro modelo para geração de rede fictícias que chamamos de modelo WS e vimos que este modelo captura o efeito de mundo pequeno (distâncias curtas, em média) mantendo, ao mesmo tempo, um alto índice de aglomeração.

Uma limitação do modelo WS é que não é possível gerar redes com densidade arbitrária, já que a densidade é diretamente relacionada à rede 4-regular inicial, sendo dada por

$densidade_{4-regular}=\frac{2m}{n(n-1)}=\frac{2\frac{kn}{2}}{n(n-1)}=\frac{4}{n-1}$.

Assim, a quantidade de enlaces na rede depende exclusivamente do tamanho da rede WS e a densidade tende a diminuir com o aumento do tamanho. Tal fato torna difícil gerar redes WS de densidade comparável a uma rede real. Para obter uma densidade controlada utilizaremos uma rede k-regular criando assim uma generalização destas redes que chamaremos de Generalized Watts-Strogatz (GWS).

No caso de uma rede k-regular, temos que $k=\frac{2m}{n}$, assim basta escolher os valores de $m$ e $n$ (número de enlaces e de nós, respectivamente) que levam à densidade desejada e calcular k. A única observação é que $k$ é um número natural, logo valores reais de k devem ser sempre arredondados ou truncados para o inteiro mais próximo. 

Excetuando a rede inicial, o processo de criação de uma rede no modelo GWS segue exatamente o mesmo do processo da rede WS: dada uma probabilidade $p$, o modelo testará cada aresta da rede inicial para determinar se ela deve ser redirecionada.

A figura abaixo compara redes WS (GWS com $k=4$) com diferentes valores de $p$ com redes GWS com $k=20$ e os mesmos valores de $p$. Além de permitir visualizar as redes, o gráfico também mostra o efeito do aumento da densidade no $CC$ e no tamanho médio do caminho (TMC) em ambas as redes. Pode-se então observar dois resultados: 1) Como já sabido, mais enlaces em uma rede k-regular implicam necessariamente em menor tamanho médio do caminho e maior coeficiente de aglomeração; 2) Assim como ocorre nas redes WS, a introdução de aleatoriedade na rede GWS leva a uma diminuição do CC e do tamanho médio do caminho, sendo esta a regra geral.

A vantagem de um modelo de densidade controlável é que ele permite a comparação de redes semelhantes ainda que tenham sido geradas por modelos diferentes. Assim, podemos, por exemplo, comparar as propriedades de uma rede gerada pelo modelo G(n,m) com o número de nós $n$ e o número de enlaces $m$ a uma rede gerada pelo modelo GWS com o número de nós $n$ e com $k=\frac{2m}{n}$. Note que $k$ pode não ter um valor inteiro (a depender dos valores de $n$ e $m$) o que obriga a arredondar seu valor para o inteiro mais próximo e resulta em redes de densidade diferentes. Esta diferença é bastante acentuada em redes pequenas (10 ou 20 nós), contudo, a diferença de densidade será praticamente nula em redes grandes (1000 ou mais nós) como as que temos interesse. Tal fato torna o modelo de redes GWS indicado para comparações.

A figura a seguir compara redes G(n,m) com redes GWS equivalentes. As rede G(n,m) estão na primeira coluna. A rede G(n,m) do canto superior esquerdo possui 100 nós e 300 enlaces. Para esta rede, a rede GWS equivalente possuirá $k=6$, já para a rede G(n,m) que possui 100 nós e 1000 enlaces, no canto inferior esquerdo, as redes GWS equivalentes possuem $k=20$. Note que o valor de $p$ não modifica a densidade, por isso temos duas redes GWS para cada uma das redes G(n,m) com valores de  $p=0,05$ e $p=0,1$.

A figura acima mostra também os valores  de $CC$ e $TMC$ de cada uma das redes geradas. Destes resultados pode-se perceber que conforme $p$ aumenta os valores de ambas as métricas na rede GWS tendem a se aproximar dos valores da rede G(n,m). Comparando o tamanho médio do caminho da rede G(n,m) com $m=1000$ às redes GWS equivalentes, por exemplo, pode-se perceber que os tamanhos médios do caminho são bem próximos.

Partindo então do que apresentamos aqui, estudaremos nos próximos artigos algumas outras propriedades das redes geradas pelo modelo GWS.