No artigo anterior, iniciamos um experimento para estudar as propriedades de quatro redes complexas que são encontradas na literatura e cujos dados são publicamente disponíveis. São elas: Facebook, Erdos, Energia e Proteína. Ao final do artigo conseguimos perceber que as redes complexas são, de forma geral, esparsas. Neste segundo artigo da série, vamos dar sequência ao estudo, nos aprofundando em outra propriedade das redes.
A tabela abaixo mostra algumas medidas associadas ao grau dos nós na rede como o grau médio ($\lambda$) e o grau do Hub ($d_{max}$). Vemos ainda uma medida ($P(d_i<\lambda)$) que indica o percentual dos nós cujo grau é menor do que o grau médio e uma outro medida ($P(d_i>\lambda+3\sigma)$) que indica o percentual dos nós com grau acima da média mais 3 desvios-padrão. Esta última medida serve para identificarmos qual a porção da rede possui grau elevado.
As redes complexas tendem a possuir uma forte assimetria na distribuição do grau de seus nós, fazendo com que haja muitos nós com grau baixo, tal como ocorre nas redes em estudo, em que o grau médio é próximo de 3 (um nó típico está conectado a 3 outros nós). A rede Facebook, novamente, difere das demais (grau médio é 23 vezes maior do que nas demais redes), mas isso é esperado devido à maior densidade desta rede. Observe que, ainda assim, a maior parte dos nós (60%) tem grau menor do que a média, tal como ocorre nas demais redes.
Uma outra característica que acompanha a anterior é que existem alguns poucos nós com grau muito elevado, i.e., grau muitas vezes (nessas redes são de 4 a 30 vezes) maior que a média. De modo geral, menos de 4% dos nós nas redes estudadas tem grau muito elevado. Para ter noção de quanto o grau pode ser grande, observe que na rede Facebook o Hub possui conexões com metade dos nós da rede ($n$ da rede Facebook é 3.898)!
A tabela abaixo ajuda a entender este conceito por outra perspectiva. Ela mostra, para cada rede, os cinco nós com maior grau. Cada dupla $(i, d_i)$ apresenta o identificador do nó $i$ com seu respectivo grau $d_i$. Observe que identificadores numéricos são comumente usados em dados públicos, para anonimizar aquilo que eles significam de verdade.
Observe que entre o Hub e o quinto nó de uma mesma rede há uma diferença significativa no grau, que pode chegar à metade (como ocorre na rede Proteína) ou a um quarto (rede Facebook). Isso ilustra a forte disparidade que existe entre os nós na rede em termos de sua importância estrutural. Nas redes sociais isso indica por exemplo a fama ou popularidade de um nó. Já na rede de energia o Hub indica um nó que geralmente é bastante central do ponto de vista geográfico (infelizmente não tenho o mapa das correspondências dos nós para verificar isso). No caso da rede Proteínas o Hub indica aquelas proteínas que tem importante papel na atividade metabólica.
Esta disparidade na distribuição do grau dos nós ficou conhecida na literatura como propriedade livre de escala (scale-free), termo primeiramente definido por Barabási e Albert no artigo Emergence of Scaling in Random Networks publicado em 1999. E as redes que apresentam esta propriedade são chamadas, por extensão do termo, redes livre de escala.
Para ser um pouco mais formal, esta característica de disparidade no grau dos nós pode ser descrita considerando que em redes livre de escala a probabilidade de que o grau do nó seja $k$ decai como uma lei de potência $P(d_i = k) \sim k^{-\alpha}$. Desta forma, pode-se definir que
Uma rede livre de escala é uma rede cuja distribuição do grau segue uma lei de potência.
Os gráficos abaixo mostram a distribuição do grau para cada uma das redes em estudo bem como a distribuição de lei de potência associada a cada uma delas. Os gráficos são exibidos em escala log-log, de modo que a lei de potência seja uma reta decrescente ($\log{P(d_i = k)} \sim -\alpha*\log{k}$). No título de cada gráfico são informados o $\alpha$ estimado em cada caso. Como se pode observar, a cauda destas distribuições segue a lei de potência, portanto estas são consideradas redes livre de escala.
Distribuição do grau e lei de potência
Como vimos neste artigo, redes complexas reais são livres de escala. E este fato tem diversas implicações para o funcionamento de processos dinâmicos em redes. Chamamos de processos dinâmicos a qualquer tipo de interação que ocorre em redes complexas ao longo do tempo. Questões como espalhamento de informação, robustez da rede à falhas, sincronização e controle e outros tipos de processos dinâmicos são fortemente impactadas pela distribuição do grau.
Considere processos de falha na rede, por exemplo. Neste tipo de processo, um nó é removidos da rede (segundo algum critério) juntamente com suas arestas, e vemos quantos nós ainda permanecem conectados na maior componente conectada deste grafo. Um critério de remoção, chamado falha, cada nó pode ser removido com mesma probabilidade. Em outro, chamado ataque, escolhemos como alvos nós com maior grau.
Se pensarmos um pouco, veremos que redes livre de escala serão pouco impactadas por falhas e muito impactadas por ataques. Ainda falaremos mais sobre isso em outro momento. Agora basta dizer que este foi objeto de estudo do artigo de Error and attack tolerance of complex networks de Albert, Jeong e Barabási em 2000 e que é só um dos resultados onde a propriedade de ser livre de escala impacta quando falamos sobre processos dinâmicos em redes complexas.
Na próxima parte desta série investigaremos outras propriedades das redes complexas em estudo.
Comentários
Postar um comentário