As complexas Redes
José Garcia Vivas Miranda


Redes Complexas
Conteúdo
• Era uma vez, na longínqua cidade de
Konigsberg...
• Teoria dos grafos
• Redes
• Redes complexas
• Caracterização
• Dinâmica em redes
• Prática
– Pajek

Histórico
Era uma vez, na longínqua
cidade de Konigsberg...
Grafos
Conceitos matemáticos.

Matemática
 Um grafo G(V,A) é definido pelo par de conjuntos V e A, onde:
V - os vértices ou nodos do grafo;
A - pares ordenados a=(v,w)  V: as arestas do grafo.
Seja, por exemplo, o grafo G(V,A) dado por:
V = { p | p é uma pessoa }
A = { (v,w) | < v é amigo de w > }
Exemplo:
V = { Maria, Pedro, Joana, Luiz }
A = { (Maria, Pedro) , (Joana, Maria) , (Pedro, Luiz) , (Joana, Pedro) }
relação simétrica : se <v é amigo
de w> então <w é amigo de v>.
As arestas que ligam os vértices
não possuem orientação
Dígrafos
Grafos orientados.

Matemática
Considere, agora, o grafo definido por:
V = { p | p é uma pessoa da família Castro }
A = { (v,w) | < v é pai/mãe de w > }
Um exemplo de deste grafo é:
V = { Emerson, Isadora, Renata, Antonio, Rosane, Cecília, Alfredo }
A = {(Isadora, Emerson), (Antonio, Renata), (Alfredo, Emerson), (Cecília,
Antonio), (Alfredo, Antonio)}
A relação não é simétrica pois se
<v é pai/mãe de w>, não é o caso de
<w é pai/mãe de v>.
O grafo acima é dito ser um grafo
orientado (ou digrafo).
 As conexões entre os vértices (ou
nós) são chamadas de arcos.
Representações
10
8
3
7

Concei tos
5
8
7
6
Ordem de um grafo

Concei tos
A ordem de um grafo G é dada pela cardinalidade do conjunto de nós, ou
seja, pelo número de vértices de G. Nos exemplos dados:
Ordem 4
Ordem 6
Adjacência
 Dois vértices v e w são adjacentes (ou vizinhos) se há uma aresta a=(v,w).
É o caso dos vértices Maria e Pedro em G1.
No caso do grafo ser dirigido (G2), a adjacência é especializada em:
Sucessor: w é sucessor de v se há um arco que parte de v e chega
em w. Ex.: em G2, Emerson e Antonio são sucessores de Alfredo.
Antecessor: v é antecessor de w se há um arco que parte de v e
chega em w. Em G2, Alfredo e Cecília são antecessores de Antonio.

Concei tos
G1
G2

Concei tos
Grau
O grau de um nó é dado pelo número de arestas que lhe são
incidentes. Em G1, por exemplo:
 grau(Pedro) = 3
 grau(Maria) = 2
 Para grafos dirigidos temos:
Grau de emissão: número de arcos que partem de v.
grauDeEmissão(Antonio) = 1
grauDeEmissao(Alfredo) = 2
grauDeEmissao(Renata) = 0
Grau de recepção: número de arcos que chegam a v.
grauDeRecepção(Antonio) = 2
grauDeRecepção(Alfredo) = 0
grauDeRecepção(Renata) = 1
G1
G2
Fonte
Um nó v é uma fonte se
grauDeRecepção(v) = 0.
É o caso dos vértices Isadora, Alfredo e Cecília em G2.

Concei tos
G2
Sumidouro
Um vértice v é um sumidouro se
grauDeEmissão(v) = 0.
É o caso dos vértices Renata e Emerson em G2.

Concei tos
G2
Laço

Concei tos
Um laço é uma aresta ou arco do tipo a=(v,v), ou seja,
que relaciona um vértice a ele próprio. Em G3 há três
ocorrências de laços para um grafo não orientado.
G3
Grafo regular

Concei tos
Um grafo é dito ser regular quando todos os seus
vértices tem o mesmo grau. O grafo G4, por exemplo, é
dito ser um grafo regular-3 pois todos os seus vértices
tem grau 3.
G4:
Grafo Completo

Concei tos
 Quando há uma aresta entre cada par de seus vértices.
Estes grafos são designados por Kn, onde n é a ordem do
grafo.
 Um grafo Kn possui o número máximo possível de
