Árvores Geradoras Mínimas e Comunidades

Vamos falar sobre Árvores Geradoras Mínimas e Comunidades desta vez. Primeiro precisamos esclarecer alguns conceitos como o que é uma árvore:

Figura 1

Uma árvore é um grafo conexo e acíclico. Um grafo conexo não tem vértice ou partes isoladas do restante do grafo. Tudo precisa estar conectado. Um grafo acíclico é, como o nome diz, um grafo sem ciclos, ou seja, sem um circuito fechado formado por suas arestas e vértices. Uma árvore possui um vértice inicial chamado raiz, os vértices seguintes são seus filhos que também podem ter filhos, sendo vértices pai desta forma, e assim por diante até chegar às folhas, ou seja, até chegar àqueles vértices que não possuem filhos.

Como este exemplo abaixo:

Figura 2

Sabendo o que é uma árvore podemos agora descobrir o que é uma árvore geradora. Árvore Geradora é aquela originária de um grafo G e que seja formada por todos os vértices de G.

Figura 3

Dá pra notar que existirão várias árvores geradoras de um mesmo grafo:

Figura 4

Uma delas é especial, trata-se da Árvore Geradora Mínima. Uma Árvore Geradora Mínima (MST) é uma árvore geradora de um grafo G ponderado que tem custo total mínimo.

Figura 5 - Árvore geradora mínima desenhada em vermelho

Há alguns algoritmos utilizados para a extração de MST's e o utilizado neste exemplo foi o Algoritmo de Prim:

Ok, vamos explicar como o algoritmo funciona.

O Algoritmo de Prim consiste em escolher um vértice inicial conhecido como raiz, sem aresta alguma ainda, do qual a árvore irá crescer. Então fazemos a árvore crescer, ou seja, vamos visitando outros vértices adicionando a aresta que está entre o vértice de partida e o novo à árvore.

Esta escolha é feita levando-se em conta o peso das arestas analisadas. A cada descoberta de nova aresta durante o crescimento da árvore o seu peso é colocado em uma lista de prioridades e substitui o seu valor antigo na lista caso seja menor. Esta lista será usada para saber qual aresta deve ser inserida na árvore. A aresta de menor peso na lista de prioridades é sempre escolhida e inserida na árvore.

Caso mais adiante outra aresta que chegue o mesmo vértice tenha uma peso menor que o atual a antiga aresta é retirada e a nova descoberta é inserida. Quando não houver mais vértices para serem visitados teremos uma árvore geradora com a menor soma de pesos de arestas possível, ou seja, encontraremos a Árvore Geradora Mínima.

Agora vamos falar de Comunidades.

Comunidades são, basicamente, conjuntos de vértices isolados. É possível obter comunidades ao retirar arestas da árvore geradora mínima.

Figura 6 - Árvore geradora mínima

Da árvore geradora mínima acima podemos retirar a aresta entre os vértices 'b' e 'e' para obter duas comunidades, chamadas aqui de A e B:

Figura 7

Há entretanto alguns métodos diferentes para se obter comunidades à partir da remoção de arestas da MST. Utilizaremos dois deles aqui.

A primeira forma é decidir um número k de comunidades que se deseja obter e então retirar as k-1 maiores arestas da MST.

Por exemplo, para se obter duas comunidades (k = 2), ou agrupamentos, da MST utilizada acima bastaria retirar as k-1 maiores arestas, ou seja, se k = 2 então k - 1 = 1, bastaria remover a maior aresta da MST. Neste exemplo a aresta a ser retirada será a entre 'b' e 'c', que tem peso 4, formando os agrupamentos A e B:

Figura 8

Se quisermos um número maior, como k = 5 agrupamentos, basta aplicar a mesma regra e retirar as k-1 maiores arestas, ou seja, as 4 maiores, formando os agrupamentos A, B, C, D e E:

Figura 9

