Random Walks - T2

Random Walks -  Trabalho 2

Fonte: http://www.mit.edu/~kardar/teaching/projects/chemotaxis(AndreaSchmidt)/random.htm

O objetivo deste trabalho é simular o processo de caminhadas aleatória em um grafo. Com isso, a intenção é ranquear os vértices mais visitados, ou seja, gerar a distribuição estacionária relativa ao grafo.

De forma simplista o processo das caminhadas aleatória se dá partindo de um vértice inicial, e aleatoriamente escolhe-se um vértice vizinho para ir em seguida. Cada vez que um vértice é visitado um contador, ou algum quantificador é usado para representar quais vértices foram mais visitados que outros. Estes quantificadores formam o que chamamos de estado estacionária do grafo, que na prática, nada mais que um vetor onde cada posição representa um vértice do gráfico conteúdo por exemplo a quantidade de vezes que o vértice foi visitado em relação ao total de vértices. É importante salientar que para uma caminhada aleatória em grafos não direcionados, a distribuição estacionária é única.

Este processo é uma das formas, bem simplificado, do que o Google utiliza para ranquear websites de acordo com sua importância no conjunto, neste caso a Internet.

• Materiais utilizados:

Para fazer a simulação da caminhada aleatória usamos a linguagem Python. No Windows, um software livre chamado Python(x,y), engloba uma série de bibliotecas e alguns ambientes de desenvolvimento. Spyder é um destes ambientes e foi utilizado para desenvolver o trabalho.

Na realidade, a utilização do Python(x,y) e o Spyder é opcional, do entanto esta IDE, possui uma boa ferramenta de Debug e um shell interpretador Python, IPython, e outras ferramentas útil que dão suporte ao desenvolvedor.

Para mais informações sobre a ferramenta, como instalar, consulte o link: https://code.google.com/p/pythonxy/ .

A escolha da linguagem Python se deu, sobretudo por possui uma biblioteca muito útil para manipular grafos: NetworkX. Para mais informação de como usar a biblioteca consulte: https://networkx.github.io/ .

A NetworkX não vem incluso nos pacotes instalados pelo Python(x,y), então uma alternativa é instalar o Setuptools, uma ferramenta que facilita a instalação, compilação, atualização e desinstalação de bibliotecas e pacotes Python, e através dele instalar o NetworkX. Para mais informação sobre a ferramenta acesse: https://pypi.python.org/pypi/setuptools .

• Grafo:

O grafo, US Politics books, utilizado neste trabalho é referente a compra de livros sobre política na Amazon.com. Os vértices representam os livros e as arestas representam quais livros foram comprados por um mesmo comprador. Por exemplo: um comprador que comprou a livro l1 também comprou o livro l2. Então haverá uma aresta interligando os vétices. Abaixo a figura 1, mostra um desenho esquemático do grafo:

Figura 1 - Grafo com mais de 100 vértices. Fonte: http://www.orgnet.com/ .

• Metodologia:

Neste trabalho realizaremos a caminhada aleatória, bem como o cálculo do estado estacionário, em três aspectos: a teórica, o power method, e a caminhada aleatória de fato. Apresentaremos o ranking dos vértices mais visitados em cada caso e faremos uma comparação dos resultados obtidos em cada abordagem.

• Desenvolvimento:

Nesta seção apresentaremos os resultados obtidos na execução de cada método da caminha aleatória assim como os procedimentos realizados para gerar cada caso.

o   A distribuição estacionária real ou teórica:

A distribuição estacionária real de cada vértice, no equilíbrio é dada por:

Wi = d(vi)/2*|E|, para todo Vi.

Onde Wi é a distribuição estacionária relativa ao vértice vi; d(vi) é o grau de vi, e |E| é o número total de arestas. W é um vetor formado por wi, com i variando de 0 até o número total de vértices do grafo.

Portanto, para calcular a distribuição estacionária teórica do grafo analisado neste trabalho (US politics book), precisamos saber o grau de cada vértice e o número total de arestas do grafo. Dessa forma iteramos em um for cada posição do vetor W, que terá o tamanho igual ao número total de vértices, e atribuímos a ela o grau do vértice dividido por duas vezes o número total de arestas, como na definição. O algoritmo, da figura 1, realiza o cálculo como o descrito acima:

Figura 2 - Algoritmo que realiza o calculo da distribuição estacionária teórica.

Neste código usamos a biblioteca NetworkX para fazemos a leitura do grafo. Logo em seguida na linha 10 criamos o vetor de distribuição estacionaria real: w_real. No for da linha 13, adicionamos a cada posição do vetor uma tupla (x,p), onde x é o número do vértice e p é a relação de visitas do vértice com o total de vértices do grafo, durante a caminhada aleatória.

