Improving DBLP Communities

O algoritmo de Bron-Kerbosch cl´assico (Bron e Kerbosch(1973)) tem como objetivo en- contrar todos os cliques maximais de um grafo G. ´E utilizado o processo de backtracking, e apenas cliques maximais s˜ao gerados, evitando assim, uma boa parte da compara¸c˜ao de um determinado conjunto de cliques que j´a foram testados.

No trabalho de Brito e Santos (2011), os autores adaptaram o algoritmo de Bron- Kerbosch b´asico para refletir o problema da enumera¸c˜ao de cliques com peso acima de um limiar. Al´em disso, propuseram algumas melhorias no algoritmo, descritas sucintamente a seguir. Primeiramente, utilizaram-se da no¸c˜ao de v´ertice pivˆo (Tomita et al. (2006)), com o prop´osito de acelerar a produ¸c˜ao de cliques com peso alto. O v´ertice de m´aximo grau modificado foi escolhido como v´ertice pivˆo. Cada v´ertice tem um grau modificado, o qual se refere ao somat´orio do seu grau com os graus de todos os v´ertices adjacentes a ele. Para reduzir o n´umero de chamadas, os autores observaram que se um clique cont´em um v´ertice adjacente ao v´ertice pivˆo u, tal v´ertice tamb´em faz parte do clique. Logo, apenas u e os v´ertices n˜ao adjacentes a ele precisam ser testados. Essa ´e a ideia central do pivoteamento, desenvolvido pelos autores do algoritmo de Bron-Kerbosch. Por fim, fora utilizado uma t´ecnica de estimativa de peso (vide linha 7 do Algoritmo1), a qual calcula o limite superior do peso de um clique parcial por meio da soma dos pesos dos v´ertices contidos nesse clique com a soma de todos os pesos dos v´ertices candidatos a entrarem no clique. Nesse sentido, alguns cliques parciais podiam ser previamente eliminados. O algoritmo implementado por Brito e Santos (2011) ´e apresentado em Algoritmo 1.

O conjunto C representa os v´ertices que fazem parte do clique. O conjunto P re- presenta os v´ertices que tˆem liga¸c˜ao com todos os v´ertices de C - v´ertices candidatos a entrar no clique. Por sua vez, o conjunto S cont´em todos os v´ertices que j´a foram anali-

Problema da Enumera¸c˜ao de Cliques com Peso acima de um Limiar 11

Algoritmo 1 Algoritmo de Bron-Kerbosch adaptado

1: procedimento BKA(C, P, S) 2: se P e S est˜ao vazios ent˜ao 3: se w (C ) ≥ limiar ent˜ao

4: Adiciona o clique C no conjunto solu¸c˜ao;

5: fim se

6: fim se

7: se w (C ) + h(C ) ≥ limiar ent˜ao 8: Escolha um v´ertice pivˆo u de P ;

9: para cada V´ertice v em P \N (u) fa¸ca 10: BKA(C ∪ {v }, P ∩ N (v ), S ∩ N (v ));

11: P := P \{v };

12: S := S ∪ {v };

13: fim para cada 14: fim se

15: fim procedimento

sados e n˜ao levam a uma extens˜ao do conjunto P. O peso do clique C est´a armazenado em w (C ). O somat´orio dos pesos de todos os v´ertices do conjunto P est´a em h(C ), onde tal vari´avel em conjunto com a vari´avel w (C ) formam a estimativa de peso, a qual ´e usada como um limite superior para o peso do Clique C.

No presente trabalho, foram utilizadas oito implementa¸c˜oes (vers˜oes) do Algoritmo de Bron-Kerbosch adaptado, apresentado em Brito e Santos(2011). Essas implementa¸c˜oes s˜ao diferentes na forma de armazenamento do grafo e na forma de sele¸c˜ao dos v´ertices pivˆos:

1. Uso de matriz: nesta implementa¸c˜ao foi utilizada uma matriz bin´aria m de di- mens˜ao |V | × |V | para representa¸c˜ao das arestas existentes no grafo. Nesse sentido, caso exista uma aresta conectando os v´ertices v1 e v2, m[v1][v2] = 1 e m[v2][v1] = 1.

