Encontro 07: Simulação e Demonstração de Hub/Authority

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 Hub/Authority:



In [ ]:

    
k = 10

# inicializa arbitrariamente hubs
g.node[0]['h'] = 0
g.node[1]['h'] = 0
g.node[2]['h'] = 0
g.node[3]['h'] = 0

# inicializa arbitrariamente authorities
g.node[0]['a'] = 2
g.node[1]['a'] = 6
g.node[2]['a'] = 4
g.node[3]['a'] = 3

for _ in range(k):
    # atualiza hubs a partir de authorities
    for n in g.nodes():
        g.node[n]['h'] = sum([g.node[m]['a'] for m in g.successors(n)])

    # atualiza authorities a partir de hubs
    for n in g.nodes():
        g.node[n]['a'] = sum([g.node[m]['h'] for m in g.predecessors(n)])

# soma hubs
sh = sum([g.node[n]['h'] for n in g.nodes()])

# soma authorities
sa = sum([g.node[n]['a'] for n in g.nodes()])

# imprime hubs e authorities normalizados
for n in g.nodes():
    print('{}: hub {:04.2f}, authority {:04.2f}'.format(n, g.node[n]['h'] / sh, g.node[n]['a'] / sa))

Considere as seguintes definições:

$A$ é a matriz de adjacência de g;
$h^k$ é o vetor de hubs no final da iteração $k$;
$a^k$ é o vetor de authorities no final da iteração $k$.

Note que:

$h^k = Aa^{k-1}$;
$a^k = A^th^k$.

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



In [ ]:

    
k = 10

# constrói matriz de adjacência
A = sn.build_matrix(g)

# constrói matriz transposta
At = A.transpose()

# inicializa arbitrariamente hubs
h = np.array([[0], [0], [0], [0]])

# inicializa arbitrariamente authorities
a = np.array([[2], [6], [4], [3]])

for _ in range(k):
    # atualiza hubs a partir de authorities
    h = A.dot(a)

    # atualiza authorities a partir de hubs
    a = At.dot(h)

# soma hubs
sh = np.sum(h)

# soma authorities
sa = np.sum(a)

# imprime hubs e authorities normalizados
for n in g.nodes():
    print('{}: hub {:04.2f}, authority {:04.2f}'.format(n, h[n, 0] / sh, a[n, 0] / sa))

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

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

Para entender, vamos desenvolver as igualdades anteriores:

$h^k = Aa^{k-1} = AA^th^{k-1} = AA^tAa^{k-2} = AA^tAA^th^{k-2} = \cdots = (AA^t)^k a^0$;
$a^k = A^th^k = A^tAa^{k-1} = A^tAA^th^{k-1} = A^tAA^tAa^{k-2} = \cdots = (A^tA)^k a^0$.

Ou seja:

$h^k$ é o resultado de multiplicar $k$ vezes a matriz $AA^t$ pelo vetor de authorities inicial;
$a^k$ é o resultado de multiplicar $k$ vezes a matriz $A^tA$ pelo vetor de authorities inicial.

Vamos demonstrar que $h^k$ converge de alguma forma conforme $k$ cresce, desde que $a_0$ seja positivo.

Por simplicidade, vamos usar o seguinte teorema como caixa-preta: para toda matriz simétrica $n \times n$, existe um conjunto de $n$ autovetores dessa matriz que são versores mutuamente ortogonais e, portanto, uma base de $\mathbb{R}^n$.

Embora $A$ não seja simétrica, podemos observar que $AA^t$ é simétrica. Então sejam $e_0, \ldots, e_{n-1}$ os autovetores de $AA^t$ mencionados pelo teorema e sejam $\lambda_0, \ldots, \lambda_{n-1}$ os autovalores correspondentes. Como esses autovetores são uma base, então existem coeficientes $\gamma_0, \ldots, \gamma_{n-1}$ tais que:

$$a^0 = \gamma_0 e_0 + \cdots + \gamma_{n-1} e_{n-1}$$

Disso segue que:

$$h^k = (AA^t)^k a^0 = (AA^t)^k \gamma_0 e_0 + \cdots + (AA^t)^k \gamma_{n-1} e_{n-1} = \lambda^k_0 \gamma_0 e_0 + \cdots + \lambda^k_{n-1} \gamma_{n-1} e_{n-1}$$

Isso não parece convergir... De fato, sabemos que o módulo de $h^k$ pode não convergir, pois os hubs podem crescer indefinidamente.

Por outro lado, podemos demonstrar que a direção de $h^k$ converge. Considere uma versão escalada do cálculo de $h_k$, na qual o resultado é dividido por uma constante $\lambda$ após cada multiplicação.

$$\frac{h^k}{\lambda^k} = \frac{\lambda^k_0}{\lambda^k} \gamma_0 e_0 + \cdots + \frac{\lambda^k_{n-1}}{\lambda^k} \gamma_{n-1} e_{n-1} = \left(\frac{\lambda_0}{\lambda}\right)^k \gamma_0 e_0 + \cdots + \left(\frac{\lambda_{n-1}}{\lambda}\right)^k \gamma_{n-1} e_{n-1}$$

Se $\lambda$ for o maior valor absoluto dentre os autovalores, podemos observar que essa versão escalada converge.

A demonstração da convergência de $a^k$ é análoga.