terça-feira, 7 de outubro de 2014

[TUTORIAL] Caminhadas Aleatórias utilizando Python

Nesse tutorial, pretendemos apresentar uma breve introdução a alguns conceitos relacionados com a Teoria dos Grafos, e, com o auxílio da linguagem de programação PYTHON utilizar algoritmos para exemplificar tais conceitos. Mais especificamente, pretendemos analisar o conceito de Caminhadas Aleatórias em Grafos e para isso, apresentaremos algumas definições para maior compreensão dos algoritmos.


  • Mas, o que é um grafo?

Um grafo, formalmente é representado pela expressão: G = (V, E), onde V representa um conjunto não vazio de vértices, e E, que está contido em V X V, é uma relação binária no conjunto V. Basicamente, simplificando, um grafo é um conjunto de pontos (vértices) ligados por um conjunto de arestas. Esses vértices e essas arestas armazenam informações de acordo com que o grafo está representando.

Um conceito bastante útil e importante é o de Grau de um Vértice. O grau de um vértice, representado por d(v) consiste, de modo mais simples, em dizer quantas arestas saem de v, ou seja, é o número de vezes que v é extremidade de alguma aresta de G. Usaremos esse conceito para determinar a distribuição estacionária, ou seja, a probabilidade de o vértice ser visitado numa caminhada aleatória.

Bem, falando mais sobre caminhadas aleatórias, iremos nesse trabalho calcular a CMH (Cadeia de Markov Homogênea que representa o processo não-determinístico conhecido como caminhada aleatória), de três maneiras distintas, atribuindo a um vetor "w" os valores de cada vértice.

A primeira tentativa de estimar o w será da forma teórica, ou seja, w(i) = d(v)/2*|E|. A segunda maneira utilizará o conceito de matriz e a terceira será realmente uma caminhada pelos vértices.

Para esse tutorial utilizaremos o grafo apresentado abaixo:

-  Forma Teórica


Para realizar essa parte, por meio da linguagem Python, utilizamos o seguinte código:


  • Explicação do código:


É necessário salientar que antes de começar a criar o código as bibliotecas a serem utilizadas durante a execução devem ser declaradas. Assim, o código começa da seguinte maneira:

import networkx as nx
import numpy as np
import random as random

O comando import "nome da biblioteca" as "nome de referência durante o programa" é o responsável por declarar a biblioteca que será utilizada e por renomeá-la caso desejado.

A biblioteca networkx possui diversas ferramentas para a manipulação de grafos. A biblioteca numpy é bastante útil e oferece diversas ferramentas para a manipulação de vetores e matrizes. Por fim, a biblioteca random é utilizada para a geração de números aleatórios.

Utilizamos, nesse trabalho, o grafo que mostra a ligação entre golfinhos, que está representado no arquivo dolphins.gml. Para podermos importar ao nosso programa, usamos o comando "G = nx.read_gml('dolphins.gml')", que faz a leitura desse arquivo e atribui o grafo desse arquivo a G, que será manipulado durante a execução do programa.

As três partes do trabalho foram divididas em funções, e aqui segue-se uma explicação da função Parte1(G), que é criada com o comando def da linguagem python. Ela recebe como parâmetro o grafo a ser analisado.

O comando "L = G.degree()" retorna para L um dicionário contendo os valores de cada grau associado a cada vértice.

Para podermos armazenar o valor da distribuição estacionária, foi criado um vetor w_real vazio.
Em seguida, o comando "NE = G.number_of_edges()" retorna para a variável NE o número de arestas presentes no grafo, para podermos calcular posteriormente os valores a serem armazenados em w_real. Entretanto a fórmula diz que w(i) = d(vi) / 2*|E|, então, na linha seguinte a variável NE é duplicada.

Chegamos ao loop. A condição de parada do loop é dada quando a lista toda de vértices for percorrida e analisada. O comando len(L) retorna o tamanho da lista L.

j = G.degree(i), nesse comando é atribuído à variável j o valor do grau do vértice i. j, em seguida é convertida para float, para podermos calcular o valor w(i) que ocorre logo depois. O comando w_real.append(j) é responsável por inserir ao final da lista o valor w(i). Ao terminar o loop, o vetor w_real possui a distribuição estacionária dos vértices do grafo calculada teoricamente.

Abaixo segue o w_real encontrado (clique em cima da foto para visualizar melhor):



-   Power Method


Na segunda parte utilizaremos outro conceito para determinar w.  Para podermos analisar o código é necessário entender o que é uma matriz de adjacência de um grafo.

  •  Matriz de Adjacência:

É uma forma de se representar um grafo a partir de uma matriz nxn onde n é o número de vértices do grafo. Se o vértice da linha i estiver conectado ao vértice da coluna j, a cédula Aij recebe 1. Se não estiver, recebe 0. 

Define-se, também, uma matriz D, que é composta totalmente por zeros, excetuando sua diagonal, que possui o valor de 1/d(vi).

Tendo isso como base, define-se a matriz P, que é dada por P = D * A. A matriz P é a matriz de probabilidades de transição e define o processo não determinístico conhecido como cadeia de Markov Homogênea.

