Encontro 04: Suporte para Análise Espectral de Grafos

Este guia foi escrito para ajudar você a atingir os seguintes objetivos:

  • lembrar conceitos básicos de geometria analítica e álgebra linear;
  • explicar conceitos básicos de matriz de adjacência.

As seguintes bibliotecas serão usadas:


In [1]:
import numpy as np
import socnet as sn
import easyplot as ep


Terminologia e notação

  • Um escalar $\alpha \in \mathbb{R}$ é denotado por uma letra grega minúscula.
  • Um vetor $a \in \mathbb{R}^n$ é denotado por uma letra romana minúscula.
  • Uma matriz $A \in \mathbb{R}^{n \times m}$ é denotada por uma letra romana maiúscula.

Geometria analítica

  • Considere dois vetores, $a = (\alpha_0, \ldots, \alpha_{n-1})$ e $b = (\beta_0, \ldots, \beta_{n-1})$. O produto interno desses vetores é denotado por $a \cdot b$ e definido como $\sum^{n-1}_{i = 0} \alpha_i \beta_i$.

  • Dizemos que $a$ e $b$ são ortogonais se $a \cdot b = 0$.

  • A norma de $a$ é denotada por $\|a\|$ e definida como $\sqrt{a \cdot a}$, ou seja, $\sqrt{\sum^{n-1}_{i = 0} \alpha^2_i}$.

  • Dizemos que $a$ é um versor se $\|a\| = 1$.

  • Normalizar $a$ significa considerar o versor $\frac{a}{\|a\|}$.

Álgebra linear

  • Considere um conjunto de vetores $a_0, \ldots, a_{m-1}$. Uma combinação linear desses vetores é uma soma $\gamma_0 a_0 + \cdots + \gamma_{m-1} a_{m-1}$.

  • Dizemos que $a_0, \ldots, a_{m-1}$ é uma base se todo vetor em $\mathbb{R}^n$ é uma combinação linear desses vetores.

  • Considere uma matriz $A$. Sua transposta é denotada por $A^t$ e definida como uma matriz tal que, para todo $i$ e $j$, o elemento na linha $i$ e coluna $j$ de $A$ é o elemento na linha $j$ e coluna $i$ de $A^t$.

  • Em multiplicações, um vetor é por padrão "de pé", ou seja, uma matriz com uma única coluna. Disso segue que o produto $Ab$ é uma combinação linear das colunas de $A$.

  • Como consequência, a transposta de um vetor é por padrão "deitada", ou seja, uma matriz com uma única linha. Disse segue que o produto $b^t A$ é a transposta de uma combinação linear das linhas de $A$.

Autovetores e autovalores

Considere um vetor $b$ e uma matriz $A$. Dizemos que $b$ é um autovetor de $A$ se existe $\lambda$ tal que

$$Ab = \lambda b.$$

Nesse caso, dizemos que $\lambda$ é o autovalor de $A$ correspondente a $b$.

Note que a multiplicação pela matriz pode mudar o módulo de um autovetor, mas não pode mudar sua direção. Essa interpretação geométrica permite visualizar um algoritmo surpreendentemente simples para obter um autovetor.


In [ ]:
from random import randint, uniform
from math import pi, cos, sin


NUM_PAIRS = 10
NUM_FRAMES = 10


# devolve um versor positivo aleatório
def random_pair():
    angle = uniform(0, pi / 2)

    return np.array([cos(angle), sin(angle)])


# devolve uma cor aleatória
def random_color():
    r = randint(0, 255)
    g = randint(0, 255)
    b = randint(0, 255)

    return (r, g, b)


# matriz da qual queremos descobrir um autovetor
A = np.array([
    [ 2, -1],
    [-1,  2]
])

# versores positivos e cores aleatórias
pairs = []
colors = []
for i in range(NUM_PAIRS):
    pairs.append(random_pair())
    colors.append(random_color())

frames = []

for i in range(NUM_FRAMES):
    frames.append(ep.frame_vectors(pairs, colors))

    # multiplica cada vetor por A
    pairs = [A.dot(pair) for pair in pairs]

ep.show_animation(frames, xrange=[-5, 5], yrange=[-5, 5])

Note que as multiplicações por $A$ fazem o módulo dos vetores aumentar indefinidamente, mas a direção converge. Para deixar isso mais claro, vamos normalizar depois de multiplicar.


In [ ]:
# normaliza um vetor
def normalize(a):
    return a / np.linalg.norm(a)


# versores positivos e cores aleatórias
pairs = []
colors = []
for i in range(NUM_PAIRS):
    pairs.append(random_pair())
    colors.append(random_color())

frames = []

for i in range(NUM_FRAMES):
    frames.append(ep.frame_vectors(pairs, colors))

    # multiplica cada vetor por A e normaliza
    pairs = [normalize(A.dot(pair)) for pair in pairs]

ep.show_animation(frames, xrange=[-1, 1], yrange=[-1, 1])

Portanto, o algoritmo converge para uma direção que a multiplicação por $A$ não pode mudar. Isso corresponde à definição de autovetor dada acima!

Cabe enfatizar, porém, que nem toda matriz garante convergência.

Matriz de adjacência

Considere um grafo $(N, E)$ e uma matriz $A \in \{0, 1\}^{|N| \times |N|}$. Denotando por $\alpha_{ij}$ o elemento na linha $i$ e coluna $j$, dizemos que $A$ é a matriz de adjacência do grafo $(N, E)$ se:

$$\textrm{supondo } (N, E) \textrm{ não-dirigido}, \alpha_{ij} = 1 \textrm{ se } \{i, j\} \in E \textrm{ e } \alpha_{ij} = 0 \textrm{ caso contrário};$$$$\textrm{supondo } (N, E) \textrm{ dirigido}, \alpha_{ij} = 1 \textrm{ se } (i, j) \in E \textrm{ e } \alpha_{ij} = 0 \textrm{ caso contrário}.$$

Vamos construir a matriz de adjacência de um grafo dos encontros anteriores.


In [ ]:
sn.graph_width = 320
sn.graph_height = 180

g = sn.load_graph('encontro02/3-bellman.gml', has_pos=True)

for n in g.nodes():
    g.node[n]['label'] = str(n)

sn.show_graph(g, nlab=True)

In [ ]:
matrix = sn.build_matrix(g)

print(matrix)

Exercício 1

Considerando um grafo não-dirigido, como encontrar vizinhos na matriz de adjacência? Há mais de uma maneira.

(sua resposta)

Exercício 2

Cite uma propriedade que matrizes de grafos não-dirigidos possuem, mas matrizes de grafos dirigidos não possuem.

(sua resposta)

Exercício 3

Considerando um grafo dirigido, como encontrar sucessores na matriz de adjacência?

(sua resposta)

Exercício 4

Considerando um grafo dirigido, como encontrar predecessores na matriz de adjacência?

(sua resposta)

Exercício 5

Se $A$ é a matriz de adjacência de um grafo não-dirigido, o que o produto $AA$ representa?

(sua resposta)

Exercício 6

Se $A$ é a matriz de adjacência de um grafo não-dirigido, o que o produto $AA^t$ representa?

(sua resposta)

Exercício 7

Se $A$ é a matriz de adjacência de um grafo dirigido, o que o produto $AA$ representa?

(sua resposta)

Exercício 8

Se $A$ é a matriz de adjacência de um grafo dirigido, o que o produto $AA^t$ representa?

(sua resposta)

Em encontros futuros, veremos como alguns dos conceitos das primeiras seções podem ser usados em análise de redes sociais.