Uma introdução matricial à TEORIA DOS
GRAFOS
IPRJ/UERJ
25 de junho de 2013
Lúcia Maria (IPRJ/UERJ)
GRAFOS
25 de junho de 2013
1 / 22
Definições arestas com pesos iguais
GRAFO
n nós (ou vértices) conectados (ou não) por m arcos (ou arestas).
Figura : Um exemplo de grafo:
G = (V , E), V = {1, 2, 3, 4, 5}, E = {{1, 2}, {2, 3}, {2, 4}, {3, 5}, {4, 5}}
GRAFOS SIMPLES → grafo sem laços e sem arestas múltiplas.
Lúcia Maria (IPRJ/UERJ)
GRAFOS
25 de junho de 2013
2 / 22
Definições arestas com pesos iguais
GRAFO ORIENTADO → cada aresta tem um ponto inicial e um ponto
final.
Figura : Um exemplo de grafo orientado:
G = (V , E), V = {1, 2, 3, 4}, E = {(1, 2), (2, 3), (3, 4)}
Lúcia Maria (IPRJ/UERJ)
GRAFOS
25 de junho de 2013
3 / 22
Definições arestas com pesos iguais
MATRIZ DE INCIDÊNCIA de um grafo orientado (A):
linha i → aresta i / coluna j → nó j
Aresta i:
Sai do nó j1 : linha i de A terá −1 na coluna j1
Chega no nó j2 : linha i de A terá +1 na coluna j2
Todas as outras posições serão completadas com zero.
Exemplo:



A=


Lúcia Maria (IPRJ/UERJ)

−1 +1 0
0
−1 0 +1 0 

−1 0
0 +1 

0
0 −1 +1 
0 +1 0 −1
GRAFOS
25 de junho de 2013
4 / 22
Definições arestas com pesos iguais
Qual a matriz de INCIDÊNCIA do grafo abaixo?
Lúcia Maria (IPRJ/UERJ)
GRAFOS
25 de junho de 2013
4 / 22
Definições arestas com pesos iguais
MATRIZ DE ADJACÊNCIA (W):
matriz n × n → linhas e colunas ⇔ nós do grafo
(W )ij = wij
nós i e j conectados ⇔ UM
nós i e j desconectados ⇔ ZERO


0 1 0 0
 1 1 0 1 

W =
 0 0 0 1 
0 1 1 0
GRAU DO NÓ i → número de arestas incidentes nesse nó.
MATRIZ GRAU DE UM GRAFO → cada (D)ii guarda o grau do nó i.


1 0 0 0
 0 3 0 0 

D=
 0 0 1 0 
0 0 0 2
Lúcia Maria (IPRJ/UERJ)
GRAFOS
25 de junho de 2013
5 / 22
Definições arestas com pesos iguais
MATRIZ LAPLACIANA (L) de um grafo → L = A> A, onde A é a matriz
de incidência de um grafo com n nós.


1 −1 0
0
 −1 2
0 −1 

L=
 0
0
1 −1 
0 −1 −1 2
OBS.: Com esta definição podemos provar que L = D − W , onde W é
a matriz de adjacência e D é a matriz grau do grafo.
Lúcia Maria (IPRJ/UERJ)
GRAFOS
25 de junho de 2013
6 / 22
Caso geral: arestas com pesos quaisquer
Definições para o caso mais geral
CASO GERAL
A cada aresta é atribuı́do um número real não negativo que será o seu
peso.
Na matriz de adjacência W o número 1 será substituı́do pelo peso
correspondente wij da aresta ligando os nós i e j.
Cada (D)ii = di será a soma dos pesos de todas as arestas incidentes
ao nó i.
(D)ii = di =
j=n
X
wij
j=1
Assim,
W → peso das arestas e
D → peso dos nós
Lúcia Maria (IPRJ/UERJ)
GRAFOS
25 de junho de 2013
7 / 22
Caso geral: arestas com pesos quaisquer
MATRIZ LAPLACIANA COM PESOS (L)
Para arestas com pesos iguais tı́nhamos: L = A> A ⇒ L = D − W
Para arestas com pesos quaisquer queremos:
L = A> CA ⇒ L = D − W
C → matriz diagonal de ordem m × m ( m é o número de arestas do
grafo!) tal que cada número positivo ckk > 0 guarda o peso wij da k
-ésima aresta que liga os nós i e j.
Note que antes a matriz C nada mais era que a matriz identidade!
Lúcia Maria (IPRJ/UERJ)
GRAFOS
25 de junho de 2013
8 / 22
Caso geral: arestas com pesos quaisquer
Quatro matrizes especiais
• Wn×n (Weight)→ adjacência (peso das arestas) - linhas e colunas
são os nós do grafo
• Dn×n (Degree)→ grau - matriz diagonal, di = (D)ii =
Pn
j=1 wij .
representa o grau do nó i (soma dos pesos das arestas ligadas a
ele).
• Ln×n → laplaciana, L = D − W .
• Pn×n → normalização de W , P = D −1 W
% L=D−W
W
−→ D
& P = D −1 W
Lúcia Maria (IPRJ/UERJ)
GRAFOS
25 de junho de 2013
9 / 22
Caso geral: arestas com pesos quaisquer
Vendo P de mais perto





