Assortatividade

Na área de grafos e ciência das redes, assortatividade é uma métrica utilizada para quantificar a tendência de nós individuais se conectarem a outros nós semelhantes um grafo (homofilia). Além disso, é capaz de definir o comportamento dinâmico de uma rede, bem como a sua robustez, analisando o seu grau de assortatividade.

É possível analisar a correlação dos graus de uma rede analisando, por exemplo, uma rede social. Nesta é possível visualizar que os nós tendem a se conectar a outros nós com graus semelhantes, ou seja, características semelhantes. Esta característica é conhecida como assortatividade. Por outro lado, quando nós de alto grau se conectam com nós de baixo grau, dizemos que esta rede é dissassortativa. Por fim, caso a rede não apresente uma tendência clara de conexão, ela apresenta a característica não-assortativa.

Algoritmo

A assortatividade de uma rede é comumente computado por meio da correlação entre nós. Existem diversas formas de se calcular esta correlação, entretanto a mais utilizada é o coeficiente de correlação de graus.

Coeficiente de correlação de graus

Assortatividade de graus. (a) grafo disassortativo, (b) grafo assortativo

O coeficiente de correlação de graus é um número que é quantificado pelo coeficiente de correlação de Pearson, r, que caracteriza a correlação de ambos os nós das extremidade de uma aresta. Este valor varia entre o intervalo [-1 ≤ r ≤ 1] e apresenta as seguintes características: Se r = 0, a rede é não-assortativa (neutra); Se r < 0, então a rede é dissassortativa; e se r > 0, então a rede é assortativa. Além disso, quando o valor de r se encontra nos limites do intervalo, diz-se então que a rede é perfeitamente assortativa (r = 1) ou completamente disassortativa (r = -1).

O valor de r, definido por Mark Newman , pode ser calculado a partir da seguinte expressão:

$r={\frac {\sum _{jk}jk(e_{jk}-q_{j}q_{k})}{\sigma ^{2}}}$ (1),

onde

$\sigma ^{2}=\sum _{k}k^{2}q_{k}-{\bigg [}\sum _{k}kq_{k}{\bigg ]}^{2}$ e

$q_{k}={\frac {kp_{k}}{\langle k\rangle }}$, sabendo que $\langle k\rangle$ é o valor médio de $k$.

Da expressão (1), pode-se observar que $q_{k}$ é a probabilidade de se obter um nó de grau $k$ no fim de uma aresta selecionada aleatoriamente. Por fim, $e_{jk}$ é a matriz de correlação de graus ou a probabilidade de se encontrar um nó de grau $j$ que possui um nó de grau $k$ no fim de suas arestas. Como se trata de uma probabilidade, temos $\sum _{j,k}e_{jk}=1$ que pode se conectar a $q_{k}$ por meio de $\sum _{j}e_{jk}=q_{k}$.

Função de correlação de graus

Assortatividade baseado na correlação de graus. (a): Assortativo, (b): Neutro, (c) Disassortativo

Existe ainda uma outra maneira de se quantificar a correlação de graus de uma rede: a função de correlação de graus. Esta função calcula a correlação de graus para todos os nós de grau $k$ existentes. Para isto, uma maneira de de quantificar a magnitude dos nós que se conectam entre si, é explorar o grau médio dos vizinhos de um nó $i$ com grau $k$, em outras palavras, calcular o valor de $k_{nn}$, definido por:

$k_{nn}(k)=\sum _{k'}k'P(k'|k)$,

onde $P(k'|k)$ é a probabilidade condicional em que uma aresta de um nó de grau $k$ alcance um nó de grau $k'$. Consequentemente, caso o valor da função cresça de acordo com o $k$, então a rede é assortativa. Por outro lado, se o valor da função diminui de acordo com o valor de $k$, então a rede é disassortativa. Por fim, pode-se concluir que, se a função não apresenta os comportamentos anteriores, então a rede é neutra.

Redes neutras possuem uma característica especial em relação ao valor de $k_{nn}$. Como o grau médio dos vizinhos de um nó independe de seu grau (aproximadamente igual para todo valor de k), pode ser calculado por meio da média global. Com isso, temos que:

$P(k'|k)={\frac {e_{kk'}}{\sum _{k'}e_{kk'}}}={\frac {e_{kk'}}{q_{k}}}={\frac {q_{k'}q_{k}}{q_{k}}}=q_{k'}$.

Substituindo em $k_{nn}$, pode-se observar que:

$k_{nn}(k)=\sum _{k'}k'_{q_{k'}}=\sum _{k'}k'{\frac {k'p(k')}{\langle k\rangle }}={\frac {\langle k^{2}\rangle }{\langle k\rangle }}\$,

onde "<>" indica média.

Aplicações

Existem diversas aplicações para o uso da assortatividade de uma rede. A medicina é uma das áreas que mais explora este conceito, visto que auxilia a entender o comportamento de uma população e como uma determinada patologia pode se espalhar nesta comunidade. Junto a isso, pode-se inferir como aplicar de forma efetiva um sistema de vacinação conforme os hábitos destes grupos. Ainda assim, pode-se observar outras áreas que abordam o conceito, o aplicando em, por exemplo, sistema de rede elétrica (quais os pontos demandam mais energia elétrica), redes colaborativas (identificação de pontos que precisam de reforço) e rede de sistemas metabólicos (qual é o efeito de um determinado fármaco no corpo).