# 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 $\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:
$P(k)=e^{-\langle k\rangle }{\frac {{\langle k\rangle }^{k}}{k!}}$, onde $\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.

### 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)=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:
$P(k)=Ck^{-\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.