Detecção de comunidades em grafos multicamada muito grandes

• Ano de defesa: 2011
• Autor(a) principal: Felipe Menezes Machado
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Minas Gerais; UFMG
• Palavras-chave em Português: redes complexas; Grafos multicamada; Teoria dos grafos; Computação; Redes complexas; Teoria das redes complexas
• Link de acesso: http://hdl.handle.net/1843/SLSS-8LWMYE

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.