Modularity maximization in networks by variable neighborhood search. (English) Zbl 1276.90055

Bader, David A. (ed.) et al., Graph partitioning and graph clustering. Proceedings of the 10th DIMACS implementation challenge workshop, Atlanta, GA, USA, February 13–14, 2012. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-9038-7/pbk; 978-0-8218-9869-7/ebook). Contemporary Mathematics 588, 113-127 (2013).
Summary: Finding communities or clusters, in networks, or graphs, has been the subject of intense studies in the last ten years. The most used criterion for that purpose, despite some recent criterions, is modularity maximization, proposed by Newman and Girvan. It consists in maximizing the sum for all clusters of the number of inner edges minus the expected number of inner edges assuming the same distribution of degrees. Numerous heuristics as well as a few exact algorithms have been proposed to maximize modularity. We apply the variable nighborhood search metaheuristic to that problem. Computational results are reported for the instances of the \(10^{\text{th}}\) DIMACS implementation challenge. The algorithm presented in this paper obtained the second prize in the quality modularity (sub-)challenge of the referred competitions, finding the best known solutions for 11 out of 30 instances.
For the entire collection see [Zbl 1262.05001].


90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
91C20 Clustering in the social and behavioral sciences