Back

G-2011-15

A Locally Optimal Heuristic for Modularity Maximization of Networks

, , and

BibTeX reference

Community detection in networks based on modularity maximization is currently done with hierarchical divisive or agglomerative as well as with partitioning heuristics, hybrids and, in a few papers, exact algorithms. We consider here the case of hierarchical networks in which communities should be detected and propose a divisive heuristic which is locally optimal in the sense that each of the successive bipartitions is done in a provably optimal way. This heuristic is compared with the spectral-based hierarchical divisive heuristic of Newman [Proceedings of the National Academy of Sciences, USA 103, 8577 (2006)] and with the hierarchical agglomerative heuristic of Clauset, Newman and Moore [Phys. Rev. E 70, 066111 (2004)]. Computational results are given for a series of problems of the literature with up to 4941 vertices and 6594 edges. They show that the proposed divisive heuristic gives better results than the divisive heuristic of Newman and than the agglomerative heuristic of Clauset et al.

, 17 pages

Research Axis

Research applications

Publication

, , and
Physical Review E, 83(5), page 056105, 2011 BibTeX reference