Os valores zero na matriz bin´aria representam que os v´ertices n˜ao est˜ao conectados. Esta abordagem ´e vantajosa no processamento do Algoritmo de Bron-Kerbosch adaptado, no momento da verifica¸c˜ao da existˆencia ou n˜ao de aresta conectando um par de v´ertices qualquer porque ´e realizada em O(1). Como desvantagem, h´a um uso consider´avel de mem´oria.

2. Uso de lista: com o uso desta implementa¸c˜ao, os v´ertices vizinhos de um v´ertice v1

qualquer s˜ao representados por uma lista de adjacˆencia. Em rela¸c˜ao `a abordagem anterior (Vers˜ao 1), esta economiza o uso de mem´oria. Al´em disso, a interse¸c˜ao realizada na linha 10 do Algoritmo 1, ´e feita de forma mais eficiente, visto que

12 Problema da Enumera¸c˜ao de Cliques com Peso acima de um Limiar

n˜ao ´e necess´ario percorrer toda a matriz para procurar a interse¸c˜ao dos v´ertices do conjunto P ou S com os v´ertices vizinhos do v´ertice v. Como desvantagem, o tempo gasto para verifica¸c˜ao da existˆencia de arco conectando dois v´ertices qualquer pode ser dispendioso (O(n)), sendo n a quantidade de v´ertices.

3. Uso de lista e matriz: esta terceira abordagem considera uma implementa¸c˜ao h´ıbrida, com o uso de lista e matriz (Vers˜oes1 e2). Nesse sentido, quando ocorre a verifica¸c˜ao de existˆencia de aresta entre dois v´ertices, ´e utilizada a matriz para esse fim. Quando o objetivo ´e realizar a interse¸c˜ao do conjunto P ou S com os v´ertices vizinhos do v´ertice v, a lista de adjacˆencia ´e utilizada.

4. Uso do conjunto P ordenado: na linha 8 do Algoritmo1, o v´ertice pivˆo u ´e escolhido a partir do v´ertice pertencente ao conjunto P com o m´aximo grau modificado. Uma quarta implementa¸c˜ao do Algoritmo de Bron-Kerbosch considera a otimiza¸c˜ao realizada com o uso de lista e matriz (Vers˜ao 3), acrescida da manuten¸c˜ao do conjunto P sempre ordenado, de modo a evitar percorrer todo esse conjunto quando ´e realizada a escolha do v´ertice pivˆo.

5. Uso do conjunto P \N (u) como vetor: esta vers˜ao modifica a forma de repre- senta¸c˜ao do conjunto P \N (u), usado na linha 9 do Algoritmo 1. Tal conjunto, que anteriormente era representado como uma lista encadeada na Vers˜ao 4, passa a ser representado como um vetor.

6. Pivoteamento 1: utiliza-se a ideia do m´aximo grau modificado, citado anterior- mente, por´em, o objetivo est´a em ordenar os v´ertices pelo m´aximo peso modificado. O conceito m´aximo peso modificado se refere ao somat´orio do peso do v´ertice com os pesos de todos os v´ertices adjacentes a ele.

7. Pivoteamento 2: faz uso da combina¸c˜ao entre peso e grau para sele¸c˜ao do v´ertice pivˆo. Nesse sentido, o Pivoteamento 2 ´e dado pela seguinte f´ormula: (m´aximo grau modificado * maior peso) + (m´aximo peso modificado). Os conceitos m´aximo grau modificado e m´aximo peso modificado j´a foram explicados. J´a o conceito maior peso refere-se ao peso do v´ertice de maior peso do grafo.

8. Pivoteamento 3: semelhante ao Pivoteamento 2, este pivoteamento ´e dado por (m´aximo grau modificado * menor peso) + (m´aximo peso modificado), onde menor peso refere-se ao peso do v´ertice de menor peso do grafo.

Problema da Enumera¸c˜ao de Cliques com Peso acima de um Limiar 13