Características fundamentais das redes GBA

O modelo de geração de redes fictícias GBA introduz, por meio dos conceitos de crescimento e anexação preferencial, um tipo de rede cuja distribuição do grau segue uma lei de potência. Porém, será que os dois conceitos são necessários para obtermos a lei de potência? Em outras palavras, será que apenas um ou outro dos mecanismos seria suficiente para obtermos uma rede livre de escala? Podemos testar essa ideia, modificando o modelo GBA pela retirada de um e outro conceito.

Vamos iniciar criando um modelo sem anexação preferencial, isto é, um modelo de rede apenas com crescimento. Em tal modelo, os nós vão sendo adicionados à rede e juntamente são adicionados $\Delta m$ enlaces, porém a ligação dos novos enlaces é feita segundo uma distribuição uniforme: todo nó possui a mesma probabilidade de ser escolhido. Para facilitar nossa apresentação, chamaremos este modelo de Modelo A.

A gráfico abaixo mostra a distribuição do grau de duas redes uma gerada pelo modelo GBA (cruzes pretas) e outra gerada pelo Modelo A (círculos vermelhos). Em ambos os casos $n=100000$, $\Delta m =3$, $n_0=3$ e $m_0 = 3$.

Embora seja assimétrica, como esperado em uma rede livre de escala, pode-se observar que a cauda da distribuição do grau da rede do Modelo A decresce mais rápido do que no modelo GBA, o que caracteriza a distribuição do grau da rede gerada pelo Modelo A como uma distribuição exponencial e não uma lei de potência. 

Este fato é confirmado ao observarmos os histogramas das distribuições do grau de cada modelo, mostrados abaixo. Neles observamos que o grau do Hub é muitas vezes menor no Modelo A do que no modelo GBA.

Agora criaremos o Modelo B, onde excluiremos o crescimento, deixando apenas a anexação preferencial. Assim, iniciamos com uma rede com todos os nós já dispostos e a cada iteração adicionamos $\Delta m$ enlaces e cada um deles estará ligado a um nó $i$ que será selecionado aleatoriamente com probabilidade $\frac{d_i}{\sum{d_i}}$, de modo a manter a anexação preferencial. A outra extremidade do enlace será ligada ao nó $k$, escolhido dentre os outros nós de forma equiprovável. 

A Figura abaixo mostra a distribuição do grau de uma rede gerada pelo modelo B e outra rede gerada pelo modelo GBA. Em ambos os casos $n=1000$, $\Delta m =3$, $n_0=3$ e $m_0 = 3$.

Pode-se observar que a forma da distribuição do grau do Modelo B aparenta ser uma distribuição simétrica. Isto fica mais claro quando observamos os histogramas abaixo que mostram a distribuição do grau das redes gerada pelo modelo GBA e pelo Modelo B.

Estes resultados nos permitem ver que tanto o crescimento quanto a anexação preferencial são essenciais para a formação de redes livres de escala no modelo GBA. A remoção de um destes conceitos faz com que a distribuição do grau deixe de seguir uma lei de potência. De certa forma, cada um destes conceitos tem seu papel na geração de uma rede livre de escala e isso torna ainda mais interessante esta descoberta.