Redes complexas: Da internet às redes sociais

Modelo de Watts e Strogatz e o efeito de vizinhança

Apesar de ser fácil trabalhar matematicamente os grafos aleatórios, este modelo é totalmente irrealista em muitos casos, devido à completa ausência de estrutura local. Pensando, por exemplo, nas redes sociais, salta à vista que a probabilidade de quaisquer dois dos meus amigos se conhecerem é bastante superior à probabilidade de duas pessoas escolhidas ao acaso se conhecerem. Na terminologia dos grafos, esta propriedade mede-se a partir do coeficiente de aglomeração C, que é a probabilidade de dois primeiros vizinhos do mesmo nodo estarem conectados entre si. Num grafo aleatório os valores de C e p são iguais, pois não há ligações privilegiadas. No entanto, para muitas redes reais, C é muito maior que p, o que mostra um importante 'efeito de vizinhança'. A tabela seguinte mostra os valores do número total de nodos N, do valor médio L da distância entre dois nodos medida em número de ligações ou graus de separação e do coeficiente de aglomeração C de várias redes reais. A coluna C_rand mostra o valor do coeficiente de aglomeração para uma rede aleatória com os mesmos valores de N e de L.

Como se pode ver, as redes consideradas nestes estudos têm um coeficiente de aglomeração muito superior ao das redes aleatórias, mas têm também, como estas, valores baixos de L. Para modelar muitas das redes reais precisamos então de um modelo mais sofisticado do que o dos grafos aleatórios, que reproduza o efeito de small world sem sacrificar o efeito de vizinhança.

Watts e Strogatz propuseram em 1998 um modelo extraordinariamente simples que apresenta estas características complementares. A ideia em que o modelo se baseia é também muito simples. Por um lado, redes aleatórias estão associadas a valores baixos de L e a valores baixos de C. Por outro, a maioria das redes regulares, em que todas as ligações são locais, correspondem a valores elevados tanto de L como de C. No exemplo da figura temos uma rede regular construída sobre um anel, em que cada um dos quinze nodos está ligado aos seus dois primeiros vizinhos da esquerda e da direita. Neste tipo de rede regular, L é da ordem do número de nodos N, e C vale 1/2.

Grafo regular sobre o anel com grau 4 e 15 nodos.

A ideia de Watts e Strogatz foi a de construir um modelo que interpolasse entre estes dois casos extremos, à procura de um regime intermédio em que as características complementares dos dois tipos de grafos aparecessem combinadas.

Tomemos como ponto de partida uma destas redes regulares, N nodos dispostos ao longo de um anel, com ligações locais entre cada nodo e os quatro nodos mais próximos, os dois que o antecedem e os dois que lhe sucedem sobre o anel. Com probabilidade p, substituamos cada uma das ligações locais por uma ligação aleatória. Quando p=0 temos a rede regular inicial, para p=1 obtemos uma rede aleatória, e os valores intermédios de p correspondem a redes em que a estrutura local é parcialmente substituída por ligações aleatórias.

Propriedades do grafo do modelo de Watts e Strogatz para diferentes valores de p.

No gráfico seguinte podemos ver como variam C e L com p:

Coeficiente de aglomeração e distância média entre nodos em função de p.

Este processo simples e não coordenado produz, para valores baixos de p, uma rede onde o coeficiente de aglomeração ainda é elevado, mas que ao mesmo tempo é um mundo pequeno, porque basta um pequeno número de ligações aleatórias para reduzir drasticamente a distância média entre os nodos em relação a uma rede regular. Este é o modelo mais simples de rede complexa, e reproduz as principais características de muitas redes socias.