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 [3]:
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 [4]:
# 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 [5]:
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 [6]:
matrix = sn.build_matrix(g)
print(matrix)
-
(sua resposta)
Em encontros futuros, veremos como alguns dos conceitos das primeiras seções podem ser usados em análise de redes sociais.