Finite-state parameter space maps for pruning partitions in modularity-based community detection
Authors:
Open Access
- 23 September 2022
- journal article
- research article
- Published by Springer Nature in Scientific Reports
- Vol. 12 (1) , 1-13
Abstract
Partitioning networks into communities of densely connected nodes is an important tool used widely across different applications, with numerous methods and software packages available for community detection. Modularity-based methods require parameters to be selected (or assume defaults) to control the resolution and, in multilayer networks, interlayer coupling. Meanwhile, most useful algorithms are heuristics yielding different near-optimal results upon repeated runs (even at the same parameters). To address these difficulties, we combine recent developments into a simple-to-use framework for pruning a set of partitions to a subset that are self-consistent by an equivalence with the objective function for inference of a degree-corrected planted partition stochastic block model (SBM). Importantly, this combined framework reduces some of the problems associated with the stochasticity that is inherent in the use of heuristics for optimizing modularity. In our examples, the pruning typically highlights only a small number of partitions that are fixed points of the corresponding map on the set of somewhere-optimal partitions in the parameter space. We also derive resolution parameter upper bounds for fitting a constrained SBM of K blocks and demonstrate that these bounds hold in practice, further guiding parameter space regions to consider. With publicly available code (http://github.com/ragibson/ModularityPruning), our pruning procedure provides a new baseline for using modularity-based community detection in practice.Keywords
All Related Versions
Funding Information
- James S. McDonnell Foundation,United States (220020315)
- National Science Foundation (BCS-2140024)
- Army Research Office (W911NF-18-1-0244)
This publication has 30 references indexed in Scilit:
- Multilayer networksJournal of Complex Networks, 2014
- Stochastic blockmodels and community structure in networksPhysical Review E, 2011
- Community Structure in Time-Dependent, Multiscale, and Multiplex NetworksScience, 2010
- Performance of modularity maximization in practical contextsPhysical Review E, 2010
- Community detection in graphsPhysics Reports, 2010
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- Analysis of the structure of complex networks at different resolution levelsNew Journal of Physics, 2008
- Resolution limit in community detectionProceedings of the National Academy of Sciences, 2007
- Statistical mechanics of community detectionPhysical Review E, 2006
- The quickhull algorithm for convex hullsACM Transactions on Mathematical Software, 1996