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.
Comentários
Postar um comentário