terça-feira, 28 de outubro de 2014

[TUTORIAL] Agrupamento de Dados com MST's


Como já comentado no post anterior (para entendimento de conceitos recomendamos a leitura desse), pretendemos realizar nesse segundo tutorial a análise de um grafo para poder simular a detecção de comunidades em redes através do uso de Árvores Geradoras Mínimas. Para realizar isso, devemos ter como objeto de análise um grafo ponderado, ou seja, as arestas do grafo possuem diferentes pesos.

No caso desse tutorial, utilizaremos um grafo contendo 59 vértices (imagem abaixo) que representa diferentes cidades da Alemanha, sendo que as arestas que ligam os vértices representam a distância entre essas cidades. Assim, temos um grafo ponderado para analisar.





Para realizar a simulação de detecção de comunidades em redes, primeiramente, através do algoritmo de Prim, que será especificado a seguir, realizaremos a computação de uma Árvore Geradora Mínima (do inglês Minimal Spannig Tree - MST) do grafo em questão, com a utilização da biblioteca networkx. A MST pode não ser única para um dado grafo ponderado (podemos encontrar várias árvores geradoras de peso minimo para um mesmo grafo G), mas toda MST desse grafo possui a mesma soma dos pesos. Ou seja, a MST gerada pela networkx pode não ter as mesmas arestas que a gerada pelo seu código, ainda assim a soma dos pesos será igual para as MST's geradas. Por fim, para poder isolar grupos e comunidades, faremos a remoção da aresta de maior valor da árvore que foi conseguida.


Para encontrar uma MST em um dado grafo, é necessário utilizar um algoritmo. Nesse tutorial demonstraremos a utilização do algoritmo de Prim, que segue o a técnica de algoritmo ganancioso. O algoritmo constrói uma MST através de uma sequência de expansão de subárvores. 















  • Algoritmo de Prim - Funcionamento:
Um vértice qualquer é selecionado arbitrariamente e se torna a raíz da árvore. Uma fila de prioridades é criada, onde cada vértice na fila, excetuando a raíz, recebe o valor infinito. A raíz, como é o vértice inicial, tem custo 0. Os vizinhos (vértices adjacentes, que se ligam) da raíz passam a ter ela como predecessora e o custo de entrada nesse vértice é atualizado na fila de prioridades para o valor da aresta que junta a raíz ao vértice. A raíz então é eliminada da fila de prioridades. O vértice de menor custo passa a ser analisado, vamos chamá-lo de u. Para todos os vizinhos v de u que se encontram ainda na fila de prioridades, se v possuir uma aresta que liga ele a u com custo inferior ao que está salvo na fila de prioridades, v passa a ter como predecessor u, e o valor do custo de entrada de v é atualizado na fila de prioridades para o peso da aresta que liga u e v. Se isso não ocorrer, ou seja, a aresta (u,v) possui peso maior que o valor que se encontra na fila de prioridades, nenhuma atualização ocorre (o predecessor e o custo de entrada continuam os mesmos). Após isso, u é eliminado da fila de prioridades, e o vértice de menor custo da fila passa a ser u, e o processo se repete.



A seguir mostraremos o processo teórico de um exemplo de geração de uma árvore geradora com peso mínimo. A primeira imagem representa a fila de prioridades, e a segunda a execução do algoritmo:



Considere o grafo a seguir:


Primeira Iteração:

a
b
c
d
e
f
g
h
i
λ (v)
0
∞
∞
∞
∞
∞
∞
∞
∞


A fila de prioridades se comporta dessa maneira primeiramente. Todos os vértices são inicializados com infinito, excetuando a raiz, que inicialmente tem valor 0.

u
Vizinhos de u que ainda estão na fila
Menor custo de v
Predecessor de v
a
{b, h}
λ(b) = 4
λ(h) = 8
π(b) = a
π(h) = a


O vértice a é escolhido como raiz. Primeiro passo é analisar os vizinhos de a que ainda estão na fila. O custo de entrar em cada vértice é atualizado, bem como seu predecessor.

O grafo fica dessa maneira:
Segunda Iteração:

a
b
c
d
e
f
g
h
i
λ (v)
0
∞
∞
∞
∞
∞
∞
∞
∞
λ (v)
4
∞
∞
∞
∞
∞
8
∞

