A distribuição do grau no modelo GBA

Nos artigos anteriores (aqui e aqui) apresentamos o modelo GBA e introduzimos a ideia de que este modelo consegue gerar redes complexas livres de escala. Neste artigo pretendemos verificar esta propriedade por meio de alguns experimentos.

A distribuição do grau da rede GBA, como já apontado, segue uma distribuição lei de potência do tipo $k^{-q}$, com $2 \le  q \le 3$. Uma aproximação bastante usada na literatura para a distribuição do grau em uma rede GBA é dada por

$P(d_i=k) = \frac{2\Delta m (\Delta m+1)}{k(k+1)(k+2)}$

Este modelo é uma aproximação introduzida por Mark Newman no artigo The structure and function of complex networks publicado em 2003. Mark Newman é um físico com importantes contribuições na área de sistemas complexos, por sinal, é autor do livro Networks cuja segunda edição é de 2018, portanto bem recente, e que cobre um amplo espectro de assuntos sobre a ciência das redes.

O racional do modelo é que ele é uma consequência direta do saldo médio de nós com grau $k$ quando cada nó é inserido na rede GBA. Ao inserirmos um nó na rede, uma parte dos nós de grau $k-1$ muda para o grau $k$ e uma parte dos nós, deixa de ter grau $k$ e passa a ter grau $k+1$. Portanto, a diferença entre estas quantidades vai determinar para onde caminha, em média, a distribuição $P(d_i=k)$. Mais detalhes desta derivação estão no artigo de Mark Newman.

Um ponto importante deste modelo é que ele mostra que para um valor grande de $k$ e um valor de $\Delta m$ constante é uma lei de potência com $q = 3$. Assumindo que $\Delta m = 3$, temos que $P(d_i=k) = \frac{24}{k^3 + 3k^2 + 2k}$. Assim, de fato, a probabilidade $P(d_i=k)$ cresce com $O(k^{-3})$. Outro ponto importante é que o modelo aponta que a distribuição segue uma lei de potência independentemente do tamanho da rede GBA.

O gráfico abaixo compara a distribuição do grau medida em uma rede GBA simulada (cruzes pretas) com $n=100.000$, $\Delta m  = 3$, $n_0 = 3$ e $m_0 = 3$ com a distribuição obtida pelo modelo de Newman (linha tracejada em vermelho). O resultado ilustra a precisão do modelo para redes GBA.

Olhando para outras medidas da rede gerada acima, vemos que o grau médio é $\lambda = 5,99982$, que o grau do Hub é $d_{max} = 957$ (não mostrado no gráfico acima, que está limitado ao grau 500), que o percentual de nós com grau abaixo da média é d$P(d_i<\lambda) = 71,49\%$ e que o percentual dos nós com grau acima de 3 desvios-padrão da média é de $P(d_i>\lambda+3\sigma) = 0,9\%$. Estas medidas demonstram a grande disparidade do grau dos nós, que é uma característica marcante nas redes complexas que estudamos anteriormente.

A respeito do grau médio, podemos ainda estimá-lo com bastante acurácia. Sabemos que $\lambda = \frac{2m}{n}$ e que, para $n$ grande, a quantidade de enlaces da rede GBA pode ser aproximada por $m \simeq n \Delta m$. Assim, o grau médio em redes GBA pode ser estimado por $\lambda \simeq \frac{2n\Delta m}{n} = 2\Delta m$. Como podemos ver, este valor é bastante preciso para o caso da rede anterior em que $\Delta m = 6$. A Tabela abaixo mostra o grau médio para redes GBA com diferentes parâmetros de $n$ e $\Delta m$ (em todos os casos, $n_0 = m_0 = 3$).

$\Delta m$	$n$	$\lambda$	$2\Delta m$
2	1000	3,994	4
2	1500	3,996	4
2	2000	3,997	4
2	2500	3,998	4
4	1000	7,980	8
4	1500	7,987	8
4	2000	7,990	8
4	2500	7,992	8
6	1000	11,958	12
6	1500	11,972	12
6	2000	11,979	12
6	2500	11,983	12
8	1000	15,928	16
8	1500	15,952	16
8	2000	15,964	16
8	2500	15,971	16

Pode-se perceber que o modelo se adéqua bem aos diferentes casos e que o tamanho da rede (desde que seja um valor suficientemente alto) influencia pouco na variação de $\lambda$.

A partir destes resultados podemos ver que as redes geradas pelo modelo GBA são livres de escala. Nos próximos artigos discutiremos outras propriedades das redes GBA.