Simulação e detecção em redes através de MST's - T 3

O objetivo deste trabalho é detectar comunidades em um grafo. A identificação dos grupos ou comunidades será realizada da seguinte forma: primeiramente computa-se uma MST(Minimum Spanning Tree) do grafo G = (V, E) em questão. De posse da MST, a forma mais trivial de obter grupos ou comunidades consiste em isolar conjuntos de vértices através da remoção de arestas da MST. Neste trabalho, o critério a ser utilizado é a remoção da maior aresta da MST no caso de 2 grupos. Para obter 3 grupos, deve-se remover as 2 maiores arestas da MST e assim sucessivamente de modo que para se obter K grupos deve-se remover as K-1 maiores arestas da MST. Para gerar a MST necessária para a computação das comunidades utilizaremos o algoritmo de Prim.

• Materiais utilizados:

Mais uma vez usamos a linguagem Python para fazer os algoritmos e simular a detecção das comidades. No Windows, usamos o Python(x,y), que engloba uma série de bibliotecas e alguns ambientes de desenvolvimento. Spyder é um destes ambientes e foi utilizado para a programação e execução dos algoritmos. Abaixo estão os links para mais informações sobre o ambiente de programação, sobre a biblioteca NetworkX também usada neste trabalho para facilitar a manipulação dos grafos e também a ferramenta Setuptools que permite de forma fácil instalar bibliotecas Python, em especial a NetworkX que não vem inclusa no pacote do Python(x,y). links: 

 - https://code.google.com/p/pythonxy/ .

- https://networkx.github.io/ .

- https://pypi.python.org/pypi/setuptools 

• Grafo:

O grafo utilizado neste trabalho é um grafo ponderado de 59 vértices que relaciona a distâncias entre as cidades na Alemanha

• Desenvolvimento:

Nesta seção apresentaremos alguns aspectos teóricos bem como os resultados obtidos na execução do algoritmo, a construção da MST e a detecção das comunidades.

o   A Minimum Spanning Tree (Árvore geradora minima):

As MST's são árvores - árvores são grafos do acíclicos, conexo onde existe um único caminho entre quaisquer dois vértices - que minimiza a soma dos pesos de uma aresta de um grafo ponderado. 

Figura 1 - Exemplo de uma árvore geradora mínima em uma grafo G.

o  O algorimo de Prim:

O algoritmo de Prim é um algoritmo que utiliza uma estratégia gulosa, para encontrar a MST de um grafo ponderado, conectado e não-direcionado. O algoritmo foi desenvolvido em 1930 pelo matemático Vojtěch Jarník e depois pelo cientista da computação Robert Clay Prim em 1957 e redescoberto por Edsger Dijkstra em 1959.
A ideia geral deste algoritmo consiste em cada passo, partindo de um vértice raiz, adicionar a MST a aresta de menor custo que sai do conjunto dos vértices já visitados e chaga no conjunto dos vértices não visitados. A implementação do algoritmo sera apresentada no decorrer do texto.

o  Implementação:

A implementação do algoritmo será apresentada em várias partes. Primeiramente sera apresentado o código que realiza a geração da MST, apresentaremos a implementação do algoritmo de Prim, bem como as funções que plotam o grafo. Em seguida, apresentaremos o algoritmo que gera as comunidades, 3 e 4 comunidades.
O trecho do algoritmo abaixo faz a geração da MST, neste código fazemos criamos uma arvore, carregamos a matriz de adjacência do grafo g, criamos as arestas baseados na matriz e por fim chamamos o Prim_algorithm(), passado g como parâmetro. Este método gerará a MST e chamara a função que desenhara a matriz na tela.





O próximo trecho é a implementação do algoritmo de Prim. Como já introduzido, o algoritmo a cada passo seleciona a aresta de menor custo. Isso é feito utilizando uma lista de prioridades. Nesta lista a cada passo será retirado no vértice de menor custo, custo este dado por um lambda que representa o custo(distância) de chegar ao vértice atual, que o passo do algoritmo está, partindo de outro vértice predecessor x. Note que x e v representado por este lambda já é o menor caminho para se chegar a v. então o algoritmo verifica nos vizinhos de v  se o caminha v ~ u, onde u é um vértice vizinho de v, é menor do que o caminho para se chegar a u que já fora computado (visitado) em outro passo. Uma observação, é que caso o vértice u ainda não foi descoberto, ou seja, não foi computado um caminho até ele, o caminho v~u é sempre o menor, pois não existe outro, então este caminho será computado na árvore até que se ache, se existir, um outro melhor. V, então, é adicionado á uma fila de predecessores como sendo o predecessor de u. Ao final do algoritmo a fila de predecessores representa a MST.

Outras funções usadas pelo algoritmo também estão expostas neste trecho. A função minimo() retorna a posição do vértice com minimo lambda na fila de prioridades. A função Gera_Arvore() cria a MST a partir do vetor de predecessores e chama a função para plotar a árvore. A função plot_weighted_graph(G) utiliza algumas funções da networkX para plotar um grafo, neste caso a MST.

A figura 2 ilustra a MST gerada para o grafo analisado neste trabalho.

Figura 2 - Grafo que representa a MST gerada a partir do código do Prim, implementado acima.

A seguir está sendo apresentado o código que gera as comunidades no grafo a partir da MST. 
Neste trecho, do mesmo modo que acima, é feita a leitura do grafo g e gerado a MST. Um dicionários com arestas sendo a chave e o peso sendo o dado associado a chave é usado para armazenar todas as arestas da MST. Logo em seguida, o o dicionário é transformado em uma lista onde cada elemento da lista continua sendo a relação aresta/peso, no entanto, esta lista está ordenada em relação aos pesos. Então o for da linha 77 e 78, itera 3 e ou 4 vezes sobre a lista de arestas deletando as 3 e ou as 4 aresta de maior peso, últimos elementos da lista, criando respectivamente 3 e 4 comunidades. 



As figuras 3 e 4 mostram as saídas do grafo com 3 e quatro comunidades. Os desenhos dos grafos obtidos foram os melhores conseguidos por nós.

Figura 3 - Grafo com 3 comunidades, gerados a partir da MST do grafo analisado neste trabalho.

Figura 4 - Grafo com 4 comunidades, gerados a partir da MST do grafo analisado neste trabalho.

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.

Welcome

Olá Leitor!

Nós, autores deste blog, somos alunos do curso de Ciência da Computação da Universidade Federal de São Carlos (UFSCar). Este espaço é uma iniciativa de uma disciplina que cursamos no quarto semestre, Teoria do Grafos. A ideia é que possamos de forma bem simples, como um guia/tutorial, apresentar como resolvemos alguns problemas expostos durante a disciplina no formato de trabalhos práticos. 

Deste de já, agradecemos o interesse e a atenção! 

att,
Autores.