Na primeiro artigo e no segundo artigo desta série, apresentamos, respectivamente, que redes complexas tendem a ser esparsas e livres de escala. Fizemos isto mostrando redes complexas reais, cujos dados podem ser acessados publicamente. São elas: Facebook, Erdos, Energia e Proteína. Neste terceiro artigo da série, vamos apresentar outras propriedades das redes complexas.
Na tabela abaixo mostramos o
coeficiente de aglomeração ($CC$) das quatro redes em estudo. Vemos ainda a quantidade de nós na rede com coeficiente de aglomeração igual à 1 ($CC=1$). Por fim, mostramos o coeficiente de aglomeração para uma rede aleatória equivalente ($CC_{rnd}$).
| Rede | $CC$ | $CC=1$ | $CC_{rnd}$ |
|---|
| Facebook | 0,262 | 46 | 0,018 |
| Erdos | 0,082 | 305 | 0,0004 |
| Energia | 0,080 | 221 | 0,0003 |
| Proteína | 0,046 | 53 | 0,001 |
Estes resultados mostram que, de modo geral, as redes complexas apresentam um alto coeficiente de aglomeração. Ok, você sabe que este valor varia entre 0 e 1, e deve estar achando os valores baixos. Mas note que um valor próximo de 1 é extremamente raro em redes reais, já que exigiria que os nós estivessem todos conectados entre si e nós já sabemos
que isso tem um alto custo. Portanto, os valores que vemos na coluna $CC$ podemos considerar alto.
Isso fica mais claro se nós compararmos estas redes com uma rede aleatória de mesmo porte (mesmo número de nós e de enlaces). Ainda não falamos sobre modelos de redes neste blog, mas pense nisso como um método para construir uma rede fictícia que emula redes complexas reais. O modelo aleatório é o mais simples dos métodos usados para construir redes fictícias (e o que tem pior desempenho em emular redes reais) e se trata da simples inserção aleatória de enlaces entre os nós, de forma equiprovável.
Mas por que estou usando um modelo que eu sei que não emula bem as redes reais? Porque ele serve para mostrar que se o processo de ligação dos nós na rede fosse puramente estocástico, o coeficiente de aglomeração deveria ser de uma ordem de magnitude muitas vezes menor do que o encontrado na rede real (na rede Erdos, por exemplo, o $CC_{rnd}$ é 20 vezes menor). Portanto, deve haver algum aspecto estrutural nas redes que faz com que o $CC$ seja alto.
O que este resultado nos permite saber é que
redes complexas são formadas por agrupamentos de elementos fortemente conectados entre si (enlaces de curto alcance), em que alguns elementos se ligam a elementos de outros grupos (enlaces de longo alcance). Esta observação foi feita primeiramente por Watts e Strogatz no artigo
Collective dynamics of ‘small-world’ networks de 1998, mas deve-se dizer que ele é bem esperado.
Pense em sua rede social real. Você costuma ter amigos que normalmente são amigos uns dos outros, em outras palavras o grupo é densamente conectado e seus enlaces são chamados enlaces curtos. Contudo, você possui alguns amigos em outros grupos sociais (como o clube, a escola, o trabalho...) aos quais seus amigos podem não pertencer. Estes são os enlaces longos, são eles que fazem a rede ser conectada e permitem que informações/gostos/opiniões de um grupo possam se propagar para outros grupos.
Assim como fizemos no artigo anterior, para o grau, poderíamos aqui procurar aqueles nós que tem maior índice de aglomeração. Este tipo de análise não é assim tão interessante, porque estes nós tendem a ter pouca importância na rede. De toda forma, nas redes em estudos pudemos observar que a quantidade de nós com $CC_i = 1$ pode chegar a 5% dos nós (como no caso da rede Erdos) ou apenas 1% dos nós (rede Facebook).
Mas, será que os nós de maior grau têm também maior coeficiente de aglomeração? Na realidade não, e justamente o contrário é verdade. Isso ocorre porque é mais provável que todos os vizinhos de um nó com grau baixo (2 ou 3) sejam conectados (fazendo $CC_i = 1$), do que todos os 30 ou 40 vizinhos de um nó de alto grau. Lembre-se de que redes complexas são esparsas, logo para que os nós de grau elevado tivessem também alto coeficiente de aglomeração seria necessário aumentar muito a quantidade de enlaces na rede.
Para ilustrar o que dissemos, vejamos na tabela abaixo o coeficiente de aglomeração de cada um dos top5 nós de maior grau em cada rede. Cada dupla $(i, d_i)$ apresenta o identificador do nó $i$ com seu respectivo coeficiente de aglomeração $CC_i$. As duplas estão ordenadas pelo grau dos nós que foram
apresentados no artigo anterior.
| Ordem | Facebook | Erdos | Energia | Proteína |
|---|
| 1 | (3755, 0,032) | (431, 0,013) | (2553, 0,064) | (1356, 0,008) |
| 2 | (2506, 0,069) | (443, 0,041) | (4458, 0,007) | (1400, 0,006) |
| 3 | (3521, 0,055) | (343, 0,021) | (831, 0,011) | (1637, 0,003) |
| 4 | (38, 0,069) | (314, 0,024) | (3468, 0) | (1017, 0,002) |
| 5 | (2473, 0,055) | (298, 0,03) | (4345, 0,22) | (528, 0,007) |
Como se pode observar, de modo geral, os coeficientes de aglomeração dos nós de maior grau são mais baixos do que o coeficiente de aglomeração médio da rede ($CC$). Este exemplo mostra também que quando empregamos os termos "geralmente", "tendem", não estamos sendo vagos, mas tentando mostrar que as propriedades que observamos são regras gerais, e não leis.
Em outras palavras, queremos dizer que podem haver exceções às propriedades que aqui abordamos. E isso acontece com o nó 4345 da rede Energia, cujo coeficiente de aglomeração é alto. Este nó possui 14 vizinhos os quais possuem entre si 20 arestas das 91 possíveis ($\frac{14*13}{2}=91$). Este tipo de situação é interessante porque ilustra o caso de um nó que combina importância global na rede (grau alto) com forte participação em um grupo (coeficiente de aglomeração destacado).
Como não temos descrição sobre os nós da rede de energia, não podemos compreender exatamente qual o papel deste nó. Contudo, podemos supor que ele poderia ser parte de um grupo de usinas de geração de energia de pequena capacidade (Pequenas Centrais Hidrelétricas) que são interligadas entre si para redistribuição da capacidade, sendo que o nó 4345 seria um nó de maior capacidade, por exemplo.
Bom, para resumir, é comum que redes complexas possuam alto coeficiente de aglomeração e que seus nós de maior grau possuam coeficiente de aglomeração baixo. No próximo artigo continuaremos este estudo observando outras propriedades das redes complexas.
Comentários
Postar um comentário