Source-linked AI summary
Constrained Enumeration Reveals Hidden Optima and Precision-Dependent Degeneracy in Modularity-Based Community Detection
Fabio Morea
TL;DR
Modularity landscapes can contain many distinct, indistinguishable partitions, leaving unresolved whether heuristic runs reach the maximum and how many partitions attain it. The paper combines heuristic sampling to novelty saturation with core–fuzzy localisation and constrained enumeration. It reports higher optima and expanded plateau coverage beyond heuristic restarts, while showing that weight precision reshapes plateau geometry.
Problem
Modularity can assign indistinguishable scores to structurally distinct partitions, while repeated restarts leave unanswered whether Qmax has been reached and how many partitions attain it.
Source: §1 · p. 1Method
The workflow samples heuristic partitions until novelty saturates, locks stable core structure, and enumerates residual ambiguity using exact partition identity.
Source: §1 · p. 2, §2.1 · p. 2, §2.2 · p. 3Results
Constrained enumeration revealed higher optima and expanded plateau coverage beyond extensive heuristic restarts, while weight precision qualitatively reshaped plateau geometry.
Source: §1 · p. 2, §5 · p. 10, §4 · p. 10Takeaways & Limitations
Degenerate landscapes warrant reporting maximum modularity relative to a defensible baseline and the set and size of partitions on the top plateau or exceeding that baseline.
Source: §4 · p. 10The paper focuses on cases where Phase I suggests plateau-like multiplicity and motivates Phase II completion.
Source: §2.2 · p. 3
Abstract
from arXiv · showhide
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.
1 Introduction
Modularity maximisation is popular, but distinct partitions can have indistinguishable scores, complicating interpretation; it also has a resolution limit that can merge small communities. The paper addresses how to assess maximality and plateau size by localising ambiguity and enumerating the remaining possibilities.
1 Introduction
- Distinct partitions can attain indistinguishable modularity values, making a single best partition potentially an arbitrary representative; modularity can also merge well-defined small communities.The resulting questions are whether the maximum has been reached and how many distinct partitions share it.Source: §1 · p. 1
- Repeated heuristic restarts do not establish how many runs suffice to reach Qmax or whether it is shared by a plateau of distinct partitions.Exact optimisation is NP-hard, while practical analysis relies on heuristics such as Louvain [7] and Leiden [8].Source: §1 · p. 1
- Full-graph enumeration is infeasible because the partition space is combinatorially enormous and has no canonical geometry, motivating a viable combination of heuristics and exhaustive tools.Different similarity measures induce different, non-Euclidean structures.Source: §1 · pp. 1–2
- After heuristic exploration stabilises, the workflow locks stable structure and enumerates only residual ambiguity, addressing maximality and plateau cardinality through exact partition identity.This extends the authors’ Bayesian solution-space exploration framework.Source: §1 · p. 2
- Constrained enumeration can reveal higher-Q optima than extensive restarts, expand plateau coverage, and expose precision-dependent changes in plateau geometry.The contributions also frame plateau multiplicity as a stability diagnostic distinguishing core structure from fuzzy uncertainty.Source: §1 · p. 2
2 Methods
The methods combine exact partition identity with heuristic sampling until novelty saturates, then constrain enumeration to variable nodes while keeping stable core structure fixed.
2.1 Modularity and exact partition identity
- Weighted modularity is computed in an equivalent community-sum form, and partitions are deduplicated by exact restricted-growth-string encodings, invariant to label permutations.Two partitions count as identical only when their canonical encodings match exactly, with zero tolerance.Source: §2.1 · p. 2
2.2 Phase I: heuristic exploration with Bayesian saturation
- Phase I repeatedly runs a stochastic heuristic under random vertex permutations and stops when posterior novelty is low and its uncertainty is small.Novelty is modelled as Bernoulli with a Beta(1, 1) prior; the stopping rule uses credible quantiles, a novelty tolerance, and required interval tightness.Source: §2.2 · pp. 2–3
2.3 Phase II: core–fuzzy decomposition and constrained enumeration
- Phase II uses ensemble co-occurrence to identify stable core and ambiguous fuzzy nodes, decomposes the fuzzy subgraph into connected components, and enumerates assignments with core constraints locked.The paper focuses on Phase I ensembles suggesting plateau-like multiplicity; a representative partition supplies the locked core structure, while incremental modularity updates avoid full recomputation.Source: §2.3 · p. 3, §2.2 · p. 3
3 Experiments
The experiments apply a two-phase workflow: heuristic novelty saturation localizes uncertainty, then enumeration targets fuzzy components under a locked core. Across toy, synthetic, and real networks, this expands plateau coverage, while weight rounding reshapes plateau geometry.
3 Experiments
- The experiment workflow stops heuristic exploration at Bayesian novelty saturation, partitions nodes into stable core and fuzzy sets, decomposes the fuzzy subgraph, and enumerates feasible assignments under locked-core constraints.It evaluates candidates with incremental modularity updates and retains only those exceeding Qbench.Source: §3 · p. 4
3.1 Experiment 1: clique-ring toy example (methodology showcase)
- In the clique-ring toy example, instability concentrates on a small set of boundary nodes, and enumeration reveals additional plateau partitions even when heuristics reach Qmax.The stable core and fuzzy subset make the residual ambiguity visually interpretable.Source: §3.1 · p. 4, Figure 2 · p. 6
3.2 Experiment 2: noisy 50-clique benchmark (hidden optima beyond heuristic baselines)
- Constrained enumeration on the 50-clique benchmark reveals under-sampled high-Q partitions and hidden optima that can exceed extensive heuristic restarts.The reported candidates exceed Qbench, defined here as mean modularity over Phase I runs; the absolute gain can be small in plateau regimes.Source: §3.2 · pp. 4–5, Figure 3 · p. 6
3.3 Experiment 3: real weighted collaboration network (Horizon projects)
- On the real weighted collaboration network, enumeration adds top-plateau partitions and can reach higher modularity, while core–fuzzy separation yields a stable summary.The solution-space map also exposes competition between near-optimal community granularities, not only ties at a single modularity value.Source: §3.3 · p. 7, Figure 5 · p. 8, Figure 6 · p. 8
3.4 Experiment 4: weight precision reshapes plateau geometry
- Two-decimal rounding can merge near-ties into wide plateaus, whereas higher precision can split ties into a stratified ordering.The paper argues that if the data do not support fine precision, an apparent unique high-precision optimum may reflect micro-perturbations rather than meaningful structural distinctions.Source: Figure 7 · p. 9, §3.4 · p. 9
4 Discussion
In degenerate modularity landscapes, reporting should include the maximum modularity relative to a defensible baseline and the set and size of partitions on the top plateau. Constrained enumeration localises ambiguity under a locked stable core, while plateau structure can depend on weight precision.
4 Discussion
- Report the maximum modularity relative to a defensible baseline and the set and size of partitions attaining the top plateau or exceeding the baseline.A single partition and modularity value are insufficient for describing degenerate landscapes.Source: §4 · p. 10
- Locking stable structure and enumerating only the remaining ambiguity component-wise bridges stochastic exploration with local completeness.Full enumeration across the graph is infeasible.Source: §4 · p. 10
- When modularity differences are on the order of 10^-5, two- versus three-decimal weights can turn plateaus from true ties into arbitrary strict orderings.The discussion recommends treating weight precision as a modelling assumption and reporting plateau robustness under plausible precision regimes.Source: §4 · p. 10
- Although Phase I uses Louvain, the approach is presented as applicable to any stochastic community detector that produces an ensemble of partitions.Source: §4 · p. 10
5 Conclusion
The conclusion presents constrained enumeration as a complement to heuristic modularity optimisation: it can reveal higher optima, quantify plateau multiplicity, and provide stable summaries through core–fuzzy separation. It also highlights that plateau geometry depends on weight precision.
5 Conclusion
- Constrained enumeration can reveal higher optima than extensive heuristic restarts and quantify plateau multiplicity through core–fuzzy separation.The approach is presented as a practical and informative complement to heuristic modularity optimisation.Source: §5 · p. 10
- Plateau geometry depends on weight precision, making precision a modelling choice that matters when interpreting community-detection results.Source: §5 · p. 10