Modularity method finds many similar network groups and improves precision
Constrained Enumeration Reveals Hidden Optima and Precision-Dependent Degeneracy in Modularity-Based Community Detection
Social and Information Networks
Summary
Finding groups in networks often leads to many equally good answers, making it hard to know the best. The authors developed a method that first samples many groupings until no new ones appear, then focuses on a small uncertain part to explore all possibilities there. This approach finds more, and sometimes better, groupings than existing popular methods. They also found that rounding edge weights changes which groupings appear, showing that how precise the data is can affect results.
What this means in practice
- •For network analysts: Identify distinct but similarly scored community structures in complex networks by systematically examining uncertain nodes after initial clustering.
- •For data quality engineers: Assess how rounding or precision changes in edge weights affect the detection of network communities and optimize data preprocessing accordingly.
Authors
Fabio Morea
Abstract
Modularity landscapes are often flat near the top: many distinct partitions achieve indistinguishable scores, and repeated runs of heuristic algorithms can still miss accessible optima. We introduce a two-phase workflow that (i) samples partitions until novelty saturates, then (ii) localises instability to a small subset of nodes and enumerates only that residual ambiguity under a locked stable core. Across a simple 50-nodes benchmark network, and a real weighted collaboration network, constrained enumeration systematically expands plateau coverage and can improve modularity beyond extensive Louvain restarts. Finally, we show that edge-weight rounding qualitatively reshapes plateau structure, making precision sensitivity an essential part of solution-space reporting.