Formação de grupos em redes aleatórias

Conforme vimos anteriormente, em uma rede aleatória suficientemente grande uma grande componente conectada se forma quando a densidade desta rede ultrapassa um valor crítico. Assim, continuando o estudo das propriedades deste modelo de rede, podemos dizer que encontraremos grupos nestas redes tal como acontecem em redes reais? Já introduzimos anteriormente esta questão quando estudamos a formação de grupos em redes reais e neste artigo queremos nos aprofundar nisto.

O principal índice usado para estudarmos a formação de grupos em redes é o coeficiente de aglomeração, que para um nó ($CC_i$) pode ser calculado por $CC_i=\frac{2c_i}{d_i(d_i-1)}$, onde $c_i$ é o número de enlaces compartilhados entre os vizinhos do nó $i$ e  $d_i$ é o grau de um nó $i$. Vejamos então, teoricamente, como se comporta o $CC_i$ típico em uma rede G(n,p).

Na média, o coeficiente de aglomeração de um nó em uma rede aleatória é dado por $\overline{CC} = \frac{2\overline{c}}{\lambda(\lambda-1)}$, onde $\lambda$ é o grau médio da rede e $\overline{c}$ é o número médio de arestas entre os vizinhos de um nó na rede. Note que este resultado é direto, dado que apenas substituímos os valores específicos de um nó por valores médios da rede. Contudo, resta-nos capturar o valor de $\overline{c}$.

Para isso, devemos lembra que o número de máximo de arestas entre os nós vizinhos a $i$ é $\frac{d_i(d_i-1)}{2}$. Nas redes aleatórias, este valor é em média $\frac{\lambda(\lambda-1)}{2}$. Sabemos que o processo de adição de cada aresta na rede é um processo de Bernoulli independente com probabilidade de sucesso $p$ (vimos inclusive que, por conta disso, as redes aleatórias não são livres de escala). Assim, temos que o número de arestas entre os vizinhos de um nó se distribui como uma Binomial com parâmetros $\frac{\lambda(\lambda-1)}{2}$ e $p$. Desta forma, o número médio de arestas entre os vizinhos de um nó é dado por $\overline{c} \cong p\frac{\lambda(\lambda-1)}{2}$.

Substituindo o valor de $\overline{c}$ na equação do coeficiente de aglomeração médio do nó ($\overline{CC}$) temos que $\overline{CC} \cong p$. Desta forma, o coeficiente de aglomeração na rede é dado por $CC_{rnd} \cong \frac{\sum_n p}{n} \cong \frac{np}{n}$.

Este resultado tem dois significados. Em primeiro lugar, podemos verificar que $CC_{rnd} \cong p$, o que significa que o coeficiente de aglomeração cresce linearmente conforme aumentamos a probabilidade de conexão $p$. Como $p$ é a densidade da rede, este resultado está nos dizendo que precisamos que a densidade da rede aleatória seja em torno de 5% para que tenhamos um coeficiente de aglomeração de também 5%. 

Este resultado é bastante distante daquilo que vimos em redes reais. Reproduzimos abaixo alguns resultados do estudo que fizemos anteriormente (em uma série de 5 artigos). Para cada uma das redes reais que estudamos apresentamos o grau médio ($\lambda$), a densidade da rede, a quantidade de nós na rede ($n$) e o coeficiente de aglomeração na rede ($CC$). Estes dados mostram que contrário ao que acontece em redes aleatórias, redes de baixa densidade (entre 0,05% e 1,8%) apresentam altos coeficientes de aglomeração (entre 5% a 26%).

Rede	$\lambda$	Densidade	$n$	$CC$
Facebook	70,59	1,811%	3.898	0,262
Erdos	2,95	0,058%	5.094	0,082
Energia	2,67	0,054%	4.941	0,080
Proteína	2,90	0,144%	2.018	0,046

O segundo significado que podemos extrair do resultado teórico que encontramos é que, como $\lambda = np$ em redes aleatórias, $CC_{rnd} \cong \frac{\lambda}{n}$. Desta forma, podemos estimar com facilidade o coeficiente de aglomeração de uma rede aleatória dados apenas os respectivos parâmetros da rede: $n$ e $p$ em redes G(n,p); e $n$ e $m$ em redes G(n,m). 

Abaixo mostramos os resultados de um experimento onde geramos redes de 2000 nós com diferentes valores de grau médio. Para cada rede gerada, são apresentados o valor de $CC$ (valor real medido na rede gerada) e o $CC_{rnd}$ estimado. Observe como o valor de $CC_{rnd}$ dá uma boa estimativa para $CC$.

$\lambda$	$CC$	$CC_{rnd}$
2	0,0007	0,0010
3	0,0013	0,0015
4	0,0026	0,0020
5	0,0019	0,0025
6	0,0039	0,0030
7	0,0040	0,0035
8	0,0030	0,0040
9	0,0039	0,0045

Este resultado ($CC_{rnd} \cong \frac{\lambda}{n}$) figura originalmente no artigo Collective dynamics of ‘small-world’ networks de Watts e Strogatz, e uma demonstração parecida com a que apresentamos aqui (embora por um caminho distinto) pode ser encontrada no livro Network Science de Ted Lewis. Ele é importante por que, por meio de parâmetros simples como grau médio e quantidade de nós, nos deixa determinar se uma rede complexa real é fortemente agrupada ou não.

Considerando novamente as redes de estudo e usando a aproximação para redes aleatórias, vemos que para a rede Facebook $CC_{rnd} \cong \frac{70,59}{3898} \cong 0,0181$. Isto indica que esta rede é fortemente agrupada, já que o coeficiente de aglomeração real da rede ($CC$) excede, e muito, o valor de $CC_{rnd}$ calculado para a rede. O mesmo procedimento pode ser feito para as redes Erdos, Energia e Proteína, no qual é possível verificar que estas redes também são fortemente agrupadas.

Como vimos, a simples aleatoriedade, embora permita a geração de redes fictícias conexas, ainda que esparsas, não permite que surjam agrupamentos nestas mesmas redes, a não ser quando deixam de ser esparsas. Veja que se mantivermos o mesmo grau médio e aumentarmos $n$, o valor de $CC_{rnd}$ cai rapidamente, porque a rede se torna mais esparsa.

Isto quer dizer que a componente aleatória não é suficiente para explicar o fenômeno da formação de grupos que vemos em redes reais, ou seja, tais redes possuem componentes determinísticas (i.e., regulares) dirigindo o processo de associação dos nós. Em redes de energia, por exemplo, isto pode ser causado pela associação de elementos geradores em grupos, enquanto que em redes sociais, podem se dar pela formação de grupos sociais sólidos como grupos de parentes, amigos de escola etc. 

Independentemente do domínio da rede complexa, a lição que tiramos deste resultado é que devemos buscar componentes determinísticas para explicar melhor o fenômeno dos grupos nas redes complexas. Faremos isso quando estudarmos outros modelos de redes.