Redes complexas: Da internet às redes sociais

Grafos aleatórios e o efeito mundo pequeno

Antes de vermos o que é um grafo aleatório, façamos uma pequena digressão pelo conceito de probabilidade. Historicamente a noção de probabilidade teve a sua origem no estudo dos jogos de azar e o seu propósito era medir quão plausível, ou não, era um determinado acontecimento.

À esquerda, representação da fortuna (sorte); à direita, conjunto de dados do póquer e a roleta.

Classicamente a probabilidade é definida pelo quociente do número de casos favoráveis pelo número de casos possíveis, quando todos os casos são igualmente plausíveis. Por exemplo quando se lança uma moeda ao ar temos dois casos possíveis: ou sai cara ou sai coroa. Como ambos os casos são igualmente plausíveis a probabilidade de sair cara é 1/2 e a probabilidade de sair coroa é 1/2. A aplicação do mesmo tipo de raciocínio ao lançamento de um dado mostra que a probabilidade de sair qualquer um dos seis números é 1/6, enquanto que a probabilidade de sair um número par é 3/6 = 1/2.

Os grafos aleatórios constroem-se da seguinte forma:

1. pega-se numa colecção de nodos,
2. pega-se numa moeda viciada que tenha probabilidade p de sair cara quando lançada ao ar, para cada par de nodos lança-se a moeda ao ar, se sair cara unem-se os dois nodos com uma aresta, se sair coroa deixam-se desligados.

Um grafo aleatório pode ser imaginado como uma colecção de botões ligados por fios, onde pares de nodos (botões) estão ligados ao acaso por intermédio de arestas (fios).

Os grafos aleatórios são o modelo mais simples que permite compreender o efeito de small world, ou porque é que o mundo social é pequeno. As suas principais propriedades foram estudadas e descritas nos anos 60 por Erdös e Rényi. Num grafo aleatório não existe nenhum critério que privilegie umas ligações em relação a outras, e portanto este fica caracterizado pelo número de nodos N e pela probabilidade p de que uma ligação qualquer das N(N-1)/2 possíveis ligações entre nodos diferentes seja estabelecida. Na figura seguinte podemos ver algumas realizações de grafos aleatórios com cem nodos para diferentes probabilidades p.

Realizações de grafos aleatórios, com 100 nodos, para diferentes valores de probabilidade p.

Diferentes realizações de um grafo aleatório com N e p fixos darão origem a estruturas diferentes, mas a média do número de ligações destes diferentes grafos será igual a pN(N-1)/2. Portanto, o grau médio do grafo, <k>, ou seja, o número médio de arestas que cada nodo tem, vem dado por <k>=p(N-1), uma vez que cada ligação 'serve' dois nodos. Para N grande a distribuição de probabilidades para os graus dos nodos é bem aproximada por uma distribuição de Poisson de valor médio <k> como as representadas na figura seguinte para alguns valores de <k>.

Distribuição de Poisson para diversos valores de <k>.

Vejamos como uma rede com esta estrutura dá origem ao efeito de small world. Escolhamos ao acaso um nodo do grafo como ponto de partida. Este nodo terá em média <k> primeiros vizinhos, cada um dos quais também com <k> primeiros vizinhos, ou seja, o nodo inicial tem aproximadamente <k>² segundos vizinhos. Seguindo o mesmo raciocínio, o nodo inicial terá cerca de <k>ⁿ n-ésimos vizinhos, isto é, nodos a uma distância de n graus de separação. Quando tivermos <k>^L ~ N, a cadeia construída a partir do nodo inicial pode chegar a qualquer nodo da rede, e portanto o número máximo de graus de separação num grafo aleatório é da ordem de L, que é da ordem do logaritmo de N. Ou seja, 6 graus de separação é um resultado plausível numa rede aleatória com vários milhões de nodos.

O modelo dos grafos aleatórios explica no essencial o efeito de small world. Mas será que as redes sociais são bem modeladas por este tipo de grafos?