Detecção de comunidades em grafos multicamada muito grandes

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.