Note como há vários vértices isolados, comunidades de um vértice só, isso se deve em parte ao tamanho do grafo utilizado mas o maior problema foi o método utilizado. Note no primeiro exemplo, com k = 2, como seria possível formar agrupamentos com um número de vértices mais parecidos mas ao invés disso o método utilizado fez com que se formasse uma comunidade com um vértice e outra com cinco. Muitas vezes não é desejável que haja tamanha discrepância entre o tamanho das comunidades e por isso utilizaremos agora outro método.

Desta vez ao invés de simplesmente remover as k-1 maiores arestas da MST para se obter k comunidades iremos utilizar o seguinte cálculo para descobrir qual é a melhor aresta a ser removida da MST de forma a deixar o número de vértices em cada agrupamento mais parecido entre si:

w(A,B) * min{Na, Nb}

Onde w(A,B) é o peso da aresta analisada e min{Na, Nb} é o mínimo entre o número de vértices do grupo A (Na) e o número de vértices do grupo B (Nb), pois sempre que uma aresta for removida serão formados exatamente dois agrupamentos (A e B, neste caso). Após fazer os cálculos para todas as arestas selecionaremos o maior valor e removeremos a aresta correspondente.

Na prática ficaria assim, utilizando o seguinte grafo e sua MST para criar dois agrupamentos:

Figura 10 - Grafo G com sua MST escurecida

Figura 11 - MST resultante sem as outras arestas do grafo G

Fazemos então o cálculo descrito para cada aresta da MST:

ab: 4 * min{1,8} = 4*1 = 4
bc: 8 * min{2,7} = 8*2 = 16
cd: 7 * min{2,7} = 7*2 = 14
de: 9 * min{1,8} = 9*1 = 9
ci: 2 * min{1,8} = 2*1 = 2
cf: 4 * min{3,6} = 4*3 = 12
fg: 2 * min{2,7} = 2*2 = 4
gh: 1 * min{1,8} = 1*1 = 1

O maior valor obtido corresponde a aresta 'bc', que será então removida, obtendo assim dois agrupamentos:

Figura 12

Faremos agora o processo para a obtenção de cinco comunidades. Para isso basta repetir os cálculos com valores e arestas atualizados a cada remoção:

ab: 4 * min{1,1} = 4*1 = 4
cd: 7 * min{2,5} = 7*2 = 14
de: 9 * min{1,6} = 9*1 = 9
ci: 2 * min{1,6} = 2*1 = 2
cf: 4 * min{3,4} = 4*3 = 12
fg: 2 * min{2,5} = 2*2 = 4
gh: 1 * min{1,6} = 1*1 = 1

Desta vez o maior valor obtido corresponde a aresta 'cd', então removendo-a teremos:

Figura 13

Temos três agrupamentos. Retiremos mais uma aresta para obter quatro agrupamentos:

ab: 4 * min{1,1} = 4*1 = 4
de: 9 * min{1,1} = 9*1 = 9
ci: 2 * min{1,4} = 2*1 = 2
cf: 4 * min{2,3} = 4*2 = 8
fg: 2 * min{2,3} = 2*2 = 4
gh: 1 * min{1,4} = 1*1 = 1

A aresta 'de' deve ser removida agora:

Figura 14

Calculamos uma última vez:

ab: 4 * min{1,1} = 4*1 = 4
ci: 2 * min{1,4} = 2*1 = 2
cf: 4 * min{2,3} = 4*2 = 8
fg: 2 * min{2,3} = 2*2 = 4
gh: 1 * min{1,4} = 1*1 = 1

Removemos 'cf' e obtemos os cinco agrupamentos abaixo, como desejado inicialmente:

Figura 15

Podemos notar que desde a primeira remoção este método acabou por evitar que vértices ficassem isolados. É claro que depois de algumas iterações alguns vértices isolados acabaram formando comunidades mas houve uma divisão mais parecida com relação à quantidade de vértices em cada comunidade por fim.

O código em Python utilizado para o primeiro método foi o seguinte: