Árvores geradoras mínimas e comunidades

O objetivo desse trabalho é usar o algoritmo de Prim em um dataset já pronto para extrair uma árvore mínima (MST) e obter comunidades de nós. As ferramentas usadas assim como no trabalho anterior é a linguagem de programação Python com a extensão networkx para abstração de código para grafos.

Árvores Geradoras Mínimas

Uma árvore geradora mínima é uma árvore e um subgrafo de um grafo G que conecta todos os vértices de um grafo com o peso total mínimo de arestas.

Os algoritmos para encontra a árvore geradora mínima tem diversas aplicações, como por exemplo conectar a rede entre os departamentos de um campus universitário com o menor custo de construção.

Fig 1: O caminho mais escuro representa uma árvore de geração mínima

Algoritmo de Prim

O algoritmo de Prim é um algoritmo guloso que encontra uma árvore geradora mínima de um grafo G dado um vértice inicial.

Ele se assemelha bastante com o algoritmo BFS, contudo ele leva em consideração o peso das arestas para formar o subgrafo.

O algoritmo de Prim parte de um vértice inicial e visita os vértices vizinhos que estão dentro da fila de prioridades de vértices não visitados atualizando seus custos e predecessores. Feito isso é escolhido o vértice com maior prioridade, ou seja, com o menor custo e se repete o processo até não existir mais vértices na fila.

Fig 2: Algoritmo de Prim

É utilizado uma lista de nós abertos e uma lista de nós fechados que determina os nós que já foram ou não visitados.

A variável w é um vetor que contem o peso da tabela de iterações conforme vimos em aula, todos eles são inicializados como infinito. A variável t é a lista que define o caminho através de seus predecessores.

A função recebe o parâmetro init que define qual o vértice que iremos começar a caminhar e inicializamos seu peso como 0, então prosseguimos o colocando na lista de vértices abertos.

Então a execução de fato do algoritmo se ínicia após essa série de inicializações. Verificamos se a lista de vértices não visitados é diferente de zero, se ela for zero implica que já caminhamos o grafo inteiro, se ela não for o algoritmo verifica os vizinhos e une eles a lista de vértices abertos caso eles não tenham sido visitados ainda, e também atualiza a lista de pesos em w e t.

Obtenção de comunidades

Para a obtenção de comunidades é utilizado estratégia de isolamento de vértices por meio de remoção de arestas de maior custos.

Ao removermos uma aresta de maior custo, obtemos duas comunidades. Se quisermos obter 3 comunidades é necessário remover 2 arestas de maior custo. Ou seja, para obter N comunidades é preciso remover N-1 arestas de maior custo.

Fig 3: Gerando colonias

O algoritmo para gerar K comunidades é bem simples, como podemos observar. Basta remover as K-1 arestas de maior custo do grafo G dentro de um loop.

Resultados Obtidos

Fig 4: MST gerada

A partir dessa MST podemos obter as comunidades a seguir.

Fig 5: Grafo separado em 2 comunidades
Fig 6: Grafo separado em 5 comunidades

Você pode encontrar o código aberto, as imagens geradas, o grafo original e outros no link:

https://www.dropbox.com/s/tkfjtli23v7prgj/t2.zip?dl=0