Assortatividade

Ciência da Rede
Teoria
Grafo Rede complexa Contágio Redes de pequeno mundo Scale-free Estrutura comunitária Percolação Evolução Difusão de inovações (redes sociais) Controlabilidade Desenho grafo Capital social Análise de links Otimização Reciprocidade Transitividade Ligação preferencial Teoria do equilíbrio Efeito de rede Influência social
Tipos de Rede
Rede de computadores Telecomunicação Rede social Neural Artificial Interdependente Semântico Dependência Fluxo
Grafos
Caraterísticas Clique Componente Corte Ciclo Estrutura de dados Aresta Laço Vizinhança Caminho Vértice Lista de adjacência / matriz Incidência Lista / matrix Tipos Grafo bipartido Grafo completo Grafo orientado Hipergrafo Multigrafo Aleatórios Ponderado
Métricas & Algoritmos
Centralidade Grau Betweenness Proximidade PageRank Clustering Centralidades Baseadas na Dissimilaridades Distribuição de Graus Correlação de Graus Assortatividade Distância Modularidade
Modelos
Grafo Aleatório Erdös–Rényi Barabási–Albert Watts–Strogatz Exponencial Aleatório (ERGM) Epidemia Hierárquica
Categorias
Teoria dos grafos Teoria das redes complexas

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).