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:
Para realizar essa parte, por meio da linguagem Python, utilizamos o seguinte código:
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.
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.
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.
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.
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.
.png)







Nenhum comentário:
Postar um comentário