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 . 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 $P(k)$ de uma rede é definida pela fração de nós na rede com grau $k$. Então, supondo que uma rede tenha $n$ nós e que tenha $n_k$ nós com grau $k$, temos $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 ou analisar a robustez 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 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 ), a distribuição de graus segue a distribuição binomial, porém em casos onde o número de nós da rede $N$ é muito maior que o grau médio da rede $⟨k⟩$, 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:

$P(k)=e^{-⟨k⟩}\frac{{⟨k⟩}^k}{k!}$, onde $⟨k⟩$ é 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 .

Exponencial

A distribuição de graus exponencial é encontrada em diversas redes reais . Nos modelos exponenciais o grau máximo ($k_{max}$) evolui lentamente com o tamanho da rede, guardando uma relação logarítmica de crescimento com relação à quantidade de nós ($N$) da rede. Apesar disso, ainda exibe um crescimento de $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:

$P(k)=C{e}^{-\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:

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

onde $\gamma$ é chamado de expoente da rede.

O valor de $\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.