Please use this identifier to cite or link to this item: http://hdl.handle.net/1843/SLSS-8LWMYE
Type: Dissertação de Mestrado
Title: Detecção de comunidades em grafos multicamada muito grandes
Authors: Felipe Menezes Machado
First Advisor: Virgilio Augusto Fernandes Almeida
First Referee: Wagner Meira Junior
Second Referee: Renato Antonio Celso Ferreira
Abstract: Vários trabalhos foram desenvolvidos na última década no campo de comunidades em grafos. No entanto, só recentemente foi desenvolvido o primeiro trabalho sobre comunidades em grafos multicamada (grafos com vários tipos de aresta) mas ainda com limitações quanto ao tamanho do grafo.Nesse trabalho apresentamos um novo algoritmo que faz o particionamento em comunidades de grafos multicamada muito grandes. Partindo de uma fórmula desenvolvida recentemente para a modularidade de grafos multicamada, multiresolução e dependentes do tempo, nós derivamos uma fórmula mais simples somente para grafos multicamada. Então nós modificamos um algoritmo guloso bem conhecido para detecção de comunidades em grafos, para chegar a um novo algoritmo que nos dá melhores resultados de modularidade multicamada. Resultados experimentais nos mostram que podemos atingir melhores resultados para modularidade multicamada com uma perda de eficiência da ordem da multiplicidade do grafo.
Abstract: Many studies have been developed in the last decade in the field of communities in graphs, with a great variety of definitions, analysis and techniques developed. However, only recently the first work about communities in multiplex graphs (graphs with many types of edges) has been published. The techniques used in this study do not allow for use with very large graphs (in the order of millions of vertexes and edges), and therefore there isnt yet a method that allows for detection of communities in very large multiplex networks.In this work we present such an algorithm, one that partitions large multiplex graphs in communities. Starting from a recently developed modularity formula for mul- tiplex, multi-resolution and time-dependent graphs, we come up with a simpler formula for multiplex networks, with some simplifications. Then, based on the structure of the simpler formula, we modify a well-known greedy algorithm for community detection based on modularity, to come up with a new algorithm that gives us better results of multiplex modularity when applied to this type of graphs. Experimental results shows us that we can achieve better results of multiplex modularity with a loss of performance in the order of the multiplex graph multiplicity. We then conclude that the algorithm is viable for very large graphs, and can be used to analyze existing complex networks with better results than with the algorithms found in the literature.
Subject: Teoria dos grafos
Computação
Redes complexas
Teoria das redes complexas
language: Português
Publisher: Universidade Federal de Minas Gerais
Publisher Initials: UFMG
Rights: Acesso Aberto
URI: http://hdl.handle.net/1843/SLSS-8LWMYE
Issue Date: 19-Sep-2011
Appears in Collections:Dissertações de Mestrado

Files in This Item:
File Description SizeFormat 
felipemenezesmachado.pdf2.15 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.