u
Vizinhos de u que ainda estão na fila
Menor custo de v
Predecessor de v
a
{b, h}
λ(b) = 4
λ(h) = 8
π(b) = a
π(h) = a
b
{c,h}
λ(c) = 8
λ(h) = 8
π(c) = b
π(h) = a


O vértice de menor custo na fila é escolhido. No caso é o b. São analisados seus vizinhos que ainda estão na fila. Os vizinhos de b que possuem custo de entrada por b inferior ao custo de entrada anterior têm seus valores de custo de entrada e predecessor atualizados. Depois, b é eliminado da fila.

O grafo fica dessa maneira:

Terceira Iteração:

a
b
c
d
e
f
g
h
i
λ (v)
0
∞
∞
∞
∞
∞
∞
∞
∞
λ (v)
∞
∞
∞
∞
∞
8
∞
λ (v)
8
∞
∞
∞
∞
8
∞
 
u
Vizinhos de u que ainda estão na fila
Menor custo de v
Predecessor de v
a
{b, h}
λ(b) = 4
λ(h) = 8
π(b) = a
π(h) = a
b
{c,h}
λ(c) = 8
λ(h) = 8
π(c) = b
π(h) = a
c
{d,f,i}
λ(d) = 7
λ(f) = 4
λ(i) = 2
π(d) = c
π(f) = c
π(i) = c 


O vértice de menor custo na fila é escolhido. Como possui dois com valor mínimo, deve-se escolher um. Bem, o escolhido será o c. São analisados seus vizinhos que ainda estão na fila. Os vizinhos de c que possuem custo de entrada por c inferior ao custo de entrada anterior têm seus valores de custo de entrada e predecessor atualizados. O c é eliminado da fila.

O grafo fica dessa maneira:
Quarta Iteração:

a
b
c
d
e
f
g
h
i
λ (v)
0
∞
∞
∞
∞
∞
∞
∞
∞
λ (v)
∞
∞
∞
∞
∞
8
∞
λ (v)
∞
∞
∞
∞
8
∞
λ (v)
7
∞
4
∞
8
2

u
Vizinhos de u que ainda estão na fila
Menor custo de v
Predecessor de v
a
{b, h}
λ(b) = 4
λ(h) = 8
π(b) = a
π(h) = a
b
{c,h}
λ(c) = 8
λ(h) = 8
π(c) = b
π(h) = a
c
{d,f,i}
λ(d) = 7
λ(f) = 4
λ(i) = 2
π(d) = c
π(f) = c
π(i) = c
i
{h,g}
λ(h) = 7
λ(g) = 6
π(h) = i
π(g) = i

O vértice de menor custo na fila é escolhido. No caso é o i, pois tem custo 2. São analisados seus vizinhos que ainda estão na fila. Os vizinhos de i que possuem custo de entrada por i inferior ao custo de entrada anterior têm seus valores de custo de entrada e predecessor atualizados. Após isso, o i é eliminado da fila.

O grafo fica dessa maneira:


Quinta Iteração:

a
b
c
d
e
f
g
h
i
λ (v)
0
∞
∞
∞
∞
∞
∞
∞
∞
λ (v)
∞
∞
∞
∞
∞
8
∞
λ (v)
∞
∞
∞
∞
8
∞
λ (v)
7
∞
4
∞
8
λ (v)
7
∞
4
6
7


u
Vizinhos de u que ainda estão na fila
Menor custo de v
Predecessor de v
a
{b, h}
λ(b) = 4
λ(h) = 8
π(b) = a
π(h) = a
b
{c,h}
λ(c) = 8
λ(h) = 8
π(c) = b
π(h) = a
c
{d,f,i}
λ(d) = 7
λ(f) = 4
λ(i) = 2
π(d) = c
π(f) = c
π(i) = c
i
{h,g}
λ(h) = 7
λ(g) = 6
π(h) = i
π(g) = i
f
{d,e,g}
λ(d) = 7
λ(e) = 10
λ(g) = 2
π(d) = c
π(e) = f
π(g) = f

O vértice de menor custo na fila é escolhido. No caso é o f, pois tem custo 4. São analisados seus vizinhos que ainda estão na fila. Os vizinhos de f que possuem custo de entrada por f inferior ao custo de entrada anterior têm seus valores de custo de entrada e predecessor atualizados. Após isso, o f é eliminado da fila.

O grafo ficará da seguinte maneira:
Sexta Iteração:

