Redes complexas e seus caminhos curtos

Chegamos ao último da artigo de nossa série! Nestes artigos estamos estudando redes complexas reais (são elas: Facebook, Erdos, Energia e Proteína) por meio de métricas bem definidas em redes complexas como grau médio, coeficiente de aglomeração, conectividade etc. Por meio deste estudo tenho mostrado algumas das propriedades presentes nas redes complexas. 

Nós já vimos, por exemplo, que redes complexas são esparsas, i.e., têm um baixo número de enlaces em proporção ao número de nós. A despeito disso, vimos que elas tendem a formar uma única grande componente conectada cujos nós estão dispostos em grupos de alta densidade interna (coeficiente de aglomeração). Vimos ainda que alguns nós possuem grau elevado e que a maioria tem grau baixo, o que chamamos de propriedade livre de escala.

Agora queremos investigar talvez a mais famosa propriedade das redes complexas. Você já ouviu falar dos seis graus de separação? Provavelmente sim. Isso quer dizer que, mesmo que as redes complexas sejam esparsas, os caminhos nelas tendem a ser curtos. Vejamos a tabela abaixo, que mostra o tamanho médio dos caminhos (TMC) e a eficiência dos enlaces ($E(G)$) nas redes em estudo.

Rede	TMC	$E(G)$
Facebook	2,49	99,998%
Erdos	5,51	99,927%
Energia	18,99	99,712%
Proteína	5,61	99,808%

Observemos a rede Facebook. Imagine que você quisesse conhecer uma certa pessoa nesta rede e que para isso tivesse de ir conhecendo outros contatos até chegar na pessoa desejada. Um TMC de 2,4 significa que você precisa (em média) conhecer apenas 2 outras pessoas para chegar na pessoa desejada. Isso porque você só precisa ir a um amigo (distância de 1), ser introduzido a um amigo do seu amigo (distância de 2) e então chegar na pessoa desejada (distância de 3). Veja que eu arredondei para cima, o que é o pior caso. No melhor caso, bastaria pedir ao seu amigo.

Você não acha intrigante que em uma rede de mais de 3000 pessoas você precise de tão poucos saltos para chegar em outra pessoa? Mesmo considerando as redes com TMC maior, este resultado ainda é surpreendente. Veja a rede Energia, que tem o maior TMC. Seu valor ainda assim pode ser considerado baixo para uma rede com 4941 nós. Você observa isso pelo alto valor de $E(G)$ para esta rede e as demais.

Este é um resultado de grande importância para a ciência das redes, pois indica que as redes tendem a ser eficientes na forma como seus enlaces são alocados para encurtar distâncias. Este fenômeno de que os elementos das redes, a despeito de seu grande número, estão muito próximos entre si é chamado de efeito de mundo-pequeno (small-world effect).

Já vimos isso anteriormente quando estudamos o coeficiente de aglomeração nestas mesmas redes. Nós vimos que as redes complexas possuem comunidades e que estas comunidades têm muitos enlaces curtos (intra-grupo) e alguns enlaces longos (inter-grupos) e são estes enlaces que encurtam as distâncias. 

Além disso, é comum que estes enlaces levem aos (ou partam dos) nós mais bem conectados, isto é, aqueles nós de maior grau. Em outras palavras, estamos dizendo que o fato da rede ser livre de escala contribui para os pequenos caminhos na rede. Voltando a analogia dos amigos, as vezes você precisa conhecer aquele cara famoso/influente para ser introduzido a pessoa que deseja alcançar.

Mas, será que é sempre assim? Será que os nós mais influentes são aqueles que diminuem os caminhos sempre? Será que não existem nós que são aparentemente sem importância (grau baixo), mas que tem um papel fundamental nas redes? Se você já leu o artigo sobre intermediação, você já sabe do que estou falando.

A intermediação mede a importância de um nó para manter os menores caminhos na rede, quanto mais menores caminhos passam por um nó, maior é seu grau de intermediação. Abaixo temos uma tabela com os top-5 nós pelo nível de intermediação de cada um. Cada dupla $(i; bet_i)$ apresenta o identificador do nó $i$ com seu respectivo nível de intermediação $bet_i$.

Ordem	Facebook	Erdos	Energia	Proteína
1	(3755; 0,247)	(422; 0,066)	(4164; 0,288)	(1356; 0,181)
2	(2506; 0,028)	(420; 0,061)	(2543; 0,281)	(1400; 0,153)
3	(3521; 0,018)	(431; 0,060)	(1243; 0,280)	(1637; 0,110)
4	(38; 0,0177)	(177; 0,059)	(4219; 0,278)	(528; 0,066)
5	(2473; 0,008)	(343; 0,056)	(2528; 0,267)	(161; 0,043)

Vamos comparar esta tabela com o grau de cada nó. Para isso consulte a tabela dos top-5 nós de maior grau aqui. Abra o artigo em uma nova aba, caso queira compará-las. Em todo caso, nós identificamos (sublinhado) neste artigo, os nós que aparecem em alguma posição dos top-5 nós de maior grau.

Aqui vemos uma resposta para nossa indagação. E a resposta é que nem sempre um nó de grau alto é também um nó importante para os menores caminhos.

Na rede Facebook, por exemplo, vemos que todos os nós de maior grau são também os nós de maior intermediação. E isso ocorre porque o grau destes nós é muito elevado em proporção à rede. O nó 2473, o menor deles, tem grau 451 o que corresponde a mais de 11% dos nós da maior componente conectada (os dados sobre isso estão aqui). Temos um efeito similar, embora não tão proeminente, na rede Proteína. Nesta rede o nó com maior grau (nó 1356) se liga a mais de 5% dos nós da maior componente conectada e o quinto nó de maior grau (528) se liga a 2,7% dos nós da maior componente.

Veja que isso não acontece nas demais redes. Na rede Erdos o nó de maior grau se conecta a apenas 1,2% dos nós da maior componente conectada, alcançando ainda um terceiro lugar em termos de intermediação. Já na rede Energia o de maior grau se conecta a apenas 0,3%. Assim, vemos que é possível que outros nós tenham maior importância na intermediação dos caminhos da rede sem ter, necessariamente, grau elevado.

Com isso concluímos nosso estudo sobre algumas das propriedades muito famosas das redes complexas. Este estudo não pretendeu abranger todas as propriedades conhecidas, na realidade estamos muito longe de cobrir tudo. Propriedades como "os ricos andam juntos" ou "Hubs e autoridades" são algumas conhecidas e fazem parte do corpus de conhecimento da ciência das redes. 

E só falamos de propriedades topológicas! Existe toda uma gama de propriedades dos processos dinâmicos em redes complexas que ainda nem chegamos a arranhar. Resta muito a apresentar. Mas eu pretendo chegar lá e te convido a vir comigo.