Community detection by modularity maximization using GRASP with path relinking

摘要

Complex systems in diverse areas such as biology, sociology and physics are frequently being modelled as graphs, that provide the mathematical framework upon which small scale dynamics between the fundamental elements of the system can reveal large scale system behavior. Community structure in a graph is an important large scale characteristic, and can be described as a natural division of the vertices into densely connected groups, or clusters. Detection of community structure remains up to this date a computationally challenging problem despite the efforts of many researchers from various scientific fields in the past few years. The modularity value of a set of vertex clusters in a graph is a widely used quality measure for community structure, and the relating problem of finding a partition of the vertices into clusters such that the corresponding modularity is maximized is an NP-Hard problem. In this paper we present a Greedy Randomized Adaptive Search Procedure (GRASP) with path relinking, for solving the modularity maximization problem in weighted graphs. A class of {0,1} matrices is introduced that characterizes the family of clusterings in a graph, and a distance function is given that enables us to define an (-neighborhood local search, which generalizes most of the related local search methods that have appeared in the literature. Computational experiments comparing the proposed algorithm with other heuristics from the literature in a set of artificially generated graphs and some well known benchmark instances, indicate that our implementation of GRASP with path relinking consistently produces better quality solutions.