a
b
c
d
e
f
g
h
i
λ (v)
0
∞
∞
∞
∞
∞
∞
∞
∞
λ (v)
∞
∞
∞
∞
∞
8
∞
λ (v)
∞
∞
∞
∞
8
∞
λ (v)
7
∞
4
∞
8
λ (v)
7
∞
6
7
λ (v)
7
10
2
7

u
Vizinhos de u que ainda estão na fila
Menor custo de v
Predecessor de v
a
{b, h}
λ(b) = 4
λ(h) = 8
π(b) = a
π(h) = a
b
{c,h}
λ(c) = 8
λ(h) = 8
π(c) = b
π(h) = a
c
{d,f,i}
λ(d) = 7
λ(f) = 4
λ(i) = 2
π(d) = c
π(f) = c
π(i) = c
i
{h,g}
λ(h) = 7
λ(g) = 6
π(h) = i
π(g) = i
f
{d,e,g}
λ(d) = 7
λ(e) = 10
λ(g) = 2
π(d) = c
π(e) = f
π(g) = f
g
{h}
λ(h) = 1
π(h) = g

O vértice de menor custo na fila é escolhido. No caso é o g, pois tem custo 2. São analisados seus vizinhos que ainda estão na fila. Os vizinhos de g que possuem custo de entrada por g inferior ao custo de entrada anterior têm seus valores de custo de entrada e predecessor atualizados. Após isso, o g é eliminado da fila.

O grafo ficará da seguinte maneira:


Sétima Iteração:


a
b
c
d
e
f
g
h
i
λ (v)
0
∞
∞
∞
∞
∞
∞
∞
∞
λ (v)
∞
∞
∞
∞
∞
8
∞
λ (v)
∞
∞
∞
∞
8
∞
λ (v)
7
∞
4
∞
8
λ (v)
7
∞
6
7
λ (v)
7
10
7
λ (v)
7
10
1

u
Vizinhos de u que ainda estão na fila
Menor custo de v
Predecessor de v
a
{b, h}
λ(b) = 4
λ(h) = 8
π(b) = a
π(h) = a
b
{c,h}
λ(c) = 8
λ(h) = 8
π(c) = b
π(h) = a
c
{d,f,i}
λ(d) = 7
λ(f) = 4
λ(i) = 2
π(d) = c
π(f) = c
π(i) = c
i
{h,g}
λ(h) = 7
λ(g) = 6
π(h) = i
π(g) = i
f
{d,e,g}
λ(d) = 7
λ(e) = 10
λ(g) = 2
π(d) = c
π(e) = f
π(g) = f
g
{h}
λ(h) = 1
π(h) = g
h
--------------
--------------
--------------

O vértice de menor custo na fila é escolhido. Dessa vez o escolhido foi o h. Como ele não possui vizinho que ainda não foi visitado, devemos analisar novamente a fila de prioridades.

Oitava Iteração:

a
b
c
d
e
f
g
h
i
λ (v)
0
∞
∞
∞
∞
∞
∞
∞
∞
λ (v)
∞
∞
∞
∞
∞
8
∞
λ (v)
∞
∞
∞
∞
8
∞
λ (v)
7
∞
4
∞
8
λ (v)
7
∞
6
7
λ (v)
7
10
7
λ (v)
7
10

u
Vizinhos de u que ainda estão na fila
Menor custo de v
Predecessor de v
a
{b, h}
λ(b) = 4
λ(h) = 8
π(b) = a
π(h) = a
b
{c,h}
λ(c) = 8
λ(h) = 8
π(c) = b
π(h) = a
c
{d,f,i}
λ(d) = 7
λ(f) = 4
λ(i) = 2
π(d) = c
π(f) = c
π(i) = c
i
{h,g}
λ(h) = 7
λ(g) = 6
π(h) = i
π(g) = i
f
{d,e,g}
λ(d) = 7
λ(e) = 10
λ(g) = 2
π(d) = c
π(e) = f
π(g) = f
g
{h}
λ(h) = 1
π(h) = g
h
--------------
--------------
--------------
d
{e}
λ(e) = 1
π(h) = d

Nesse momento, o vértice de menor custo é o d. Ele possui como vizinho que ainda não foi retirado da fila de prioridades o e. O custo de entrada de e pelo d é menor que o anterior, então, tanto o predecessor de e, como seu custo são atualizados.


O grafo ficará da seguinte maneira:


E o valor de entrada em e passa a ser 9:

