As suas relações sociais são aleatórias?

Estamos chegando ao fim de nosso estudo sobre as redes aleatórias e queremos neste artigo discutir se estas redes apresentam caminhos curtos, como vimos nas redes complexas reais. Mas antes, vamos recapitular o que sabemos sobre estas redes até agora. 

Nós vimos dois tipos de algoritmos para geração de redes aleatórias fictícias: as redes G(n,p), propostas por Gilbert; e as redes G(n,m), propostas por Erdös e Rényi. A despeito da diferença de algoritmo, vimos que os modelos gerados são equivalentes entre si, possuindo as mesmas propriedades. Controlando os parâmetros destas redes, percebemos que é possível gerar redes fictícias esparsas com densidade similar àquelas vistas em redes reais e que, a depender do valor da densidade ($densidade > \frac{1}{n-1}$), a rede forma uma componente conectada proeminente, contendo a maior parte dos nós da rede.

Em nossos estudos também vimos que a distribuição do grau nestas redes segue uma distribuição binomial, fazendo com a rede tenha a maior parte de seus nós com grau próximo da média e distribuídos de forma simétrica em relação à ela, ou seja, vimos que estas redes não são livres de escala. Também vimos que a aglomeração em redes aleatórias cresce linearmente com a densidade, precisando que a rede deixe de ser esparsa para que os grupos surjam, o que não é observado em redes reais.

Mas e quanto a formação de caminhos curtos? Será que as redes aleatórias são eficientes como as redes reais?

Veremos que a resposta para estas questões é sim e faremos isso, inicialmente, mostrando com um modelo teórico. 

Considere a métrica de Tamanho Médio do Caminho. É possível observar que de modo geral, conforme $p$ aumenta, o tamanho médio do caminho tende a diminuir, porque há um aumento da densidade. Da mesma forma, se aumentarmos o grau médio ($\lambda$) também diminuímos o TMC. Assim, existe uma aproximação para o valor do tamanho médio do caminho, que é dada por $\frac{\log{n}}{\log{\lambda}}$.

A ideia por trás da fórmula é que em uma rede aleatória suficientemente grande de grau médio $\lambda$, se partirmos de um nó qualquer atingiremos $\lambda$ nós com um salto, $\lambda^2$ nós com dois saltos (já que cada vizinho do nó original tem em média $\lambda$ vizinhos) e, generalizando, $\lambda^D$ nós com $D$ saltos. Assim, assumindo que $D$ é a quantidade de saltos média para atingir todos os $n$ nós da rede, teremos:

$n=1+\lambda+\lambda^2+\lambda^3+\ldots+\lambda^D$

O que temos acima é a soma de uma progressão geométrica com razão $\lambda$, o primeiro termo $1$ e o último termo $\lambda^D$, que pode ser calculada por

$n = 1 \times \frac{\lambda^{D+1}-1}{\lambda-1}$

Este valor pode ser aproximado por $\lambda^D$, para $\lambda$ grande. Assim temos que 

$n \cong \lambda^D \Rightarrow \log{n} \cong D\log{\lambda} \Rightarrow D = \frac{\log{n}}{\log{\lambda}}$

Este resultado aparece no trabalho Models of the Small World de Mark Newman, reconhecido autor na área de Ciência das Redes cujos esforços ajudaram muito a sedimentar os principais achados dela. Neste artigo, publicado no Journal of Statistical Physics em 2000, Newman revê diversos aspectos do efeito mundo-pequeno (small-world effect) sendo esta equação um dos resultados. Este é um resultado importante porque o aumento logarítmico do TMC com o tamanho da rede é a representação formal do efeito de efeito mundo-pequeno. Como $\log{n}$ cresce devagar com $n$, a tendência é que o TMC cresça pouco em sistemas muito grandes.

Note que o resultado é uma boa aproximação para o comportamento geral do TMC, mas que tende a subestimar o valor real. Para isso, Ted Lewis, em seu livro Network Science: Theory and Applications, apresenta outra aproximação que encontra melhores resultados. Sua aproximação para o TMC, obtida experimentalmente via regressão por mínimos quadrados, é

$TMC  = \frac{1.32(\log_2{n})}{\log_2{(1.51\times n \times densidade)}}$

Para demonstrar a acurácia do modelo de Lewis, realizei uma simulação para redes G(n,p) com 100, 150 e 200 nós e para diferentes valores de grau médio ($\lambda = {7,8,\ldots,14}$). Para cada rede gerada, computamos o TMC obtido na rede e o TMC aproximado pelos modelos de Newman e de Lewis. Os gráficos abaixo mostram os resultados desta simulação e o comportamento que havíamos descrito.

Com isso, vimos que o modelo de redes aleatórias consegue explicar o fenômeno mundo-pequeno que se apresenta também em redes reais. Mas, considerando as demais propriedades, vimos que o coeficiente de aglomeração e a distribuição do grau estão longe dos valores encontrados na realidade. Isto ocorre porque poucos fenômenos na natureza são puramente aleatórios. As redes reais sempre possuem alguma estrutura.

Mas então, por que estudar modelos aleatórios? Primeiramente, porque eles oferecem um modelo de referência para o estudo dos outros modelos. Em segundo lugar, os modelos aleatórios mostram que a aleatoriedade é um elemento essencial para diminuir as distâncias de uma rede, de modo a gerar o efeito de mundo-pequeno.

Para demonstrar com maior clareza o efeito da aleatoriedade sobre redes estruturadas, considere a inserção de enlaces aleatórios em uma rede em anel mostrada na figura abaixo. Esta figura é inspirada em um experimento descrito no livro de Ted Lewis. Nós iniciamos com uma rede em anel com 100 nós e vamos introduzindo arestas ($L$ é a quantidade de arestas inseridas) de forma aleatória e uniforme, i.e., assumindo que a escolha dos nós é equiprovável. Este processo é similar ao que ocorre na rede G(n,m), exceto pelo fato de que a rede inicial já possui um conjunto de arestas.

A Figura mostra a evolução do processo desde a rede inicial até a inserção de $L=9$ arestas. Observe que, conforme adicionamos enlaces, as medidas relativas ao tamanho médio dos caminhos e ao diâmetro tendem a diminuir. A adição de apenas um pequeno número de enlaces ($L=6$), por exemplo, consegue reduzir o tamanho médio do caminho pela metade. O efeito da introdução da aleatoriedade é dramático. Em outras palavras, a adição de alguma aleatoriedade em uma rede regular leva ao efeito mundo-pequeno.

Este resultado nos ajuda a entender com mais clareza o que vemos em redes reais. Nós já reportamos a existência nas redes complexas de enlaces curtos e longos ou, respectivamente, enlaces intra-grupo e enlaces inter-grupo. Considerando as redes sociais, por exemplo, as relações mais próximas e evidentes são os enlaces curtos, enquanto que as relações casuais são os enlaces longos. Tais relações casuais, que surgem por preferências pessoais ou outras circunstâncias (determinísticas no nível microscópico), podem ser vistas, do ponto de vista macroscópico, como aleatórias e independentes. 

Assim, embora as relações mais próximas ajudem na formação de grupos mais coesos, são as relações aleatórias (casuais) que tornam a rede "menor". Em próximos artigos, falaremos mais sobre o fenômeno mundo-pequeno. Se tiver dúvidas deixe nos comentários. E se gostou é só marcar aí embaixo.