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.

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.

É 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).

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].

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}}$

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.