No for em questão usamos alguns métodos disponibilizados pela biblioteca NetworkX, como o G.nodes() que retorna a lista de nós do grafo; G.degree(v) retorna o grau do vértice v, do grafo G, passado nos parâmetros; e G.number_of_edges() retorna o número total de arestas do grafo G. Com isso, em w_real já temos a distribuição estacionária real, no entanto, ainda precisamos gerar um rank dos 10 vértices mais visitados.

Para isso, na linha 19, ordenamos nosso vetor de distribuição estacionária real em ordem decrescente relativa a p. O for da linha 23 atribui a lista rW_real as 10 primeiras tuplas de w_real. Em seguida imprimimos a w_real e o ranking rW_real.

O resultado da execução do algoritmo acima é o exibido na figura 3 e 4, onde na figura 3 mostramos o resultado da impressão do w_real e na figura 4 o resultado do ranking.

Figura 3 - Resultado da execução do algoritmo de calculo da distribuição estacionária. No console está mostrando o conteúdo do w_real.

Figura 4 - Resultado da execução do algoritmo de calculo da distribuição estacionária. No console está mostrando o conteúdo do rW_real.

Dessa forma, obtemos o ranking dos vértices mais visitados. Como cada vértice representa um livro, temos que os livros mais comprados, por exemplo, foram respectivamente os dos índices: 8, 12, 3, 84, 72, 66, 73, 30, 11, 40. Fazendo uma analogia ao Google os vértices poderiam significar websites, então teríamos um ranking das páginas da web mais visitadas ao invés de livros.

o   A distribuição estacionária gerada pelo power method:

No power method a distribuição estacionária é calculada, de certa forma, por “Força bruta”, pois pode ser implementada de forma recursiva e utiliza multiplicações de matrizes a cada recursão tornado a execução deste método bastante custosa. No entanto, a recursão pode ser substituída pela formula, que mesmo assim ainda exige bastante processamento:

W(k) = w(0)*pK

W(k) é a distribuição estacionária relativa à etapa k, ou seja, na execução k da recursão, ou ainda é a distribuição estacionária quando realizado uma caminhada aleatória de tamanho k; w0 é o vetor inicial de distribuição, dado por quaisquer valores, desde que a soma dos elementos do vetor sejam 1; e pk é a matriz de probabilidade que representa a probabilidade de visitar um vértice em uma caminhada aleatória. Pk é dado pela expressão:

pk = ∆(-1)*A, onde A é a matriz de adjacência

E ∆(-1) é uma matriz de mesma dimensão de A, e é dado por:

∆(-1) = { 1/d(vi) se i = j;  0 se i != j onde d(vi) é o grau do vértice vi.

Para obtermos a distribuição estacionaria com k = 5 e 100, w(5) e w(100), criamos o algoritmo escrito na figura 5:

Figura 5 - Algoritmo do power method da caminhada aleatória de tamanho 5.

Neste algoritmo, calculamos a distribuição estacionária para k igual a 5. A linha 66 inicializamos o vetor de distribuição inicial. Logo em seguida, calculamos a função ∆(-1), o que no código chamamos de Delta. Depois calculamos a matriz de adjacência e chamamos o PowerMethod(), que retorna o vetor de distribuição estacionária e atribui à w_power5. Na linha 64 ordenamos em ordem reversa a distribuição e pegamos os 10 primeiros elementos para o ranking. A figura 6 mostra o código do método power para k = 100.

Figura 6 - Alteração do algoritmo do power method para uma caminhada aleatória de tamanho 100.

Agora, vamos analisar a função PowerMethod(). Nesta função, no primeiro while, multiplicamos a matriz p, n vezes obtendo p^n, que no algoritmo é a matriz Pnew. Depois fazemos a multiplicação da matriz Pnew e do vetor de distribuição estacionária inicial e atribuímos o resultado a power. Por fim, convertemos a matriz power em um vetor de tuplas como fizemos na distribuição estacionária teórica e retornamos este vetor. 
É interessante notar que para manipular as matrizes usamos a biblioteca numpy: http://www.numpy.org/.  A figura 7, exibe o algoritmo:

Figura 7 - Função que realiza o power method para uma caminhada aleatória de tamanho n.

O código das funções que calcula a matriz de adjacência e múltipla matriz, por questão de espaço não vamos comenta-los. 

Os resultados do ranking da execução do power method 5 e 100 estão nas figuras 8 e 9 respectivamente:

Figura 8 - Resultado da execução do algoritmo de calculo da distribuição estacionária com power method para uma caminhada aleatória de tamanho 5. 

Figura 9 - Resultado da execução do algoritmo de calculo da distribuição estacionária com power method para uma caminhada aleatória de tamanho 100. 

Observamos que tanto para a execução de power 5 quanto para a execução do power 100 o ranking gerado de vértices mais visitados foram respectivamente: 12, 3, 72, 8, 84, 66, 73, 11, 47 e 40. Como no exemplo da distribuição teórica, estes vértices representam quais foram os livros mais comprados, uma vez que o grafo simboliza a relação de livros (vétices) que foram comprados por clientes (arestas).  

o   A distribuição estacionária gerada pela caminhada aleatória de fato:

Nessa seção, foi usado o método de estimar a distribuição estacionária simulando caminhadas aleatórios de fato sobre o grafo. Começamos a caminhada de um vértice qualquer, e sorteamos um vértice entre os vizinhos para seguir a caminhada. A cada vez que passamos por cada vértice, contamos uma visita a mais, e assim no final temos os valores das visitas em cada vértice. Esse método, se baseia em quanto mais o vértice tiver conexões maior a probabilidade dele ser caminho de algum lugar.

Nesse modelo, foram usadas caminhadas aleatórias de tamanho 100, e 1000.  Os vértices inicias usados foram 1 e 103. Segue o código:

Figura 10 - Algoritmo que realiza a caminhada aleatória em um gafo G, a partir de uma raiz no e de tamanho n.

Neste código, também, usamos funções da biblioteca networkx:

                                                    for v in G.nodes():

          G.node[v]['Visitas'] = 0

Nessa porção de código, construímos um loop que pega cada vértice v presente no Grafo G, ou seja, ele vai rodar até que a G.nodes não tenha mais nenhum elementos inspecionado, e em v estará o objeto vértice corrente do grafo. Na segunda linha, usamos o conceito de dicionário de dados, que consiste na capacidade do desenvolvedor associar objetos com outros objetos vinculados por um índice, ou nesse caso, por um vértice. Associamos com cada vértice o objeto Visitas, que vai controlar o número de visitas que cada vértice terá. Nesse primeiro for, estamos inicializando todas as visitas como 0.

                                              

u = no

for x in range(tamanho):

F = G.neighbors(u)

c = random.randint(0, (len(F)-1

u = F[c]

G.node[u]['Visitas'] = G.node[u]['Visitas'] + 1

Nessa trecho, fazemos com  que a variável u, receba o valor de nó, que por definição da função terá o vértice inicial. Posteriormente, construímos um loop que roda de 0 até o tamanho da sua caminhada aleatória. Na terceira linha, usamos a função G.neighbors(u) que retorna todos os vizinhos do vértice u, e joga esses valores nessa lista F. Na quarta linha, a variável c, recebe o resultado da função radint, que retorna um inteiro aleatório definido nas margens pelos parâmetros apresentados. Ou seja, um aleatório entre 0 e o tamanho da lista F que contém os vizinhos. Na quinta linha, pegamos o vértice da lista F, que foi sorteado, e posteriormente contamos uma visita a mais pra ele.

                                  

                                       Tuplas = []

for v in G.nodes():

a = G.node[v]['Visitas']

a = a / float(tamanho)

Tuplas.append((v, a))

return Tuplas

Nessa porção, criamos uma lista chamada Tuplas, inicialmente vazia. Na segunda linha construímos um loop que roda para vértice presente em G, em seguida, pegamos o número de visitas de cada nó, e dividimos pelo tamanho da caminhada para obter a probabilidade de cada vértice. Guardamos esses valores de probabilidades juntamente com o vértice correspondente em uma tupla, e usamos a lista Tuplas para armazenar essas tuplas. Depois, como resultado da função retornamos a lista Tuplas.
Testes: 

Figura 11 - Algoritmo que aplica a função a função randomwalk (da figura 10) e gera os ranking em cada caso.

 Resultado da execução do algoritmo:

Figura 11 - Resultado da aplicação das caminhas aleatórias de tamanhos variados e partindo de vértices diferentes.

• Análise e conclusões

Analisando o resultado obtido na execução do power method com k = 5 e k = 100, temos que a distribuição gerada por este método aproximou bastante a distribuição estacionaria real, uma vez que os vértices lá apontados também estão na aproximação deste método, apesar de a ordem em que eles apareçam variar um pouco e apenas um vértice não coincidir em ambas as distribuições. 

Observando os resultados obtidos na execução da caminhada aleatória em n =100a e n = 100b percebemos que ambas são totalmente diferentes, apesar de a relação de visitas nos seus vértices serem parecidas. isso se dá de certa forma, por a caminhada ao iniciar no vértice 1 não chega quase a visitar ou inspecionar os vértices mais distantes. O mesmo ocorre quanto iniciamos a caminhada do vértice 103, os vértices visitados não chegam próximo aos vértices iniciais. Por isso, esta discrepância nos ranking.

Para as caminhadas n =1000a e  n=1000b o mesmo fenômeno ocorre, no entanto, para esta já começam a ter vértices iguais em ambos os ranking como os vértices 73, 84 e o 30. Apesar de não possuírem a mesma posição no ranking, ou seja, terem as mesmas relações de visitas por total de vértices visitados, já percebemos que em uma caminhada de tamanho 100 já começam a se destacar alguns vértices que fazem partes da distribuição estacionária real como é o caso destes vértices.