P = D −1 W = 



Para cada linha i de P :
Pn
w11
d1
w21
d2
w12
d1
w22
d2
...
..
.
..
.
..
wn1
dn
wn2
dn
...
j=1 pij
=
...
wij
j=1 di
Pn
w1n
d1
w2n
d2
..
.
.
=
wnn
dn
di
di









= 1 ⇒ P 1 = 1.1.
Como Pv = λP v ⇒ Lv = λL Dv, onde λL = 1 − λP então L1 = 0.D 1.
Lúcia Maria (IPRJ/UERJ)
GRAFOS
25 de junho de 2013
10 / 22
Caso geral: arestas com pesos quaisquer
Um exemplo com grafo simples e conexo



W =





D=


Lúcia Maria (IPRJ/UERJ)
GRAFOS
0
1
0
0
0
1
0
2
1
0
0
2
0
0
3
0
1
0
0
1
0
0
3
1
0

1
0
0
0
0
0
4
0
0
0
0
0
5
0
0
0
0
0
2
0
0
0
0
0
4











25 de junho de 2013
11 / 22
Caso geral: arestas com pesos quaisquer
L e P para o exemplo anterior



L=





P=


Lúcia Maria (IPRJ/UERJ)
GRAFOS

1 −1 0
0
0
−1 4 −2 −1 0 

0 −2 5
0 −3 

0 −1 0
2 −1 
0
0 −3 −1 4

0
1
0
0
0
1/4 0 2/4 1/4 0 

0 2/5 0
0 3/5 

0 1/2 0
0 1/2 
0
0 3/4 1/4 0
25 de junho de 2013
12 / 22
Grafos e Markov
Cadeia de Markov
Matriz de transição de uma cadeia de Markov →
entradas não negativas e soma das linhas igual a um.
A matriz P = D −1 W é uma matriz de Markov.
• wij → peso da aresta ligando Xi com Xj (afinidade).
• Núcleo gaussiano: simetria, positividade.
• Todo autovalor de uma matriz de Markov é | λ |≤ 1.
• A matriz de transição de passo t é igual a matriz de transição de
passo 1 elevada a t-ésima potência.
W → processo de Markov → espectro → φ.
Lúcia Maria (IPRJ/UERJ)
GRAFOS
25 de junho de 2013
13 / 22
Grafos e Markov
Processo de Markov
Estados → nós do grafo.
Dinâmica → sair de qualquer estado Xi para outro Xj .
Probabilidade de transição → elementos da matriz P = D −1 W .
Maior a afinidade (wij ) entre os nós → maior a probabilidade de
transição entre eles.
P=D
−1
X1
X
2
W =
..
.
Xn
Lúcia Maria (IPRJ/UERJ)
X1
w11
d1
w21
d2
X2
w12
d1
w22
d2
..
.
...
...
...
..
.
Xn
w1n
d1
w2n
d2
wn1
dn
wn2
dn
...
wnn
dn
..
.
GRAFOS
..
.
25 de junho de 2013
14 / 22
Grafos e Markov
Um exemplo
2
2
2k
3k
w12 = exp( kX 1−X
); w13 = exp( kX 1−X
);
σ2
σ2
1 1
X1 =
1 1
0.9673 0.9511
X2 =
0.9285 0.9414
0.9611 0.9709
X3 =
0.9286 0.9869
Lúcia Maria (IPRJ/UERJ)
GRAFOS
2
3k
w23 = exp( kX 2−X
)
σ2
25 de junho de 2013
15 / 22
Grafos e Markov
Escolhi σ 2 = 0.012. Assim temos:


1.0000 0.3679 0.5294
W =  0.3679 1.0000 0.8116 
0.5294 0.8116 1.0000


1.8973
0
0

0
2.1795
0
D=
0
0
2.3410


0.5271 0.1939 0.2790
P = D −1 W =  0.1688 0.4588 0.3724 
0.2261 0.3467 0.4272
Lúcia Maria (IPRJ/UERJ)
GRAFOS
25 de junho de 2013
16 / 22
Grafos e Markov
Pt
=
(D −1 W )t

