Dissertação

{pt_PT=Fast hierarchical graph clustering} {} EVALUATED

{pt=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., en=This work studies how graph clustering methods can be used to solve other graph problems, such as hierarchical clustering and graph reordering. In this context, it explores how Faststep, a recent method for matrix factorization and graph clustering, can be adapted to solve these other problems. Our study develops a new method for this task, based on Faststep, and compares the proposed algorithm with state-of-the-art clustering methods: Layered Label Propagation and Louvain method. The results obtained are evaluated by several tests, which include comparison with ground-truth communities, networks generated by random models and direct comparison of algorithms. This study takes also advantage of Webgraph, a framework for succinct representation of graphs, and explores how clustering can be a powerful tool to improve the compression rates. We conclude that Faststep, although designed to solve a different problem, can still obtain acceptable results for this one. We also show that Louvain method, a hierarchical clustering method, can in fact obtain really promising results in the graph reordering task.}
{pt=Ciência de Redes, Redes Complexas, Clustering de grafos, Clustering hierárquico de grafos, Compressão de grafos, en=Network Science, Graph Clustering, Hierarchical Graph Clustering, Graph Compression}

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