Encontro 07: Simulação e Demonstração de PageRank

Importando as bibliotecas:



In [ ]:

    
import sys
sys.path.append('..')

import numpy as np
import socnet as sn

Configurando a biblioteca:



In [ ]:

    
sn.graph_width = 225
sn.graph_height = 225

Carregando o grafo:



In [ ]:

    
g = sn.load_graph('graph.gml', has_pos=True)

sn.show_graph(g)

Vamos fazer uma simulação de $k$ iterações do algoritmo PageRank:



In [ ]:

    
k = 10

scale = 0.8

residue = (1 - scale) / g.number_of_nodes()

# inicializa ranks

rank = 1 / g.number_of_nodes()

g.node[0]['r'] = rank
g.node[1]['r'] = rank
g.node[2]['r'] = rank
g.node[3]['r'] = rank

for _ in range(k):
    # calcula quanto cada nó recebe

    received = {n: 0 for n in g.nodes()}

    for n in g.nodes():
        sent = g.node[n]['r'] / len(g.successors(n))

        for m in g.successors(n):
            received[m] += sent

    # atualiza quanto cada nó tem, considerando escala e resíduo

    for n in g.nodes():
        g.node[n]['r'] = scale * received[n] + residue

# imprime ranks

for n in g.nodes():
    print('{}: rank {:04.2f}'.format(n, g.node[n]['r']))

Seja $(N, E)$ o grafo g e considere as seguintes definições:

$R \in \mathbb{R}^{|N| \times |N|}$ é uma matriz tal que, denotando por $\rho_{ij}$ o elemento na linha $i$ e coluna $j$, temos que $\rho_{ij} = \frac{1}{|\mathcal{S}(i)|}$ se $(i, j) \in E$ e $\rho_{ij} = 0$ caso contrário, lembrando que $|\mathcal{S}(i)|$ é o número de sucessores de $i$;
$s$ é o fator de escala;
$r$ é o resíduo, ou seja $\frac{1 - s}{|N|}$;
$\tilde{R}$ é a matriz obtida quando cada elemento de $R$ é multiplicado por $s$ e somado a $r$;
$r^k$ é o vetor de ranks na iteração $k$.

Note que:

$r^k = \tilde{R}^tr^{k-1}$.

Vamos fazer uma nova simulação de $k$ iterações do algoritmo PageRank, desta vez usando álgebra matricial:



In [ ]:

    
k = 10

scale = 0.8

residue = (1 - scale) / g.number_of_nodes()

# constrói matriz de atualização
R = sn.build_matrix(g)
for n in g.nodes():
    R[n,] /= np.sum(R[n,])
R = scale * R + residue

# constrói matriz transposta
Rt = R.transpose()

# inicializa ranks
rank = 1 / g.number_of_nodes()
r = np.array([[rank], [rank], [rank], [rank]])

for _ in range(k):
    r = Rt.dot(r)

# imprime ranks
for n in g.nodes():
    print('{}: rank {:04.2f}'.format(n, r[n, 0]))

Nas duas simulações, modifique o valor de $k$ e note que os valores de rank convergem.

Mas por que convergem? Tivemos sorte em relação à matriz? Tivemos sorte em relação aos valores iniciais?

Para entender, vamos desenvolver a igualdade anterior:

$r^k = \tilde{R}^tr^{k-1} = \tilde{R}^t\tilde{R}^tr^{k-1} = (\tilde{R}^t)^kr^0$.

Ou seja:

$r^k$ é o resultado de multiplicar $k$ vezes a matriz $\tilde{R}^t$ pelo vetor de ranks inicial.

Não vamos demonstrar que $r^k$ converge, mas o argumento baseia-se no Teorema de Perron-Frobenius, que garante convergência para um autovetor se a matriz for positiva. Não temos essa garantia em relação à matriz $R$, mas temos em relação a $\tilde{R}$.