Community detection by modularity maximization using GRASP with path relinking

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 l-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.