Transição de fase em redes aleatórias

Em artigo anterior, apresentamos o modelo das redes aleatórias: G(n,p) e G(n,m) e a partir deste artigo discutiremos algumas das propriedades destas redes quando comparadas as redes complexas reais. Como dissemos no artigo anterior, os modelos são equivalentes entre si e por isso escolheremos um deles para nos referir ao longo do texto. Preferimos, neste caso, fazer nossas análises com o modelo G(n,p) cuja componente de aleatoriedade é diretamente controlada pela probabilidade de conexão $p$.

Nós já vimos que redes complexas são conexas ou tendem a formar grandes componentes conectadas com a maior parte dos nós que a ela pertence. Sabendo disso, você acha que um processo completamente aleatório é capaz de gerar uma rede conexa? Note que o processo inicia com uma rede sem aresta alguma, e a esta são introduzidas, com certa probabilidade, algumas arestas. Portanto, será que é possível partindo de uma rede desconexa gerar uma rede conexa?

Você certamente já capturou a resposta, que é: depende! Se olharmos para o processo é óbvio que é possível gerar uma rede conexa. Para qualquer que seja $n$, se fizermos $p=1$ teremos uma rede conexa certamente e se fizermos $p=0$ teremos uma rede desconexa com a mesma certeza. Mas, o que temos no meio do caminho entre $p=0$ e $p=1$? Em outras palavras, será que precisamos de uma probabilidade de conexão próxima de 1 para que tenhamos uma rede conexa?

Esta pergunta foi respondida por Gilbert no artigo Random Graphs em que apresentou o modelo G(n,p). Gilbert demonstrou que, para $n$ muito grande (i.e., $n \to \infty$), a probabilidade de que a rede seja conexa $P(\epsilon = 1)$ ($\epsilon$ é a conectividade da rede, e indica o percentual de nós alcançáveis dentro da rede) pode ser aproximada por $P(\epsilon = 1) = 1 - nq^{n-1}$, onde $q$ é a probabilidade de que uma aresta não seja criada ($q = 1 -p$). 

O racional desta equação é que a probabilidade de uma rede ser conectada é o oposto da probabilidade de ser desconexa. Por sua vez, a probabilidade da rede ser desconexa é a probabilidade de que ao menos um de seus $n$ nós não esteja conectado à rede. Como cada nó pode possuir $n-1$ enlaces, ele participará do processo aleatório $n-1$ vezes e a probabilidade de que nenhum de seus enlaces seja criado é $q^{n-1}$.

A seguir mostramos o comportamento de $P(\epsilon = 1)$ com o crescimento de $p$, para uma rede com $n=4000$ (escolhi este valor por ser próximo das redes reais que estudamos anteriormente).

Comportamento da probabilidade da rede ser conexa em um modelo G(n,p)

Observe o eixo da probabilidade de conexão. Nele estamos variando a probabilidade entre 0,07% e 0,15%. Você notou como as probabilidades são pequenas? Com um valor de $p$ em torno de 0,11% a  rede já está (praticamente, $P(\epsilon = 1) = 0,9989843$) conectada! Vamos chamar este valor probabilidade crítica de conexão ($p_{cc}$). Este é o principal resultado que podemos tirar da equação que Gilbert encontrou: em redes grandes, basta uma pequena probabilidade de conexão para que a rede seja conexa.

Será que este resultado é importante apenas para os modelos de redes? Isso tem alguma conexão com redes complexas no mundo real? Sim e Sim! Este resultado corrobora a propriedade que observamos em redes complexas reais. Nós vimos que redes reais possuem densidade baixa, ou seja poucas arestas em proporção a quantidade possível dado o número de nós, e mesmo assim, tendem a ser conexas. 

O mesmo ocorre nas redes aleatórias: mesmo um nível relativamente baixo de densidade (lembre-se que no modelo G(n,p) a densidade é a própria probabilidade de conexão $p$) é capaz de deixá-las conectadas. O que estou tentando dizer é que a criação de algumas relações de forma aleatória entre um conjunto de nós - ou seja, sem um propósito guiando a criação destas arestas - é suficiente para que se forme uma rede na qual é possível encontrar um caminho de um nó para qualquer outro.

Retornando ao gráfico, observamos que para valores menores do que 0,11% a probabilidade de termos uma rede conectada, embora não seja 1, é alta. O que acontece neste intervalo $0 \leq p \leq p_{cc}$? Neste caso veremos que, embora a rede não esteja conectada, temos a formação de uma única grande componente conectada. 

Este é outro resultado importante na ciência das redes, divulgado por Erdös e Rényi em 1960 no trabalho On the evolution of random graphs (na seção 9 do artigo). Os autores descobriram que a conectividade $\epsilon$ passa por transições de fase, fenômenos similares aos encontradas em outros sistemas físicos.

A transição de fase é o fenômeno de mudança nas propriedades macroscópicas de um elemento/substância/sistema ocasionada pela mudança em uma propriedade microscópica sua. Você já estudou as transições de fase da água, por exemplo, em que a água muda de estado (sólido, líquido e gasoso) pelo aumento de sua temperatura (para uma certa pressão). Observe que temos duas temperaturas críticas neste caso: uma a partir da qual a água funde (temperatura de fusão) e outra a partir da qual a água evapora (temperatura de ebulição).

