Source-linked AI summary
Limits of modularity maximization in community detection
Andrea Lancichinetti, Santo Fortunato
TL;DR
Community detection commonly uses modularity maximization, but its resolution limit motivates tunable multiresolution variants. This paper analyzes their merger and splitting biases and tests them on heterogeneous benchmark networks, finding that no resolution value reliably recovers the planted partition.
Problem
Modularity's resolution limit motivates multiresolution variants, but heterogeneous networks contain clusters with widely varying sizes and no characteristic cluster scale.
Method
The paper analyzes merger and splitting conditions mathematically and tests multiresolution modularity on LFR benchmarks with power-law degree and community-size distributions.
Results
For every resolution parameter, benchmark graphs contain misclassifications from merging, splitting, or both, with at least 10% of vertices affected.
Takeaways & Limitations
Multiresolution modularity does not solve modularity maximization's practical partitioning problems, and the same issue extends to other multiresolution methods.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
Community detection is motivated by dense, functionally similar subgraphs, but modularity maximization has a resolution limit and multiresolution variants may not recover networks with heterogeneous cluster sizes.
- Communities are subgraphs whose vertices share features or functions and have higher internal-link density than the surrounding graph.
- Modularity is widely used to detect communities by measuring how cluster link density deviates from a null expectation.
- The resolution limit can systematically merge small, well-defined clusters into larger modules.
- Multiresolution modularity introduces a tunable parameter, but heterogeneous real-network cluster sizes lack a characteristic scale for tuning.
- The paper argues that multiresolution modularity can both merge small clusters and split large ones, making simultaneous avoidance difficult.
- Benchmark tests examine whether any resolution parameter recovers planted partitions in realistic community-structured graphs.
A. Multiresolution modularity
The paper analyzes when generalized modularity favors merging or separating two subgraphs, with λ controlling the balance between larger and smaller modules.
- The generalized modularity Qλ is adopted to analyze mathematical conditions governing the merger or split of subgraphs.
- Higher λ favors smaller modules because the resolution-dependent penalty becomes more important during modularity maximization.
- For a partition comparison, ΔQλ is the modularity of the merged partition minus that of the separated partition.
- The merger-versus-split decision depends on internal degrees and on links between A, B, and the rest of the network.
- Modularity favors merging A and B exactly when Δ > 0.
- The analysis specializes to cases with equal external connectivity, l = r = η, to make the relevant calculations tractable.
B. Splitting clusters
The splitting analysis asks when modularity avoids dividing random subgraphs while still separating loosely connected cliques, using analytical and numerical estimates of optimal bipartitions.
- B. Splitting clusters: A good community method should avoid splitting random graphs while separating loosely connected cliques.
- B. Splitting clusters: The analysis models a random subgraph S within a larger network and studies when modularity optimization splits it under bipartitions.
- B. Splitting clusters: For Q2 = 0, the expected number of links joining two arbitrarily chosen equal-size modules is v = MS/2.
- B. Splitting clusters: Figure 2 compares analytical Reichardt–Bornholdt estimates with simulated-annealing estimates on Erdős–Rényi and scale-free graphs.
- B. Splitting clusters: Optimizing modularity reduces expected links between bipartition modules relative to arbitrary equal-size bipartitions while increasing their internal link density.
- B. Splitting clusters: The analytical estimate of αS closely approximates numerical estimates across the tested graph types and remains essentially independent of λ.
- B. Splitting clusters: For a clique, αS is approximately 0.5, and modularity can split it under the stated condition.
C. Merging clusters
For two equal-sized subgraphs connected by one edge, modularity's preferred partition depends on the resolution threshold λC. Small ξC requires high resolution to separate the subgraphs, while large ξC permits separation across a wider λ range.
- C. Merging clusters: For two equal-sized subgraphs joined by one edge, separation requires ∆<0.The comparison is between modularity for merged and separated partitions.
- C. Merging clusters: When ξC is very small, λ must be very large to resolve the subgraphs.If λC > 1, standard modularity at λ = 1 cannot resolve them, recovering the resolution limit.
- C. Merging clusters: When ξC is large, the subgraphs are resolved for a large range of λ values.For two cliques of nC nodes, ξC = nC(nC −1).
D. Condition on the ineliminability of the bias
The paper combines thresholds for splitting random subgraphs and merging connected clusters, then tests their compatibility in a network of two cliques and one random subgraph. The analysis identifies parameter regimes where both biases cannot be avoided, with only a small safe region in the illustrative case.
- D. Condition on the ineliminability of the bias: Above λ1 modularity splits random subgraphs, whereas below λ2 it merges subgraphs connected by one link.Between λ1 and λ2, both biases should in principle be avoidable.
- D. Condition on the ineliminability of the bias: Eq. (21) is independent of the whole network's size in vertices or edges.The condition therefore concerns the relevant subgraphs rather than total graph scale.
- D. Condition on the ineliminability of the bias: The test network contains two identical cliques and one internally random subgraph, with each cluster pair connected by one edge.The random subgraph has nS vertices and average degree ⟨k⟩S; each clique has nC vertices.
- D. Condition on the ineliminability of the bias: Above the curves in the nS–nC plot, modularity cannot recover the right partition for any λ.The curves correspond to the equality λ1 = λ2 for selected values of ⟨k⟩S.
- D. Condition on the ineliminability of the bias: At sufficiently high λ, modularity can separate vertices of the random subgraph and eventually split it into nS clusters.The threshold is expressed using the minimum product of degrees over connected vertex pairs in the random subgraph.
- D. Condition on the ineliminability of the bias: If connected vertices in the random subgraph have degree product below (nC −1)(nC −2), no λ is suitable for recovering the intended partition.This condition is likely when the random subgraph has a broad degree distribution with many low-degree vertices.
- D. Condition on the ineliminability of the bias: For nC = 13 and ⟨k⟩S = 100, the region where both biases are absent is quite small.Figure 5 plots λ1 and λ2 against nS and includes exact and approximate λ1 curves.
III. TESTS ON BENCHMARK GRAPHS
LFR benchmark tests show that multiresolution methods cannot reliably recover heterogeneous planted communities: low resolution merges clusters, high resolution splits them, and no λ avoids both errors.
- Benchmark design: The LFR benchmark uses power-law degree and community-size distributions, with mixing parameter µ measuring the fraction of neighbors outside a vertex’s community.µ = 0 gives disconnected clusters, whereas µ = 1 gives no communities.
- Benchmark results: For small λ, modularity merges many clusters and essentially splits none; for large λ, splitting dominates merging.Across every λ, some misclassification results from merging, splitting, or both.
- Benchmark results: At least 10% of vertices remain affected for every λ, even with well-separated clusters at µ = 0.1 and 0.3.The situation does not improve when benchmark size increases from 10000 to 50000 vertices.
- Comparative analysis: RB and CPM can outperform Infomap and OSLOM when cluster sizes span less than one order of magnitude, but this advantage depends on narrow size variation.The comparison includes several multiresolution techniques on LFR benchmarks.
- Comparative analysis: With 10000 vertices and cluster sizes from 10 to 1000, multiresolution methods fail even at very low µ, while Infomap always detects the planted partition over the explored range.The failure is especially pronounced for the broader cluster-size distribution.
IV. CONCLUSIONS
The paper concludes that multiresolution modularity has concurrent merger and split biases that are often impossible to eliminate together. This failure persists across quality functions and complicates recovery of the real partition.
- Conclusions: Multiresolution modularity tends to merge small clusters and split large ones, making simultaneous avoidance of both biases difficult or impossible.Benchmark tests find substantial misclassification for every resolution parameter, even when clusters are well separated.
- Conclusions: Because errors include both merging and splitting, repairing modularity’s partition requires splitting some detected clusters and merging others.Determining which clusters contain smaller groups or belong to larger groups requires careful exploration of groups of clusters.
- Conclusions: The reported results extend to various quality functions, including the Constant Potts Model.The paper frames this as evidence that the issue is not restricted to one multiresolution modularity formulation.