Distribuição de graus

No estudo de Grafos e Redes Complexas, o grau de um nó em uma rede é o número de conexões que esse nó tem com outros nós, e a Distribuição de Graus é a distribuição de probabilidade dos graus dos nós de toda a rede.

Definição

O grau de um nó em uma rede é o número de conexões que este nó faz com outros nós. As arestas de uma rede podem ser direcionadas (orientadas) ou não direcionadas. O primeiro caso ocorre quando a aresta de um nó do grafo aponta para outro nó com direção especificada. Já nas redes não direcionadas, as arestas não possuem orientação, permitindo fluxo nos dois sentidos ^[1]. Nas redes direcionadas, existem dois tipos de graus distintos: o grau de entrada, que é a quantidade de arestas orientadas para o nó, e o grau de saída, que é a quantidade de arestas orientadas no sentido de saída do nó. Nas redes não direcionadas, o grau de um nó é simplesmente o número de arestas conectadas ao nó.

A distribuição de graus ${\displaystyle P(k)}$ de uma rede é definida pela fração de nós na rede com grau ${\displaystyle k}$. Então, supondo que uma rede tenha ${\displaystyle n}$ nós e que tenha ${\displaystyle n_{k}}$ nós com grau ${\displaystyle k}$, temos ${\displaystyle P(k)={\frac {n_{k}}{n}}}$.

A distribuição de graus é uma peça fundamental para a modelagem de redes, pois através dela pode-se determinar, por exemplo, se uma rede é livre de escala ^[2] ou analisar a robustez ^[3] de uma rede.

Distribuições

É possível construir redes que se comportam como redes reais a partir da escolha da distribuição de graus. Vamos detalhar características de três distribuições ^[4] muito utilizadas: distribuição de Poisson, Exponencial e Lei de Potência (encontrada em redes Livres de Escala).

Poisson

A distribuição de Poisson é uma distribuição de probabilidade que consegue representar uma série de redes, sendo especialmente útil para as redes modeladas como grafo aleatório. Em um grafo aleatório (por exemplo, o modelo de Erdős-Rényi ^[5]), a distribuição de graus segue a distribuição binomial, porém em casos onde o número de nós da rede ${\displaystyle N}$ é muito maior que o grau médio da rede ${\displaystyle \langle k\rangle }$, pode-se aproximar a distribuição binomial com a distribuição de Poisson. Uma distribuição de graus seguindo um modelo de Poisson é descrita por:

${\displaystyle P(k)=e^{-\langle k\rangle }{\frac {{\langle k\rangle }^{k}}{k!}}}$, onde ${\displaystyle \langle k\rangle }$ é o grau médio da rede.

Redes reais, como a internet, redes sociais e redes biológicas raramente tem um comportamento de Poisson, pois esta distribuição tende a subestimar a frequência de nós com alto grau ^[6].

Exponencial

A distribuição de graus exponencial é encontrada em diversas redes reais ^[7]. Nos modelos exponenciais o grau máximo (${\displaystyle k_{max}}$) evolui lentamente com o tamanho da rede, guardando uma relação logarítmica de crescimento com relação à quantidade de nós (${\displaystyle N}$) da rede. Apesar disso, ainda exibe um crescimento de ${\displaystyle k_{max}}$ maior que os modelos de Poisson, ou seja, quanto maior a rede, maior o grau máximo dela, mesmo que o crescimento aqui seja logarítmico. Apesar de maior que os modelos de Poisson, o crescimento do grau máximo de um modelo exponencial não é tão grande quanto em redes modeladas como redes livres de escala.

O modelo exponencial de distribuição de graus pode ser escrito como:

${\displaystyle P(k)=Ce^{-\lambda k}}$

Lei de Potência (Redes Livres de Escala)

Diversos estudos sobre este modelo foram feitos e popularizados por Albert Barabási. Este tipo de distribuição representa bem um número muito elevado de redes, entre elas a internet. As redes modeladas como livres de escala possuem distribuição de graus que acompanha uma lei de potência:

${\displaystyle P(k)=Ck^{-\gamma }}$,

onde ${\displaystyle \gamma }$ é chamado de expoente da rede.

O valor de ${\displaystyle \gamma }$ vai depender de cada rede. Este parâmetro é importante para a determinação de algumas características de redes livres de escala. Este tipo de rede é a inspiração para o modelo de Barabási–Albert (BA), que produz redes livres de escala, com distribuição de lei de potência.

Referências

1. Barabási, Albert-László (28 de março de 2013). «Network science». Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences (em inglês) (1987). 20120375 páginas. doi:10.1098/rsta.2012.0375. Consultado em 15 de dezembro de 2020 
2. Barabási, Albert-László; Albert, Réka (15 de outubro de 1999). «Emergence of Scaling in Random Networks». Science (em inglês) (5439): 509–512. ISSN 0036-8075. doi:10.1126/science.286.5439.509. Consultado em 17 de dezembro de 2020 
3. Albert, Réka; Jeong, Hawoong; Barabási, Albert-László (julho de 2000). «Error and attack tolerance of complex networks». Nature (em inglês) (6794): 378–382. ISSN 1476-4687. doi:10.1038/35019019. Consultado em 17 de dezembro de 2020 
4. Hernandez-Lopez, Rogelio A. (2010). «Studying Complex Networks» (em inglês). Consultado em 17 de Dezembro de 2020 
5. Erdős, Paul; Rényi, Alfréd (1959). «On Random Graphs I». Publ. math. debrecen (em inglês): 290-297  |acessodata= requer |url= (ajuda)
6. Newman, M. E. J. (12 de fevereiro de 2002). «Random graphs as models of networks». arXiv:cond-mat/0202208 (em inglês). Consultado em 17 de dezembro de 2020 
7. Deng, Weibing; Li, Wei; Cai, Xu; Wang, Qiuping A. (15 de abril de 2011). «The exponential degree distribution in complex networks: Non-equilibrium network theory, numerical simulation and empirical data». Physica A: Statistical Mechanics and its Applications (em inglês) (8): 1481–1485. ISSN 0378-4371. doi:10.1016/j.physa.2010.12.029. Consultado em 18 de dezembro de 2020