Limits of modularity maximization in community detection
Authors:
Top Cited Papers
- 27 December 2011
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 84 (6) , 066122
Abstract
Modularity maximization is the most popular technique for the detection of community structure in graphs. The resolution limit of the method is supposedly solvable with the introduction of modified versions of the measure, with tunable resolution parameters. We show that multiresolution modularity suffers from two opposite coexisting problems: the tendency to merge small subgraphs, which dominates when the resolution is low; the tendency to split large subgraphs, which dominates when the resolution is high. In benchmark networks with heterogeneous distributions of cluster sizes, the simultaneous elimination of both biases is not possible and multiresolution modularity is not capable to recover the planted community structure, not even when it is pronounced and easily detectable by other methods, for any value of the resolution parameter. This holds for other multiresolution techniques and it is likely to be a general problem of methods based on global optimization.Keywords
All Related Versions
This publication has 33 references indexed in Scilit:
- Community detection in graphsPhysics Reports, 2010
- Dynamical Processes on Complex Networks2008
- Scale-Free Networks2007
- Complex networks: Structure and dynamicsPhysics Reports, 2006
- Finding and evaluating community structure in networksPhysical Review E, 2004
- Evolution and Structure of the Internet2004
- The Structure and Function of Complex NetworksSIAM Review, 2003
- Community structure in social and biological networksProceedings of the National Academy of Sciences, 2002
- Evolution of networksAdvances in Physics, 2002
- Statistical mechanics of complex networksReviews of Modern Physics, 2002