Dissertação

Fast hierarchical graph clustering EVALUATED

Este trabalho estuda como é que métodos de clustering de grafos (ou pesquisa de comunidades em grafos) podem ser usados para resolver problemas em grafos, tais como clustering hierárquico e reordenação. Neste contexto, explora-se como é que o Faststep, um método recente para factorização de matrizes e clustering de grafos, pode ser adaptado para resolver estes problemas. Desenvolveu-se um novo método, baseado no Faststep, e comparou-se o algoritmo proposto com métodos actuais de clustering: Layered Label Propagation e método de Louvain. Os resultados avaliaram-se num conjunto alargado de testes, incluido comparação com comunidades reais conhecidas, redes geradas por modelos aleatórios e comparação directa de algoritmos. Este estudo toma partido do Webgraph, uma ferramenta para representação sucinta de grafos, e explora como as comunidades podem ser usadas para melhorar as taxas de compressão obtidas. Concluiu-se que o Faststep, apesar de desenhado para resolver um problema diferente, pode ainda assim obter resultados aceitáveis neste. Mostrou-se também que o método de Louvain, um método de clustering hierárquico, pode de facto ser bastante promissor na tarefa de reordenação de grafos.
Ciência de Redes, Redes Complexas, Clustering de grafos, Clustering hierárquico de grafos, Compressão de grafos

Outubro 20, 2017, 10:30

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

Alexandre Paulo Lourenço Francisco

Departamento de Engenharia Informática (DEI)

Professor Auxiliar

ORIENTADOR

Pedro Manuel Pinto Ribeiro

Faculdade de Ciências da Universidade do Porto

Professor Auxiliar