Coeficiente de Aglomeração

Considere a rede abaixo e foquemos nos nós 0 e 4, cada um deles com grau 5. Se estivéssemos querendo determinar a "importância" destes dois nós poderíamos, olhando apenas para esta métrica, dizer que eles tem a mesma "importância" na rede. Certo?

Grafo para estudo do coeficiente de aglomeração

Contudo, você observa que o nó 4 se insere em uma porção do grafo que é muito mais conectada? Seus vizinhos se interligam e neste sentido, parece que o nó 4 faz parte de uma comunidade e tem, por isso, uma "importância" diferente daquela do nó 0.

Para medir essa forma de "importância" podemos usar uma outra métrica chamada de coeficiente de aglomeração (Cluster Coefficient – $CC$, em inglês). De modo informal, a função do coeficiente de aglomeração é medir o quanto a vizinhança de um nó é coesa. Assim, o coeficiente de aglomeração do nó será maior quanto mais de seus vizinhos estiverem conectados entre si. 

Formalmente dizemos que se \(d_i\) é o grau de um nó \(i\), o número máximo de enlaces entre os vizinhos do nó $i$ em uma rede dirigida é $d_i(d_i-1)$ (o nó $i$ tem $d_i$ vizinhos e cada um se conecta a $d_i-1$ nós). Logo, em uma rede não-dirigida, este valor cai pela metade $\frac{d_i(d_i-1)}{2}$.

Assim, considerando redes não-dirigidas e sendo $c$ o número de enlaces compartilhados entre os vizinhos do nó $i$, temos que \(CC_i=\frac{2c}{d_i(d_i-1)}\). Em outras palavras, o coeficiente de aglomeração de um nó é um percentual da quantidade de enlaces possíveis entre os vizinhos de um nó. Observe que que $c$ não contabiliza todos os enlaces que os vizinhos de $i$ tenham, mas apenas aqueles para os nós vizinhos de $i$.

Considerando a rede de exemplo, podemos observar diretamente que $CC_0 = CC_1 = CC_2 = CC_6 = CC_7 = 0$, já que os vizinhos destes nós não se conectam entre si. Temos ainda que $CC_3 = CC_5 = CC_9 = 1$, pelo motivo oposto. Já para o nó 8 temos que $d_8 = 4$ e o número de enlaces entre seus vizinhos é 4, logo $CC_8 = \frac{2*4}{4*3} \approx 0,667$. Finalmente, para o nó 4 temos $CC_4 = \frac{2*4}{5*4} = 0,4$.

Em redes sociais, valores elevados para o coeficiente de aglomeração de um nó (para redes grandes, um valor acima de 0,2, por exemplo, é considerado elevado) indicam que o nó participa, provavelmente, de alguma comunidade em que há certa coesão entre os membros do grupo social tal como famílias, partidos políticos etc. 

Esta medida pode ser inclusive calculada sob a perspectiva da rede, de forma que o coeficiente de aglomeração da rede como um todo é dado pela média do coeficiente de aglomeração de seus nós $CC(G) = \sum\limits_{i=1}^{n}\frac{CC_i}{n}$. Para a rede que estudamos temos que 

$CC(G) = \frac{0+0+0+1+0,4+1+0+0+0,667+1}{10} \approx 0,407$.

Isso indica que a rede, de forma geral, possui alguma comunidade bem estruturada e coesa. Apesar do que pode parecer, este tipo de propriedade não é encontrada apenas em redes sociais. Redes complexas em domínios distintos tendem a apresentar um alto coeficiente de aglomeração. 

No trabalho seminal de Watts & Strogatz, por exemplo, a rede de colaboração de atores (uma rede social) apresentou um alto $CC$ de 0,79, como era de se esperar. Mas o surpreendente é que a rede biológica estudada neste trabalho (rede neural do c. elegans) apresentou um $CC$ elevado de 0,28, indicando que há fortes "comunidades" de neurônios. Falaremos mais sobre estas características em outra oportunidade.