Modelo Small-World

Como visto em artigos anteriores, as redes aleatórias possuem a interessante propriedade de que os caminhos nestas redes tendem a ser menores do que em redes regulares, o que coincide com o que vimos em redes complexas na realidade. Contudo, as redes aleatórias não são suficientes para modelar outros aspectos presentes nas redes reais como a distribuição do grau ou o coeficiente de aglomeração.

O modelo de Watts-Strogatz (WS), também conhecido como modelo Small-World, foi introduzido no artigo Collective dynamics of ‘small-world’ networks publicado na revista Nature em 1998. Este modelo avança na compreensão das redes complexas, já que oferece um algoritmo que consegue explicar melhor o coeficiente de aglomeração. Assim, diferentemente do modelo aleatório, o modelo WS procura combinar regularidade com aleatoriedade, de modo a aproveitar as características básicas da rede regular com o efeito característico da aleatoriedade: a redução do tamanho dos caminhos na rede.

Neste modelo para geração de redes fictícias, começamos criando uma rede 4-regular. Que é criada dispondo os nós em um círculo e ligando cada nó a 2 sucessores no círculo. A figura abaixo exemplifica o processo de criação de uma rede 4-regular com 6 nós. 

Iniciando a partir de um dos nós, que denominamos primeiro, criamos dois enlaces ligando este nó a dois nós sucessivos. Repetimos isso para cada um dos nós. Para os últimos nós do círculo, os sucessores são os primeiros nós. Assim, temos que na rede 4-regular, cada nó tem 4 vizinhos. Esse modelo pode ser generalizado para um número $k$ de vizinhos, que é chamado k-regular.

Voltando ao modelo WS, temos que a partir da rede 4-regular inicial, iremos redirecionar os enlaces criados a partir de uma probabilidade de redirecionamento $p$. Cada enlace será testado apenas uma vez, e poderá ser mudado com probabilidade $p$. O processo é semelhante ao das redes G(n,p), contudo no modelo WS os enlaces não são adicionados, mas somente redirecionados. As figuras abaixo são duas redes WS com 10 nós e $k=4$. Na primeira, usamos $p=0$ (rede original) e na segunda temos $p=0,1$. Note que a segunda poderia ser diferente, já que o processo é aleatório.

O aumento de $p$ implica em um aumento do número de enlaces redirecionados, o que torna a rede mais próxima de uma rede aleatória e proporciona uma diminuição do tamanho médio do caminho. Por outro lado, quanto menor for o valor de $p$, mais regular será a rede. Assim, $p$ é usado para determinar o quão regular ou quão aleatória é a rede WS gerada. 

As figuras abaixo ilustram essa ideia. Quando $p=0$ temos que a rede 4-regular inicial não muda e sabemos que o seu Coeficiente de Aglomeração ($CC$) é 0.5, ou seja, cada nó vizinho se conecta em média com metade dos outros vizinhos. Conforme aumentamos o valor de $p$, o valor de $CC$ e o tamanho médio do caminho tendem a diminuir. Porém, ambas as medidas decrescem de forma não-linear. 

O fenômeno da não-linearidade do decrescimento do coeficiente de aglomeração e do tamanho médio do caminho em redes WS pode ser melhor visualizado na figura a seguir, que mostra os valores do $CC$ e do tamanho médio do caminho computados para redes WS de 1000 nós geradas com diferentes probabilidades de redirecionamento, a qual varia entre  0,01% e 100%. 

Deve-se observar que os valores de tamanho médio do caminho (average path length, com círculos pretos) e $CC$ (cruzes vermelhas) na figura foram padronizados dividindo-se o valor obtido na rede gerada pelo valor correspondente na rede 4-regular inicial. A apresentação dos dados neste formato facilita a compreensão das propriedades da rede WS já que é possível apresentar os valores das duas métricas em uma mesma escala no intervalo entre 0 e 1. Desta forma, na rede WS com $p=1\%$, por exemplo, o tamanho médio do caminho reduziu para 15% do valor da rede 4-regular enquanto o $CC$ sofreu uma pequena queda, ficando em 93% do valor da rede 4-regular.

Um primeiro dado a ser notado é a variabilidade do tamanho médio do caminho para valores de $p$ baixos. Para entender este resultado, deve-se ter em mente que o redirecionamento de um enlace em uma rede 4-regular levará ao encurtamento das distâncias na rede, porém os nós escolhidos para a recriação do enlace podem tanto estar distantes quanto próximos. Caso estejam próximos, a redução do tamanho médio do caminho será pequena, já quando os nós estão mais distantes a redução será maior. 

Como um valor baixo para a probabilidade de redirecionamento $p$ implica na mudança de poucos enlaces, a redução no tamanho médio do caminho pode não ser tão significativa caso o processo de escolha aleatório selecione apenas nós próximos. Este efeito da variabilidade pode ser amenizado pela tomada da média de diversas execuções para cada valor de probabilidade de redirecionamento. 

Em todo caso, mesmo com a presença da variabilidade, é possível perceber que há uma forte tendência decrescente nos valores do tamanho médio do caminho. Isto nos leva a principal observação neste gráfico: um pequeno aumento de $p$ leva a uma drástica redução do tamanho médio do caminho, enquanto que o coeficiente de aglomeração permanece o mesmo, praticamente. Isto quer dizer que a adição de uma pequena aleatoriedade na rede regular encurta as distâncias na rede sem afetar muito a regularidade da rede inicial. Tal resultado já havia sido observado por Watts-Strogatz em seu trabalho seminal e constitui um dos principais resultados no campos das redes complexas.