Erdös e Rényi observaram a transição de fase da componente conectada (propriedade macroscópica) quando aumentamos a probabilidade de conexão (propriedade microscópica). De início, para valores de probabilidade de conexão abaixo de um ponto crítico ($p_c$) a rede aleatória não forma uma componente conectada mais proeminente, mas acima dele a rede forma uma grande componente.

O gráfico abaixo mostra o comportamento da conectividade (percentual) em uma simulação considerando redes G(n,p) com 200 nós e com a probabilidade de conexão variando de 0 a 0,05. Cada ponto neste gráfico é uma rede gerada com seu respectivo valor de $p$ e de $\epsilon$. As flutuações no valor da conectividade ocorrem devido à natureza estocástica do experimento, contudo é possível observar a tendência geral da curva.

Os pontos destacados por linhas vermelhas tracejadas são os dois pontos críticos de interesse. O primeiro ponto ($p_c$), em torno de 0,003, é onde ocorre um "salto" (termo usado por Erdös e Rényi) a partir do qual a conectividade deixa de ter um valor muito baixo (próximo a zero) e passa a aumentar consideravelmente. Note que, neste ponto (chamaremos de probabilidade crítica), surgem diversas componentes conectadas na rede, com uma delas sendo um pouco maior que as outras, porém não muito destacada (tamanho na ordem de $n^{2/3}$). Quando a probabilidade de conexão ultrapassa $p_c$, uma grande componente se forma e envolverá todos os nós quando a probabilidade de conexão for maior que $p_{cc}$, cujo valor valor é próximo de 0,05 para esta rede.

Com base nestes dois pontos, podemos identificar três regiões no gráfico:

• Subcrítica: quando $p$ é menor que um valor crítico $p_{c}$. Nessa região a conectividade fica muito próxima de 0. O que significa que existem muitos nós isolados.
• Supercrítica: região entre $p_c$ e $p_{cc}$. Nesta região o número de nós na componente conectada cresce exponencialmente.
• Conectada: região a partir de $p_{cc}$. Neste ponto a rede se encontra conectada, i.e., todo nó na rede pode ser alcançado a partir de qualquer outro nó.

Uma observação importante no comportamento da componente conectada é que o valor exato de $p_c$  e $p_{cc}$ depende exclusivamente da quantidade de nós da rede aleatória. No entanto, Erdös e Rényi observaram que se considerarmos o grau médio da rede é possível estabelecer $p_c$ de forma mais geral.

Observe que o grau médio $\lambda$ de uma rede aleatória G(n,p) é dado por $\lambda = p(n-1)$ (falaremos sobre a distribuição do grau em redes aleatórias em outra oportunidade, mas você pode chegar neste resultado lembrando que o número de enlaces médio da rede G(n,p) e $m=p\frac{n(n-1)}{2}$. Assim, verificamos que para a probabilidade $p_c$ temos um grau médio crítico equivalente $\lambda_c$, o mesmo ocorre para $p_{cc}$ e $\lambda_{cc}$, sendo este último o grau médio crítico de conexão. O gráfico abaixo mostra o comportamento da conectividade com a variação do grau médio.

O comportamento da conectividade é o mesmo observado no gráfico com a variação de $p$, já que o grau médio cresce linearmente com a probabilidade $p$. As regiões identificadas também são as mesmas. Porém, o fato interessante é que $\lambda_c = 1$ qualquer que seja o tamanho da rede. Este foi o resultado que Erdös e Rényi chegaram e isso nos permite estimar a probabilidade crítica para qualquer rede aleatória, basta para isso sabermos a quantidade de nós da rede $p_c = 1/(n-1)$. 

Para ficar mais claro esse fenômeno reproduzimos abaixo redes 200 nós com diferentes valores de grau médio $\lambda = 0,8$, $\lambda = 1,0$ e $\lambda = 1,2$. Observe o crescimento do tamanho da componente conectada em cada caso.

O fenômeno da transição de fase em redes aleatórias também aparece no artigo Statistical mechanics of complex networks de Albert e Barabasi, publicado em 2002, no qual os autores estabelecem uma relação entre a observação de transição de fase encontrada por Erdös e Rényi e a teoria de percolação.

Diferentemente do valor de $\lambda_c$,  não temos uma estimativa precisa para o valor do grau médio crítico de conexão $\lambda_{cc}$. Como demonstrou Gilbert, a probabilidade de termos uma rede conectada, para um $n$ fixo e grande, se aproxima assintoticamente de 1 com o aumento de $p$, ou seja, temos uma boa probabilidade de obter uma rede conexa, mas não há garantia disto, afinal de contas existe sempre a possibilidade (ainda que pequena $q^{n-1}$)  de que um nó não tenha enlaces. 

Contudo, Watts e Strogatz (em Collective dynamics of ‘small-world’ networks) comentam, baseados no livro Random Graphs de Béla Bollobás (infelizmente não tenho este livro dar mais detalhes da demonstração), que para $\lambda_{cc} \gg \ln{n}$, praticamente todas as redes aleatórias geradas serão conectadas. Este fenômeno é possível observar por experimentação.