Usuário(a):Rodrigo Araújo Marinho Franco/Testes

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

No 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

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 {kk'}{2L}}$

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$ . Nesta matriz, cada elemento $e_{ij}$ 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.

Matriz de correlação de graus de uma rede neutra.

Matriz de correlação de graus de uma rede assortativa.

Matriz de correlação de graus de uma rede dissassortativa.

Adaptação da imagem 7.3 do livro Network of Science de Albert-László Barabási

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_{nn}(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_{nn}(k)$ deve resultar em uma linha horizontal;
• Em redes assortativas, o gráfico de $k_{nn}(k)$ aumenta conforme o grau k vai aumentando;
• Em redes dissassortativas, o gráfico de $k_{nn}(k)$ diminui conforme o grau k vai diminuindo.

Gráfico da função de correlação de graus de uma rede assortativa.

Gráfico da função de correlação de graus de uma rede neutra.

Gráfico da função de correlação de grau de uma rede dissassortativa.

Adaptação da imagem 7.6 do livro Network of Science de Albert-László Barabási

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

$k_{nn}(k)=ak^{\mu }$

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

• Se $\mu >0$, a rede é assortativa;
• Se $\mu =0$, a rede é neutra;
• Se $\mu <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, e que pode ser definido como:

$r=\sum _{jk}{jk{\bigl (}e_{jk}-q_{j}q_{k}{\bigr )} \over \sigma ^{2}}$

Sendo:

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

$q_{k}={\frac {kp_{k}}{\langle k\rangle }}$

Onde $p_{k}$ é probabilidade de se encontrar um nó com grau $k$ na rede, $\langle k\rangle$ é o grau médio dos nós da rede e $e_{jk}$ é calculado da mesma forma que os elementos ($e_{ij}$) 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, podemos reescrever a equação do coeficiente de correlação $r$ como:

$r\ =\ {\frac {M^{-1}\sum _{i}{j_{i}k_{i}\ -\ \left[M^{-1}\sum _{i}{{\frac {1}{2}}\ \left(j_{i}\ +k_{i}\right)}\right]^{2}}}{M^{-1}\sum _{i}{{\frac {1}{2}}\left({j_{i}}^{2}\ +{k_{i}}^{2}\right)}-\ \left[M^{-1}\sum _{i}{{\frac {1}{2}}\ \left(j_{i}\ +k_{i}\right)}\right]^{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.

Correlação de graus no mundo real

A tabela abaixo apresenta o coeficiente de correlação de graus $r$, descrito na seção anterior, em diferentes tipos de redes.

Quantidade de nós $n$ e coeficiente de correlação de graus $r$ em diversas redes.

	Rede	$n$	$r$
Redes do mundo real	co-autoria de físicaa	52909	0,363
	co-autoria de biologiaa	1520251	0,127
	co-autoria de matemáticab	253339	0,120
	colaboração de atores de cinemac	449913	0,208
	Diretores de uma empresad	7673	0,276
	Internete	10697	-0,189
	World-Wide Webf	269504	-0,065
	Interações de Proteínasg	2115	-0,156
	Rede Neuralh	307	-0,163
Modelos	Rede Aleatóriau		0
	Barabási and Albertw		0

Nesta tabela, os indíces representam: (a) redes de colaboração científica de físicos, biólogos e (b) matemáticos ; (c) atores de filmes; (d) empresários; (e) conexões entre sistemas autônomos na internet; (f) hyperlinks não direcionados entre páginas da Web em um único domínio; (g) Interação proteína-proteína no fermento; (h) Conexões sinápticas não direcionadas e sem peso de um nematóide; (u) Rede aleatória produzida pelo modelo de Erdós and Rényi; (w) Modelo de Barabási e Albert com acoplamento preferencial.