Correlação de graus

Predefinição:Ciência da RedeNo estudo de ciência das redes, assortatividade ou correlação de graus é uma propriedade estrutural amplamente observada em redes do mundo real. A correlação de graus indica a relação entre os nós de uma rede, e é frequentemente definido como o coeficiente de correlação de Pearson^[1]

Topologias de rede devido a correlação de graus

A partir do cálculo da correlação dos graus da rede estudada, é possível observar até três tipos de topologias diferentes, que irão impactar na forma como hubs (nós fortemente vinculados) se comportam na rede.

Rede Neutra (Neutral Network)

Em redes neutras, os hubs não possuem tendências a se conectar entre si e nem com nós de baixo grau, ao invés disso, possuem um número aleatório de arestas entre si. A rede elétrica é um exemplo de rede neutra. Nesse tipo de rede, a probabilidade de se ter uma aresta entre um nó com grau $k$ e $k^{'}$ , pode ser calculada a partir de:

$P_{k, k^{'}} = \frac{k k^{'}}{2 L}$

onde $L$ é o número de links (arestas) na rede.

Rede Assortativa (Assortative Network)

Em redes assortativas, os hubs tendem a se conectar entre si, evitando nós com grau baixo. Ao mesmo tempo, nós com grau baixo tendem a se conectar entre si. Redes sociais são exemplos de redes deste tipo.

Rede Dissassortativa (Disassortative Network)

Em redes dissassortativas, os hubs tendem a se conectar com nós de baixo grau. Um exemplo de rede deste tipo é a rede formada pelo mapa de interações de proteínas de fermento.

Formas de quantificar a correlação de graus

Existem diversas formas de verificar a correlação de graus em uma rede, ela pode ser quantificada na forma de uma matriz, função ou até mesmo um único número.

Matriz de correlação de graus

Uma das formas de observar a correlação de graus em uma rede é através da visualização da matriz de correção de graus $e$ ^[2]. Nesta matriz, cada elemento $e_{i j}$ representa a probabilidade de se selecionar uma aresta aleatória, e nesta aresta encontrar um nó de grau $i$ em uma ponta, e grau $j$ na outra ponta.

Predefinição:Multiple image

Função de correlação de graus

Uma outra forma de observar a correlação de graus, é através da função de correlação de graus, a qual oferece uma forma mais simples de verificar a correlação em uma rede. Essa função pode ser calculada para todos os nós com grau $k$ , a partir de:

$k_{n n} (k) = \sum_{k^{'}} k^{'} P (k^{'} | k)$

onde $P (k^{'} | k)$ é a probabilidade condicional de que seguindo uma aresta de um nó com grau $k$ , encontraremos um nó com grau $k^{'}$ .

Em redes neutras, o gráfico de $k_{n n} (k)$ deve resultar em uma linha horizontal;
Em redes assortativas, o gráfico de $k_{n n} (k)$ aumenta conforme o grau k vai aumentando;
Em redes dissassortativas, o gráfico de $k_{n n} (k)$ diminui conforme o grau k vai aumentando.

Predefinição:Multiple image

Podemos também aproximar a função de correlação de graus, escrevendo-a da seguinte forma:

$k_{n n} (k) = a k^{μ}$

onde $a$ é a amplitude, e $μ$ é o expoente de correlação. Utilizando essa aproximação, podemos verificar a correlação de graus a partir de $μ$ :

Se $μ > 0$ , a rede é assortativa;
Se $μ = 0$ , a rede é neutra;
Se $μ < 0$ , a rede é dissassortativa.

Coeficiente de correlação de graus

Também é possível determinar correlação de graus utilizando um único número, para tal, podemos usar o coeficiente de correlação de graus, proposto por Mark Newman^[3], e que pode ser definido como:

$r = \sum_{j k} \frac{j k (e_{j k} - q_{j} q_{k})}{σ^{2}}$

Sendo:

$σ^{2} = \sum_{k} k^{2} q_{k} - [\sum_{k} k q_{k}]^{2}$

$q_{k} = \frac{k p_{k}}{⟨ k ⟩}$

onde $p_{k}$ é probabilidade de se encontrar um nó com grau $k$ na rede, $⟨ k ⟩$ é o grau médio dos nós da rede e $e_{j k}$ é calculado da mesma forma que os elementos ( $e_{i j}$ ) da matriz de correlação $e$ .

O coeficiente de correlação $r$ é um valor que está sempre no intervalo $[- 1, 1]$ . De forma mais prática, assim como proposto por Newman^[3], podemos reescrever a equação do coeficiente de correlação $r$ como:

$r = \frac{M^{- 1} \sum_{i} j_{i} k_{i} - {[M^{- 1} \sum_{i} \frac{1}{2} (j_{i} + k_{i})]}^{2}}{M^{- 1} \sum_{i} \frac{1}{2} ({j_{i}}^{2} + {k_{i}}^{2}) - {[M^{- 1} \sum_{i} \frac{1}{2} (j_{i} + k_{i})]}^{2}}$

onde $j_{i}$ , $k_{i}$ são os graus dos nós nas pontas da i-ésima aresta da rede. Utilizando $r$ , podemos verificar a correlação de graus de acordo com o sinal do valor encontrado:

Se $r > 0$ , a rede é assortativa;
Se $r = 0$ , a rede é neutra;
Se $r < 0$ , a rede é dissassortativa.