Grau de um nó

Uma das formas de caracterizar redes complexas é pela quantidade de vizinhos que cada nó possui. Quantificar vizinhos nos permite medir a importância ou a popularidade de um nó na rede, quanto mais enlaces um nó possui, maior sua importância na rede, geralmente. 

Além disso, em redes complexas reais  é possível observar que os nós não possuem a mesma importância, havendo uns poucos nós com muitos vizinhos (em redes sociais, estes são os perfis de famosos, por exemplo) e a maior parte dos nós com poucos vizinhos (perfil das pessoas normais). 

Esta assimetria no número de vizinhos é uma das características mais marcantes das redes complexas e vamos voltar a falar dela em outro momento. Por enquanto, vamos conhecer melhor a métrica que captura esta importância, que é chamada de grau do nó.

O grau (degree, em inglês) de um nó é o número de enlaces que este nó possui. Tal medida é indicada por $d_i$ ou $k_i$, para o nó $i$. A título de exemplo, no grafo em linha representado abaixo temos que $d_0 = 2$ e $d_1 = d_2 = 1$.

Grafo em linha com 3 nós

Para digrafos temos duas medidas de grau: temos o grau de entrada e o grau de saída. O primeiro é dado pelo número de enlaces que chegam ao nó $i$ e é indicado por $d^{in}_i$, enquanto o segundo é dado pelo número de enlaces que partem do nó ($d^{out}_i$). Considerando o grafo abaixo, temos: $d^{out}_0 = 1$ e $d^{in}_0 = 1$; $d^{out}_1 = 1$ e $d^{in}_1 = 1$; $d^{out}_2 = 0$ e $d^{in}_2 = 2$; e $d^{out}_3 = 2$ e $d^{in}_3 = 0$.

Digrafo com 4 nós

Podemos ainda sumarizar as medidas dos graus dos nós de um grafo em duas importantes métricas: o grau médio do grafo e o Hub do grafo. O grau médio, indicado por $\lambda$, é a média aritmética dos graus de todos os nós do grafo. Já o Hub é o nó de um grafo que possui o maior grau, que representamos como $d_H$.

Podemos ainda definir a sequência de graus de um grafo como um vetor contendo o grau de cada nó, e a distribuição do grau dos nós de um grafo é dada por $P(d_i=k)=[h_0,h_1,h_2,...,h_{d_H}]$, onde $h_i$ é a fração dos nós com grau $0,1,2,\ldots,h_{d_H}$. A função $P(d_i = k)$ lê-se como a probabilidade do grau de um nó da rede ser igual à k. 

Assim, considerando o grafo de 3 nós, temos que o Hub é o nó $0$, $\lambda = 4/3$, a sequência dos graus é $[2,1,1]$ e $P(d_i=k)=[0,2/3,1/3]$. A posição zero da lista é o $P(d_i = 0)$, que tem valor $0$ (já que não temos nós com grau $0$); $P(d_i = 1) = \frac{2}{3}$ (2 dos 3 nós tem grau 1) e $P(d_i=2) = \frac{1}{3}$ (1 dos 3 nós tem grau 2).

O grafo a seguir (com $n=30$ e $m=30$) ilustra um caso com um número maior de nós, onde $\lambda=2$, $d_H=4$ e a distribuição do grau possuindo um pico em 2 (aproximadamente 70% dos nós tem grau 2).

                                       Grafo com 30 nós                              Distribuição do grau do grafo

Espero que tenha ficado claro, caso não tenha deixe um comentário com sua dúvida.