Análise de Redes Complexas –
Conceitos e Propriedades Básicas
Ricardo Prudêncio
Redes Complexas
• Rede = conjunto de itens (vértices ou nós)
com conexões (arestas ou links) entre si
Tipos de Redes
• Redes Tecnológicas
– E.g., Internet, redes de transporte, redes de distribuição
• Redes Informacionais
– E.g., WWW, redes de citação, redes de preferência
• Redes Sociais
– E.g., Redes de amizade, redes de colaboração, redes de contato
sexual
• Redes Biológicas
– E.g., redes metabólicas, redes regulatórias de genes,
cadeia alimentar
Redes Complexas
- Representação
• Grafos: G(V,E)
Vértices:
v4
v3
v1
v2
V = {v1,v2,v3,v4,v5}
Arestas
E = {(v1,v2), (v2,v3), (v2,v5),
(v3,v4), (v3,v5)}
v5
Representação
• Grafos Direcionados
Vértices:
v4
v3
v1
V = {v1,v2,v3,v4,v5}
Arestas
v2
E = {(v1,v2), (v2,v3), (v2,v5),
(v3,v4), (v3,v4), (v3,v5)}
v5
E.g., Redes de influência,
Web, Twitter, redes de
citação, cadeia alimentar,
malha aérea,…
Representação
• Grafos com Pesos
Vértices:
2
5
v1
3
v3
v2
v4
V = {v1,v2,v3,v4,v5}
Arestas
2
1
v5
E = {(v1,v2,3), (v2,v3,5), (v2,v5,1),
(v3,v4,2), (v3,v5,2)}
Representação
• Grafos Multipartidos
Diferentes tipos de vértices e arestas
1
A
2
B
3
C
4
Pessoas
Instituições
Representação
• Matriz de Associação (Adjacência)
v4
v3
v1
v2
v5
v1 v2 v3 v4 v5
v1
0
1
0
0
0
v2
1 0
1
0
1
v3
0 1
0
1
1
v4
0 0
1
0
0
v5
0 1
1
0
0
Grafo não-direcionado = matriz simétrica
Representação
• Matriz de Associação
v4
v3
v1
v2
v5
v1 v2 v3 v4 v5
v1
0
1
0
0
0
v2
0 0
1
0
1
v3
0 0
0
1
1
v4
0 0
1
0
0
v5
0 0
0
0
0
Representação
• Matriz de Associação
5
v4
v3
1
v1
2
3
v2
4
7
v5
v1 v2 v3 v4 v5
v1
0
2
0
0
0
v2
0 0
1
0
7
v3
0 0
0
5
4
v4
0 0
3
0
0
v5
0 0
0
0
0
Representação
• Matriz de Adjacência
– Vantagens
• Muitas operações são bastante simples
– Desvantanges
• Desperdícios de memória, em especial para redes
esparsas
– Alternativa: Lista de Adjacência
Representação
• Lista de Adjacência
v4
v3
v1
v2
v5
v1
v2
v2
v1 v3 v5
v3
v2 v5 v4
v4
v3
v5
v2 v3
Representação
• Lista de Adjacência
Arestas de
saída
v4
v3
v1
v2
v5
Arestas de
entrada
v1
v2
v2
v3 v5
v1
v3
v5 v4
v2 v4
v4
v3
v3
v5
v2 v2
Propriedades
• Grau = Número de arestas do nó
v4
v3
v1
v2
v5
v1 v2 v3 v4 v5
v1
0
1
0
0
0
v2
1 0
1
0
1
v3
0 1
0
1
1
v4
0 0
1
0
0
v5
0 1
1
0
0
N
Grau do vértice vi
ki   A(i, j )
j 1
onde N = número total de nós
Propriedades
• Grau de entrada vs Grau de saída
v4
v1 v2 v3 v4 v5
v3
v1
v2
v5
N
k   A(i, j )
in
i
j 1
N
out
i
k
v1
0
1
0
0
0
v2
0 0
1
0
1
v3
0 0
0
1
1
v4
0 0
1
0
0
v5
0 0
0
0
0
  A( j, i )
j 1
Propriedades
• Distribuição do Grau
– Fração de vértices que possui determinado grau
Nk
fk 
N
Nk = número de vértices com grau igual a k
- Distribuição cumulativa complementar
Fk
k 1
Fk  1   f i
i 0
Probabilidade do grau ser maior ou igual a k
k
Propriedades
• Caminho geodésico
– Caminho mais curto entre dois nós
v4
v3
v1
v2
d1,4 = 3
v5
Propriedades
• Distância Média
– Média de todos as distâncias geodésicas
l
1
d
1
N ( N  1) i  j
2
ij
v4
v3
v1
v2
l = ???
v5
Propriedades
• Efeito de Mundo Pequeno
– Distância média é tipicamente pequena, mesmo
em redes muitos grandes
Ver Experimento de Milgran – 6 graus de separação
Ver Documentário “How Kevin Bacon Cured Cancer”
Propriedades
• Diâmetro
– Máximo das distâncias geodésicas
Diâmetro = 4
Diâmetro = ?
Propriedades
• Coeficiente de Clustering
– Qual a probabilidade de dois nós com um vizinho
em comum serem conectados?
B
A
?
Transitividade
C
Cc =
3 x número de triângulos da rede
número de triplas de vértices conectados
Propriedades
• Coeficiente de Clustering
– Exercício: calcule o cc da rede abaixo.
4
5
3
1
Cc =
3 x número de triângulos da rede
número de triplas de vértices conectados
2
Propriedades
• Estrutura de Comunidades
Ponte = laço fraco
Grupo 1
Grupo 2
Obs.: Grupo 2 é uma clique
Propriedades
• Componentes
Grafo com 13 vértices
- 3 Componentes
- Componente principal
(ou gigante) de tamanho 9
Material de Estudo
• - Introdução às redes complexas, por D.
Figueiredo
• - Structure and Function of Complex
Networks, by M. Newman