P1 = 

P2 = 

P3 = 

P4 = 

P5 = 
representa o estado do sistema no parâmetro t.

0.5271 0.1939 0.2790
0.1688 0.4588 0.3724 
0.2261 0.3467 0.4272

0.3736 0.2879 0.3385
0.2506 0.3724 0.3770 
0.2743 0.3510 0.3747

0.3221 0.3219 0.3560
0.2802 0.3502 0.3696 
0.2886 0.3441 0.3673

0.3046 0.3336 0.3618
0.2904 0.3431 0.3665 
0.2932 0.3412 0.3656

0.2987 0.3376 0.3638
0.2938 0.3408 0.3654 
0.2948 0.3401 0.3650
Lúcia Maria (IPRJ/UERJ)
GRAFOS
25 de junho de 2013
17 / 22
Grafos e Markov


0.2967 0.3389 0.3644
P 6 =  0.2950 0.3400 0.3650 
0.2953 0.3398 0.3649


0.2960 0.3394 0.3647
P 7 =  0.2954 0.3397 0.3648 
0.2955 0.3397 0.3648


0.2957 0.3395 0.3647
P 8 =  0.2956 0.3397 0.3648 
0.2956 0.3396 0.3648


0.2957 0.3396 0.3648
P 9 =  0.2956 0.3396 0.3648 
0.2956 0.3396 0.3648


0.2956 0.3396 0.3648
P 10 =  0.2956 0.3396 0.3648 
0.2956 0.3396 0.3648
Lúcia Maria (IPRJ/UERJ)
GRAFOS
25 de junho de 2013
18 / 22
Grafos e Markov
Processo de Markov e distância de difusão
pij =
wij
di
→ caminho aleatório - Xi para Xj - um passo.
P t = (D −1 W )t → aumenta para t passos (diferentes escalas).
pijt → probabilidade de transição de Xi para Xj em t passos.
Quanto maior t mais o processo incorpora a geometria dos dados.
Dt (Xi , Xj ) → taxa de conectividade entre Xi e Xj por caminhos de
comprimento t. Muitos caminhos → ”distância” pequena
v
uX t
(pir − pjrt )2
u
Dt (Xi , Xj ) = t
,
σr
Xr ∈X
onde σr =
Pndr
i=1
di
Lúcia Maria (IPRJ/UERJ)
→ densidade de grau do r-ésimo nó.
GRAFOS
25 de junho de 2013
19 / 22
Grafos e Markov
A chave do método
A aplicação de difusão φ deve preservar distâncias:
distância de difusão (Xi , Xj ) = distância euclidiana (φ(Xi ), φ(Xj )).
Como fazer?
e = D 1/2 PD −1/2 similar a P = D −1 W → mesmos autovalores.
P
e é simétrica → decomposição espectral.
Vantagem: P
P
Decomposição de P t = (D −1 W )t → pijt = k λtk vk (i)e>
k (j)
• λ, v → autovalores e autovetores à direita de P t
• e> → autovetores à esquerda de P t
• λ1 = 1 ≥ λ2 ≥ . . . ≥ λn .
Lúcia Maria (IPRJ/UERJ)
GRAFOS
25 de junho de 2013
20 / 22
Grafos e Markov
Distância e aplicação de difusão
Reescrevendo a distância de difusão entre Xi e Xj :
v
u n
uX
Dt (Xi , Xj ) = t
λ2t (vk (i) − vk (j))2 .
k
k=2
Famı́lia de aplicações de difusão que preservam distâncias:



φt : Xi 7→ 

Lúcia Maria (IPRJ/UERJ)
λt2 v2 (i)
λt3 v3 (i)
..
.
λtn vn (i)
GRAFOS





25 de junho de 2013
21 / 22
Grafos e Markov
Por quê φ?
n
X
2 1/2
Dt (Xi , Xj ) = (
λ2t
=k φt (Xi ) − φt (Xj ) k .
r (vr (i) − vr (j)) )
r =2
Como |λ| ≤ 1, se t grande ⇒ λtr insignificantes ⇒ k(t) pequeno.
Dt (Xi , Xj ) ∼
=(
k(t)
X
2 1/2
λ2t
=k φt (Xi ) − φt (Xj ) k
r (vr (i) − vr (j)) )
r =2
com



φt : Xi 7→ 

Lúcia Maria (IPRJ/UERJ)
λt2 v2 (i)
λt3 v3 (i)
..
.
λtk(t) vk(t) (i)
GRAFOS





25 de junho de 2013
22 / 22