a
b
c
d
e
f
g
h
i
λ (v)
0
∞
∞
∞
∞
∞
∞
∞
∞
λ (v)
∞
∞
∞
∞
∞
8
∞
λ (v)
∞
∞
∞
∞
8
∞
λ (v)
7
∞
4
∞
8
λ (v)
7
∞
6
7
λ (v)
7
10
7
λ (v)
10
λ (v)
9

A árvore geradora mínima de peso 37 foi gerada.

  • Gerando a MST pela biblioteca Network X: 
Mostraremos como gerar uma MST a partir de um grafo G com utilização da biblioteca networkx da linguagem Python. Logo depois utilizaremos essa MST e suas informações para comparar com a MST gerada pelo algoritmo que implementamos nesse tutorial.

No algoritmo apresentado acima, estamos lendo os valores salvos na matriz e convertendo em um grafo. Na linha 9 com a função nx.minimum_spanning_tree(G) geramos a árvore geradora mínima, salvando em T. Logo depois salvamos os pesos em uma lista e apresentamos o somatório dos pesos para que no próximo tópico conferirmos com a árvore que vamos gerar:




A partir das linhas 18 a 25 foi possível plotar o grafo dessa MST. Observe abaixo.



  • Implementação do Algoritmo de Prim
Acima temos a implementação do Algoritmo de Prim realizada. Nessa implementação escolhemos manipular os dados diretamente da matriz para que fosse compreendido o conceito de matriz de adjacência.

Como no exemplo de funcionamento que mostramos, foi utilizado uma lista para custos, outra para fila e outra para os predecessores. Nas linhas 3, 4 e 5 apresentam as inicializações com seus devidos valores. Logo depois utilizamos uma função random para a escolha do vértice raiz, já que o Algoritmo de Prim tem como conceito escolher uma raiz arbitrária. O custo da raiz e o predecessor são inicializados com valores que não serão validados quando plotar a árvore.

O while da linha 15 a 30 é toda a implementação do algoritmo de Prim. Nessa parte está sendo preenchida a fila com os pesos das arestas da matriz e logo depois é selecionado dessa fila o menor valor peso presente e então o vértice vizinho que contém essa aresta é escolhido como o vértice que será visitado. Esse loop acontecerá até que a fila esteja com elementos.

Com todos os predecessores preenchidos, já que a fila está vazia todos os elementos foram visitados, vamos criar nosso grafo com as arestas correspondentes a (i, pred[i]), sendo i os vértices e pred[i] seus predecessores, encontraremos nossa árvore geradora mínima, observe a imagem desta abaixo:



Na linha 46 pegamos a lista dos pesos dessa árvore para realizar a soma e conferir com o valor encontrado da árvore gerada pela biblioteca e assim validarmos nosso algoritmo.



Concluímos então, comparando a soma dos pesos e o número de vértices, que são Árvores Geradoras Mínimas diferentes, mas que possui o mesmo somatório de peso, logo as duas estão corretas. Como falamos na introdução, é possível encontrar várias MSTs, mas todas vão gerar o mesmo valor de peso mínimo.


  • Identificação dos grupos ou comunidades:



Essa parte consiste em eliminar as arestas com maior peso e assim formar grupos (ou comunidades) similares.

Inicialmente ordenamos de forma crescente a lista de pesos para identificar os maiores. Na lista de peso original (W_MST) identificamos a posição desse peso e selecionamos seu predecessor. Com a função G.remove_edge(u,v) removemos as duas maiores arestas e depois removendo mais uma, formando 4 grupos.

Imagem com 3 grupos (remoção das duas maiores arestas):


 Animação mostrando a MST normal e a MST com remoção das duas arestas:

Imagem com 4 grupos (remoção das três maiores arestas):

Animação com a MST original, depois com a remoção das duas maiores e depois com a remoção da terceira maior:


  • Conclusão:


A detecção de comunidades em grafos é de extrema importância na análise de redes representadas por grafos. Neste tutorial apresentamos uma maneira simples de realizar essa detecção. A geração de uma MST no grafo analisado foi o ponto inicial para que pudéssemos realizar tal feito. Isso demonstra a importância desses tipos de algoritmos na análise de Grafos.

O grafo em questão representa distância entre cidades da Alemanha. A detecção de comunidades em grafos que representam informações como essa se mostra bastante útil no dia-a-dia, seja em redes sociais, tecnológicas, biológicas ou de informação.

Nenhum comentário:

Postar um comentário