In [1]:
import numpy as np
import socnet as sn
import easyplot as ep
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\|}$.
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$.
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.
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)
(sua resposta)
(sua resposta)
(sua resposta)
(sua resposta)
(sua resposta)
(sua resposta)
(sua resposta)
(sua resposta)
Em encontros futuros, veremos como alguns dos conceitos das primeiras seções podem ser usados em análise de redes sociais.