O teorema fundamental das CMHs diz que, seja a matriz P a matriz de transição de uma CMH irredutível e aperiódica. Então a distribuição estacionária é única sendo que:

lim(h->infinito) P elevado a h = | w |
                                                  | w |
                                                  | ... |
                                                  | w |

Quando P tende a um valor muito grande, os valores das linhas da matriz tendem a ser iguais e basta pegar uma linha para poder ter o vetor w, que é o vetor com a distribuição estacionária dos vértices.

Portanto agora iremos analisar a distribuição estacionária a partir da matriz P. Primeiramente, faremos um teste com P elevado a 5 e depois com P elevado a 100.


Foi criada a função Parte2(G, V, k) que recebe como parâmetros o grafo G, o número de vértices desse grafo e o valor de k. O comando A = nx.adjacency_matrix(G), sendo nx.adjacency_matrix uma função da biblioteca networkx, faz com que a variável A receba a matriz de adjacência do grafo G. Precisamos agora da matriz D, que é conseguida a partir dos comandos D = np.zeros((V,V)), que cria uma matriz VXV (número de vértices do grafo) preenchida com 0. O loop em seguida é utilizado para preencher a diagonal com o valor 1/d(v) utlizando a função apropriada da biblioteca networkx que retorna o valor dos vértices.

A matriz P é conseguida logo em seguida, pelo produto das matrizes D e A. Para conseguir P elevado a k foi criada a variável NP que recebe a matriz P e sofrerá as alterações de P elevado a k. Isso acontece no comando while logo em seguida, que tem como condição de parada a variável i atingir o valor de k passado como parâmetro. O comando NP = np.dot(NP, P) realiza a partir de uma função da biblioteca numpy a multiplicação de forma segura da matriz. Por fim, um vetor que representará w recebe os valores de uma das linhas. Para se confirmar, é feita a soma dos valores do vetor, soma a qual deve sempre resultar em 1, já que é uma distrinuição de probabilidades.

A partir da execução dessa função com k = 5 e com k = 100 percebeu-se que a matriz tem seus valores das linhas cada vez mais iguais a medida que o k aumenta.




-   Caminhada Aleatória

Na terceira parte de nosso tutorial, implementamos de fato uma caminhada aleatória no grafo em questão. O código e uma explicação detalhada de seu funcionamento poderá ser vista mais abaixo.

A ideia geral de se realizar a caminhada aleatória se dá da seguinte maneira: escolhemos um vértice inicial, e apartir dele, a caminhada é realizada aleatoriamente entre os vértices vizinhos do anterior. Para podermos determinar uma métrica probabilística dos vértices, é feita a contagem de quantas vezes o vértice foi visitado nessa caminhada e o valor é dividido pelo tamanho da caminhada.

Foi criado uma função CaminhadaAleatoria(G, inicio, tam), onde os parâmetros G, inicio e tam correspondem respectivamente ao grafo, o vertice escolhido para ser o início e o tamanho de visitas totais.

O algoritmo consiste em visitar os vizinhos do vértice atual e ir contando o número de visitas que cada vértice teve.  Através da função random() sorteamos um número inteiro entre 0 e o tamanho do vetor e depois verificamos se é vizinho do vértice atual, se for acrescenta um no contador correspondente a esse vértice e este torna-se o atual.

Após percorrer as 'n' visitas fizemos o cálculo das probabilidades a partir do contador de visitas dividido pelo tamanho total de visitas (prob[i] = contador[i]/float(tam)) e definimos o top 10, pegando os vértices com maior número de visitas.

Para entender o funcionamento da caminhada aleatória foram feitos testes com n = 100 e n = 1000 começando nos vértices 5 e 50. Observe os resultados abaixo:


  • Caminhada de tamanho 100 começando em 5:


Top 10 em ordem decrescente = [10 , 51 , 13 , 6 , 42 , 21 , 9 , 18 , 57 , 37]


  • Caminhada de tamanho 100 começando em 50:


Top 10 em ordem decrescente = [51 , 45 , 18 , 21 , 38 , 33 , 23 , 14 , 37 , 16]


  • Caminhada de tamanho 10000 começando em 5:




Top 10 em ordem decrescente = [14 , 17 , 45 , 57 , 37 , 20 , 29 , 13 , 1 , 33]


  • Caminhada de tamanho 10000 começando em 50:


Top 10 em ordem decrescente = [14 , 45 , 37 , 33 , 51 , 20 , 29 , 40 , 57 , 15]

Conclusões:

A partir da análise da execução das caminhadas aleatórias para número de vértices visitados = 100, começando por 5 e depois por 50, e para número de vértices visitados = 1000, começando em 5 e depois em 50, foi possível perceber que o top dos vetores visitados não se diferenciam muito (comparando apenas os vetores visitados na mesma quantidade - 100 ou 1000 ). Por exemplo, quando a caminhada possui valor 100, é possível perceber que o 51 tem grande probabilidade de ser visitado, mesmo se a caminhada começar no vértice 5. No segundo caso, quando a caminhada possui tamanho 1000, percebemos que os vértices com maior chance de ser visitados são o 14 e o 45, em ambas caminhadas.


Nenhum comentário:

Postar um comentário