arestas para um dados n. Ele é, também regular-(n-1) pois
todos os seus vértices tem grau n-1.
Grafo Ponderado
 Um grafo G(V,A) é ponderado quando existe uma
funções relacionando V e/ou A com um conjunto de
números. Ex.:
V = {v | v é um bairro}
A = {(v,w,t) | <há linha de ônibus ligando v a w,
sendo t o tempo esperado de viagem>

Concei tos
Lapa
60
Itinga
50
Ribeira
120
30
40
Pituba
Cadeia

Concei tos
 É uma seqüência de arestas adjacentes que ligam dois
vértices. Para grafos orientados se ignora o sentido dos
arcos
A seqüência (x6, x5, x4, x1) é uma cadeia em G5.
 elementar se não passa duas vezes pelo mesmo nó.
 simples se não passa duas vezes pela mesma aresta.
 comprimento de uma cadeia é o número de arestas
(arcos) que a compõe.
G5:
Caminho
 Um caminho é uma cadeia na qual todos os arcos
possuem a mesma orientação. Aplica-se, portanto, somente
a grafos orientados.
Os nós (x1, x2, x5, x6, x3) é um exemplo de
caminho em G5.

Concei tos
G5:
Grafo Conexo : G é conexo se para todo par x,y
de vértices existe um caminho que liga x a y.
Matriz de adjacência
A
B
D

Concei tos
C
A
B
C
D
A
0
0
1
0
B
1
0
1
1
C
0
1
0
0
D
0
0
0
0
Sumidouro
Como seria
uma fonte?
Fechamento de trânsito

Concei tos
 Considerando um dígrafo não ponderado a expressão lógica:
adj[i][k] && adj[k][j]
será TRUE se e somente se existe um arco entre i e j passando por
k.
 A expressão
adj[i][0] && adj[0][j] || adj[i][1] && adj[1][j] || ...
será TRUE se e somente se existir um caminho de
comprimento 2 do no i ao j passando por 0, ou 1, ou 2, ou 3...
Existe uma matriz ajd2 chamada de
matriz de caminhos de comprimento
2.
ajd2 é o produto booleano de adj com
ela mesma.
A
B
C
D
Fechamento de trânsito
exemplo
A
B
D
C

Concei tos
A
B
A
B
C
D
0
0
1
0
1
0
1
B
C
D
A
0
1
0
0
B
0
1
0
0
C
1
0
1
1
D
0
0
0
0
1
C
0
1
0
0
D
0
0
0
0
Matriz adj
A
Matriz adj2
Fechamento de trânsito
Matriz path
 Matriz path é a matriz que assummirá TRUE se e somente se
existir um caminho, de qualquer tamanho, entre i e j.
Evidentemente:
path[i][j]=adj[i][j] || adj2[i][j] || adj3[i][j] || ... || adjn[i][j]
Onde n é o numero de nós do grafo.
A

Concei tos
A
B
C
D
B
C
Código no Tenembaum
D
A
1
1
1
1
B
1
1
1
1
C
1
1
1
1
D
0
0
0
0
Matriz path, ou fechamento de
trânsito de adj.
Matriz de vizinhança
A
B
C

Concei tos
A
B
C
D
D
A
B
C
D
A
1
1
1
1
A
3
2
1
3
B
1
1
1
1
B
1
2
1
1
C
1
1
1
1
C
2
1
2
2
D
0
0
0
0
D
0
0
0
0
Fechamento de trânsito
Algoritmo de WARSHALL

 Definir pathk de forma que pathk[i][j] será TRUE se e somente se existir um
caminho entre i e j que não passe por nenhum nó com numeração acima de k.
 pathk+1 será TRUE se e somente se:
 pathk [i][j]=TRUE
pathk[i][k+1]= TRUE e pathk[k+1][j]=TRUE
FecTra(int adj[][MAXNO],int path[][MAXNO])
{
int i,j,k;
for(i=0;i<MAXNO;++i)
for(j=0;j<MAXNO;++j)
path[i][j]=adj[i][j];
for(k=0;k<MAXNO;++k)
for(i=0;i<MAXNO;++i)
if(path[i][k])
for(j=0;j<MAXNO;++j)
path[i][j]=path[i][j] || path[k][j];
}

Redes Complexas
Alguns Conceitos Importantes
1.
Menor caminho médio: L = comprimento médio do menor caminho entre nós
# de ligações entre os vizinhos de um nós
2.
Coeficiente agregação: C =
# de ligações total possível entre esses vizinhos

Índices
Se A é amigo de B e de C,
então existe a probabilidade
de B ser amigo de C.
C=0
3.
C=1
Conectividade dos nós:
k = número de ligações existentes nesse nós (grau)
1
2
1
1
5
1
3
Distribuição de Graus

P(k)
Índices
k=5
1 2
3 4
k
...
270
Tipos de Redes

Redes Aleatórias
Redes de Mundo Pequeno Redes Livres de Escala
(Small World)
Grafos aleatórios

Paul Erdös
(1913-1996)
Alfréd Rényi
(1921-1970)
Publications Mathematicae, 6 (1959) 290.
Grafos aleatórios
Modelo de Erdös e Rényi
Dada uma probabilidade p e N vértices, são adicionadas arestas de forma aleatória.
Para cada uma das p(N(N-1))/2 arestas possíveis..
...se sorteiam um par de vértices
... caso não exista uma aresta entre os vértices
... Sorteia-se um número q, caso q<p a aresta é adicionada para este par.
Este procedimento é feito para todas as p(N(N-1))/2 arestas do grafo.

Problemas:
Para probabilidades altas o algoritmo é
bastante lento!
Solução: Para p> ½ eliminar arestas.
Rede Erdös-Rényi (1960)
Ligar vértices com probabilidade, p e (N fixo)
p = 1/6
N = 10
k ~ 1,6
L ~ 1,3
C~0.15
Pál Erdös
(1913-1996)
Distribuição de Poisson

 Democrático
 Aleatório
Se N é grande e p é pequeno a distribuição é binomial.

Redes aleatórias
Redes aleatórias
Aglomeração médio

•
Em uma rede aleatória, a probabilidade de dois vértices vizinho de um vértice
arbritário se conectem é a mesma de que dois vértices quaisquer se conectem, ou
seja:
Redes aleatórias
Percolação
•

•
•
Qual a probabilidade crítica em que todos os nós da rede estão conectados em um
único aglomerado gigante?
O Limite de percolação infinita em redes equivale a N
Resultados de Erdös e Rényi:
Ver NETLOGO
Redes de mundo pequeno
Experimento de Stanley Milgram

 Famoso experimento do psicólogo social Stanley Milgram
(1967).
 160 cartas foram enviadas
a pessoas em Omaha
(Nebraska), com o pedido
de que elas reenviassem a
correspondência
a
conhecidos que pudessem
fazê-la chegar mais perto
do destinatário alvo: um
corretor de valores em
Boston (Massachusetts).


O Mundo é Pequeno!!!
No fim do experimento, Milgram descobriu que as cartas que chegaram ao
destino passaram por seis pessoas (em média).

Rede small-world (WattsStrogatz, 1998)
Watts & Strogatz, Nature 393, 440(1998)
Fenômeno mundo pequeno
Diz-se que uma rede apresenta este tipo de comportamento quando a menor distância
média entre nós (vértices) variar com o logaritmo do tamanho do sistema (N), e o
coeficiente de aglomeração for grande comparado com o caso aleatório.
Rede
regular
Zona de
mundo pequeno

Rede
aleatória
Ver NETLOGO
Watts & Strogatz, Nature 393, 440(1998)
Redes Livre de Escala

R. Albert, H. Jeong,
A-L Barabasi,
Nature, 401 130
(1999).
Redes Livre de Escala
Iniciando com uma rede aleatória de tamanho mo muito menor que N
Cada passo é acrescentado um novo vértice na rede e m (m< mo)arestas que o
conectam com o resto da rede.
O mecanismo de conexão é dado pelo algoritmo de “preferential attachment” dada
pela probabilidade:

Após t passos a rede terá N=t+mo
vértices e mt+E(mo) arestas.
Distribuição de graus para diferentes
valores de mo.
Ver NETLOGO
Redes Livre de Escala

Muitas redes neturais exibem este
comportamento.
Idéia de “The rich get richer”
R. Albert, H. Jeong, A-L Barabasi, Nature, 401 130 (1999).
Robustez
Esquema de uma rede livre de escala. Um
ataque aos nodos a vermelho pode ser
drástico. O número destes pontos vitais
é baixo. Logo, no caso de falhas
aleatórias na maior parte dos casos são
atacados nodos verdes ou pretos.

Este tipo de fenómeno é válido tanto para a Internet,
como para reacções metabólicas ou redes de proteínas.

Falha

Ataque
Fractais e redes complexas

•
Muitas redes naturais exibem uma topologia do tipo Mundo pequeno ou Livre de
Escala.
C. Song, S. Havlin, and H. A. Makse, Nature (London) 433, 392 (2005).

Fractais e redes complexas
•
Sendo a rede Fractal, esta exibirá um comportamento em forma de lei de
potência.
•
Invariância na distribuição de
graus.
Agentes e redes complexas

Autômatos e redes complexas
Cronologia das Redes
Cronologia das Redes

Aplicações das redes
complexas
Redes de Chuva
Rede de estações meteorológicas.

4.6
4.4
outono verão
4.2
4.0
CMM
Aplicações
4.8
3.8
primavera
inverno
3.6
3.4
3.2
3.0
8.5
9.0
9.5
10.0
D
10.5
11.0
11.5
Redes de Chuva (Charles
Santana)

4.6
4.4
outono verão
4.2
4.0
CMM
Aplicações
4.8
3.8
primavera
inverno
3.6
3.4
3.2
3.0
8.5
9.0
9.5
10.0
D
10.5
11.0
11.5
Redes de migração (Fernanda
Regebe)
SAÍDAS
1000
 = -2,5

p(K)
Aplicações
100
10
1
1
10
K
100
Redes de tuberculose (Alex e

Aplicações
Helder Santana)
•
Levantamento da rede social de lugares
comuns.
•
Elaboração de um modelo de agentes
autônomos sobre uma rede complexa.
•
Matriz de probabilidade de contágio!
Rede de acesso a internet
(Helder Santana)
•
Rede de acesso ao servidor UFBA
1000
=2.34
P(k)
100

# caminhos mais prováveis
Aplicações
10
1
100
1
10
100
k
10
1
0
10
20
30
profundidade dos caminhos
40
1000
Plasticidade Neural
•

Aplicações
•
•
O modelo
– Utilizando métodos da física estatística se constrói uma rede com propriedades complexas.
– Esta rede representa a rede de sinapses, onde o nó da rede é o neurônio e as arestas as
sinapses.
– Tarefa difícil é a de fazer com que a rede se estabilize.
Ver modelo funcionando
Um modelo similar está sendo feito para o aparelho psíquico.
Plasticidade Neural
Dec.P.At.=0.1%
-54.95
Dec.P.At.=0.1%
-65.20
Neur.Inib.
50%
10%

-65.10
Neur.Inib.
10%
50%
-55.05
-55.10
-55.15
-55.20
-55.25
-55.30
-55.35
0
40
80
120
160
200
Tempo (ms)
-65.05
-65.00
Dec.P.At.=0.1%
-64.95
20
-64.90
0
40
80
120
Tempo (ms)
160
200
Quant. Neurônios Ativados
Aplicações
Energia média (mV)
-65.15
Potencial Ativação Médio (mV)
-55.00
Neur.Inib.
10%
50%
15
10
5
0
0
40
80
120
Tempo (ms)
160
200
Redes semânticas
•
NORMAL
INTERNADO

Aplicações
S_12
S_11

Aplicações
Matrizes de vizinhança
Estudos atuais

Aplicações
•
•
•
•
•
•
•
•
•
•
•
•
Esquizofrenia (ISC)
Dengue (ISC, Hugo Saba)
Tuberculose (ISC, Alex e Helder)
Agentes autônomos do mercado financeiro em redes complexas (Marcos, Banco
Central,UCC)
Redes de diferenciação celular (Viviane,UEFS)
Agentes em Células Tronco (Viviane,FioCruz)
Aparelho Psíquico de Freud (Jayme, CPPEV)
Redes de Neuroplasticidade (Nadja, CPPEV)
Redes de Chuva (Charles, UEFS)
Métodos teóricos (Matrizes de ordem superior)
Genoma (UEFS)
...

Referências
1.
2.

3.
S. Milgram, The Small World Problem, Psychology Today 1, 60-67 (1967).
S. N. Dorogovtsev, J. F. F. Mendes, Evolution of Networks,Advances in
Physics 51, 1079 (2002).
R. Albert, A-L. Barabási, Statistical mechanics of complex networks,
Reviews of Modern Physics 74, 47 (2002).
4.
http://ww.if.sc.usp.br/~pac
5.
http://sweet.ua.pt/~f2064/net.html
6.
http://www.nd.edu/~alb
O
b

d
r
i
a
o