The performance of modularity maximization in practical contexts

Benjamin H. Good; Yves-Alexandre de Montjoye; Aaron Clauset

Source-linked AI summary

The performance of modularity maximization in practical contexts

Benjamin H. Good, Yves-Alexandre de Montjoye, Aaron Clauset

arXiv:0910.0165v2Oct 1, 2009physics.data-ancond-mat.dis-nnphysics.soc-phq-bio.MNq-bio.QM

TL;DR

Modularity maximization is widely used, but its practical accuracy and interpretability are not well understood. The paper combines analytic and numerical analyses to characterize resolution limits, degeneracy, size dependence, and partition disagreement. It finds that high-scoring solutions can be exponentially numerous and structurally diverse, so modularity-based outputs require cautious interpretation, with network size and module count limiting fair comparisons.

Problem
The practical quality and significance of modularity-maximization outputs remain insufficiently understood despite the method’s widespread use.
Method
The paper uses analytic and numerical techniques to study resolution limits, high-modularity degeneracy, maximum-modularity scaling, and structural variation in metabolic-network partitions.
Results
The study finds exponentially many structurally diverse near-optimal partitions, with substantial variation in module sizes and other structural properties.
Takeaways & Limitations
Partitions obtained by modularity maximization should be interpreted cautiously, particularly when networks are large or contain many module-like structures.
Takeaways & Limitations
Estimated Qmax is generally a lower bound whose accuracy depends on the algorithm and network, and its value is not fairly comparable across networks without controlling for network size.

Abstract

from arXiv · show

Although widely used in practice, the behavior and accuracy of the popular module identification technique called modularity maximization is not well understood in practical contexts. Here, we present a broad characterization of its performance in such situations. First, we revisit and clarify the resolution limit phenomenon for modularity maximization. Second, we show that the modularity function Q exhibits extreme degeneracies: it typically admits an exponential number of distinct high-scoring solutions and typically lacks a clear global maximum. Third, we derive the limiting behavior of the maximum modularity Q_max for one model of infinitely modular networks, showing that it depends strongly both on the size of the network and on the number of modules it contains. Finally, using three real-world metabolic networks as examples, we show that the degenerate solutions can fundamentally disagree on many, but not all, partition properties such as the composition of the largest modules and the distribution of module sizes. These results imply that the output of any modularity maximization procedure should be interpreted cautiously in scientific contexts. They also explain why many heuristics are often successful at finding high-scoring partitions in practice and why different heuristics can disagree on the modular structure of the same network. We conclude by discussing avenues for mitigating some of these behaviors, such as combining information from many degenerate solutions or using generative models.

I. INTRODUCTION

Modularity maximization is widely used to identify network modules, but its practical behavior is poorly understood. The paper characterizes resolution limits, degeneracy, size dependence, and disagreement among high-modularity partitions.

I. INTRODUCTION: Modularity maximization scores partitions by comparing observed within-module connectivity with a degree-sequence random-graph expectation.Higher Q indicates more internal connectivity than expected, and the optimal partition maximizes Q.
I. INTRODUCTION: The practical quality and significance of modularity-maximization outputs remain insufficiently characterized, despite widespread use and many successful heuristics.Most prior work emphasized developing detection methods rather than evaluating their performance in real-world settings.
I. INTRODUCTION: The paper finds exponentially many structurally diverse high-modularity solutions, whose differences can make scientific interpretations depend strongly on the selected partition.These solutions can disagree on properties such as largest-module composition and module-size distributions, creating a serious problem for scientific applications.
I. INTRODUCTION: The resolution limit can cause modularity to merge intuitively distinct modules when their observed inter-module connectivity exceeds the random-graph expectation.This effect arises because the expected connectivity decreases with network size, so even a single inter-module edge can favor merging in large unweighted networks.
I. INTRODUCTION: In a ring of k = 24 cliques with c = 5 nodes, modularity favors merging adjacent cliques into 2-clique tiles: Q2 = 0.8712 versus Q1 = 0.8674 for individual cliques.Above a network-size threshold k*, merging adjacent cliques produces a higher modularity score than the intuitive partition.
I. INTRODUCTION: The resolution limit depends on how inter-module connectivity scales with network size, not solely on the internal structure or total network weight.A weighted construction whose inter-module connectivity follows the null expectation avoids the resolution limit, whereas constant inter-module weights produce it.

B. A broader perspective

The broader perspective identifies limitations arising from modularity’s resolution behavior, null-model assumptions, and reliance on an external notion of intuitive modules. It also outlines algorithmic and modeling approaches that may mitigate these issues.

B. A broader perspective: For unweighted and many weighted networks, the resolution limit complicates direct interpretation of the optimal partition’s composition.Intuitively meaningful modules may be hidden within larger agglomerations that receive higher modularity scores.
B. A broader perspective: Divisive, agglomerative, multiscale, and edge-weighting methods may circumvent the resolution limit in some cases, but most remain incompletely characterized.Multiscale methods require choosing a target resolution, and binary divisions can leave residual problems.
B. A broader perspective: The random-graph null model can make unintuitive merges more likely because it permits edges from a module to connect to any node in the network.A more realistic null model for inter-module connectivity could reduce this problem.
B. A broader perspective: Sampling fluctuations can create apparent modular structure, especially in sparse networks where expected inter-module connectivity is below one edge.Edge reweighting or statistically significant interconnectivity criteria are suggested as possible ways to reduce this effect.
B. A broader perspective: Distinguishing optimal from intuitive partitions requires an external definition of what constitutes an intuitive module.The difficulty reflects the broader challenge of constructing a mathematical module definition that consistently matches intuition.

III. EXTREME DEGENERACY AMONG HIGH-MODULARITY PARTITIONS

Modularity maximization produces exponentially many near-optimal partitions because merging weakly connected groups incurs only small penalties, especially in modular and hierarchical networks. This degeneracy makes the optimum difficult to find and leaves the scientific meaning of any selected high-modularity partition uncertain.

Even when merging modules lowers Q, the penalty can be very small, allowing many structurally different partitions to remain competitive.As modular structures increase, the number of such combinations grows exponentially, making the global optimum harder to identify.
2^k−1 lower bound and the kth Bell number upper bound bracket the number of degenerate solutions for k modular groups.The lower bound arises in string networks, while the upper bound occurs when every group connects to every other group.
Sparse modular networks approach the lower degeneracy bound, whereas dense modular networks approach the upper bound.Intermediate degeneracy levels reflect varying degrees of inter-module connectivity.
Hierarchical networks: Hierarchical networks have at least as many degenerate solutions as simple modular networks, with alternative modularity scores that can be even closer.In balanced hierarchies, penalties depend on connectivity differences and become especially small for nearby or low-level groups.
Hierarchical networks: Resolution-limit-induced agglomerations can create hierarchy-style degeneracies even in networks without explicit hierarchical organization.These solutions arise whenever many node groups have relatively few inter-group connections.
The modularity function is not strongly peaked around its optimum on modular networks, leaving the scientifically meaningful partition unclear without external information.The number of structurally diverse alternatives can diminish the practical value of the optimum despite its existence.

IV. THE LIMITING BEHAVIOR OF Qmax FOR MODULAR NETWORKS

For an infinitely modular network model, the paper analyzes how the maximum modularity depends on network growth, module count, and resolution-limit agglomeration. Accounting for that agglomeration yields Qmax →1 as the number of modules grows, while comparisons across networks require matching structural expectations.

Qmax →1 as k →∞ when resolution-limit agglomeration makes average external degree negligible relative to average internal density.The result applies to the analyzed infinitely modular network model, not to every weighted-network limiting process.
The analysis assumes a sparse network with m = O(n), module size ⟨e⟩= O(1), and k = O(n) as new modular subgraphs are added.Under these assumptions, average external degree and average degree remain O(1), while the variance term vanishes asymptotically.
Without accounting for the resolution limit, Qmax approaches a constant below 1 determined by the relative proportions of internal and external edges.The paper identifies this as an incomplete analysis because optimal-module size may grow with network size.
Increasing n or k will generally increase Qmax, so modularity scores should not be compared across networks without accounting for network size and module count.The precise dependence also varies with network topology and how topology changes as n or k increases.
Extremely high Qmax values in very large real-world networks may reflect deviation from the degree-matched random-graph null model rather than especially strong modularity.The paper cites estimates of Qmax ≥0.984 and Qmax ≥0.979 for Web graphs with 118 million and 39 million nodes, respectively.

V. MAPPING THE MODULARITY LANDSCAPE

The paper reconstructs the modularity landscape by embedding sampled partitions and visualizing their modularity scores, revealing disagreement among high-modularity partitions.

The reconstruction maps sampled partitions into a low-dimensional space while preserving their pairwise distances as much as possible.Each embedded point receives the modularity score of its corresponding partition, enabling visualization of the modularity function.
High-modularity partitions of empirical networks can disagree strongly on many, but not all, partition properties.

A. The reconstruction technique

The reconstruction technique samples partitions, measures their variation of information, embeds them in two dimensions, and assigns modularity scores to expose rugged high-modularity regions.

Sampling and embedding: Simulated annealing samples both local optima and intermediate partitions by varying stopping points across independent runs.Runs begin from random initial partitions and stop either at randomly chosen steps or at local optima.
Sampling and embedding: Variation of information measures distances between partitions and supports quantitative tests of whether high-modularity solutions differ mainly in small ways.The same distance also enables low-dimensional visualization of the sampled modularity function.
Sampling and embedding: The embedding assigns partition coordinates to preserve pairwise distances, then uses each partition’s modularity score as a third dimension.Only relative positions in the embedding are meaningful; precise coordinates are not.
Synthetic and empirical landscapes: The Treponema pallidum metabolic network shows qualitatively the same rugged high-modularity structure as the hierarchical networks.The network’s largest connected component contains n = 482 nodes, and the reconstruction uses 1199 sampled partitions.
Synthetic and empirical landscapes: The ring network’s high-modularity partitions form a plateau with complicated internal degeneracies.The reconstruction uses k = 24, c = 5, and nearly 1000 sampled partitions.
Synthetic and empirical landscapes: The hierarchical model produces a rugged high-modularity region with many peaks and valleys and no clear global maximum.High-modularity partitions often mix submodules from different hierarchy levels and fail to resolve distinct branches.
Synthetic and empirical landscapes: Because curvilinear component analysis guarantees only a lower bound on ruggedness, the true modularity landscape is likely even more rugged than the visualization suggests.

VI. STRUCTURAL DIVERSITY AMONG HIGH-MODULARITY PARTITIONS

Across metabolic networks, high-modularity partitions can disagree on large-scale module composition and summary statistics, although some statistics are more representative than others.

Empirical networks: The empirical networks may differ from the synthetic models because real-world networks can have unequal module sizes and heavy-tailed degree distributions.
Empirical networks: Three metabolic networks exhibit broad, rugged high-modularity regions with no clear global maximum.
Large-scale similarity: The coarsening test evaluates large-scale agreement by retaining the k′ largest modules and merging all smaller modules.If distance remains substantial for small k′, partitions disagree on the composition of large modules.
Large-scale similarity: 0.05%: the mean pairwise distance for empirical partitions decreases by this amount when only the k′ = 9 largest groups are retained, versus 13% for the degree-matched random graph.
Large-scale similarity: Below 50%: the empirical mean pairwise distance falls below half its original value only after all but the k′ = 2 largest groups are merged.Almost half of the variation of information therefore remains in the two largest groups.
Large-scale similarity: High-modularity partitions can be far apart structurally despite having similar modularity scores, with disagreements concentrated in the largest identified modules.A high modularity score therefore provides little information about the underlying modular structure.
Structural summary statistics: Simulated-annealing partitions show more variance than Louvain partitions in mean module density and module-size distribution distances.This indicates that simulated annealing samples more of the structural diversity among high-modularity partitions.
Structural summary statistics: 1.421 ± 0.013 versus 1.520 ± 0.005: estimated mean module density for simulated annealing versus Louvain.

VII. DISCUSSION

The discussion identifies resolution limits, exponential degeneracy, and size-dependent Q_max as major problems, while recommending cautious interpretation and methods that integrate multiple solutions.

Three problems: The optimal partition may differ from the most intuitive partition because the assumed random inter-module connectivity creates a resolution limit.
Three problems: Typically, an exponential number of structurally diverse partitions have modularities very close to the optimum.The degeneracy problem extends to weighted, directed, bipartite, and multi-scale modularity variants.
Three problems: Q_max depends on network size n and the number of modules k.
Interpretation and algorithms: Different heuristics can return different partitions because they sample or target distinct subsets of the many high-modularity solutions.The effect is especially relevant for very large networks and deterministic algorithms that return a unique partition.
Interpretation and algorithms: High-modularity partitions or structural statistics should not be trusted as representative unless the optimization or sampling method is shown to find representative solutions.
Interpreting Q_max: Estimated Q_max is usually a lower bound whose accuracy depends on the algorithm and network, so values should not be compared across networks without controlling for size-related behavior.
Possible mitigations: Combining information from many high-modularity partitions, estimating statistical significance, and using generative models are proposed ways to mitigate degeneracy-related problems.Generative approaches include stochastic and hierarchical block models, though flexibility can increase computational costs and reduce interpretability.
Practical conclusion: Modularity maximization is likely to perform better on small networks with few non-hierarchical, non-overlapping modules; otherwise it may provide only a rough sketch of modular organization.

Appendix A: The dependence of Qmax on n for the ring network

For ring networks with k cliques, modularity’s maximum approaches one as network size grows, while the high-modularity plateau expands exponentially with the number of cliques. The analysis also describes simulated annealing procedures used to sample this partition landscape.

Qmax → 1 as n →∞ because the second and third terms in the ring-network expression vanish like O(1/√n).
2^k partitions arise by independently cutting or retaining each of the k edges connecting neighboring cliques.
For cliques with c ≥ 5 nodes, the intuitive partition’s ratio Q1/Qmax is 10/11 and remains within the plateau.
At least 2^k(1−1/ℓ) partitions with no more than ℓ cliques per module lie within 10% of maximum modularity.
As k grows, both plateau height and size increase, with plateau size increasing exponentially.
Simulated annealing proposes node moves, merges, or splits and accepts lower-modularity proposals with probability e−|∆Q|/T.

On the choice of move set and alternative algorithms

The authors deliberately compare two principled simulated-annealing move sets with Louvain because move-set design determines which regions of the modularity landscape algorithms can explore. Their metabolic-network test finds little overlap among the high-modularity partitions sampled by different heuristics.

Single-node and merge-split move sets are principled but not guaranteed optimal, and another move set might reduce the degeneracy problem.
Different heuristics implicitly use different move sets and may sample distinct high-modularity regions of the modularity function.
In the Treponema pallidum network, samples from Louvain, single-node, and merge-split methods were compared using pairwise variation of information distances.
The three heuristics’ high-modularity samples overlap very little, including the two simulated-annealing move sets, while sampled regions retain very high modularities.

Appendix C: The Distance Between Partitions

Variation of information provides a metric distance between network partitions and supports quantitative comparisons of their disagreement. The appendix also uses VI to visualize the modularity landscape and test whether high-modularity alternatives differ only trivially.

Variation of information satisfies standard metric axioms and can be computed efficiently without maximally aligning overlapping groups.
VI quantifies whether suboptimal high-modularity partitions differ from an optimum only through small or trivial changes.
The distance can be simplified using group sizes ni, nj, and joint counts ni,j.
Two partitions are identical exactly when VI(C, C′) = 0, while the maximum possible VI is log n.

Two example calculations using VI

Examples show how VI responds to node displacements, merges, and splits, while Jaccard distance provides a robustness check for the reconstructed modularity landscape. CCA then embeds partition distances into a two-dimensional landscape while prioritizing local structure.

Two example calculations using VI: Merges and splits produce larger VI distances than displacing only a few nodes, matching the expected disagreements among suboptimal high-modularity partitions.
Two example calculations using VI: VI distances cannot be reliably compared across networks with different sizes or module counts, so the analysis uses only within-network relative distances.
Alternative distance measures: Jaccard distance reproduces the qualitative rugged high-modularity plateau and similar coarse-graining results found with VI.
Curvilinear Component Analysis: CCA projects pairwise partition distances into two-dimensional latent space, preserving local distances while allowing distortion at larger distances.

Appendix E: Hierarchical Random Graphs

The simplified HRG model fixes a balanced binary hierarchy and makes connection probabilities increase toward the leaves, producing assortative structure with denser lower-level modules.

Model construction: The model arranges n = 2^dmax nodes in a balanced binary tree with dmax + 1 levels.The hierarchy is fixed rather than inferred as part of the model.
Model construction: Connection probabilities increase with distance from the root, so modules become denser lower in the dendrogram.This regularity gives the generated network an assortative structure.
Model construction: The model assigns edge probabilities according to the level of the lowest common ancestor of each node pair.The probability rule is expressed in the model through the corresponding level-dependent probability equation.

The optimal partition of a hierarchical network

The analysis identifies the hierarchy level that maximizes average modularity in a balanced assortative network and examines how resolution limits and modularity degeneracy appear in metabolic networks.

The optimal partition of a hierarchical network: Symmetry forces the optimal partition to contain equal-sized groups, reducing the search to selecting the hierarchy level d* that maximizes average modularity.The derivation uses a mean-field average over network instances from the simplified HRG model.
The optimal partition of a hierarchical network: As the network grows, the resolution limit moves the optimal level upward and makes the optimal partition aggregate smaller modules into hierarchical agglomerations.In this model, the agglomerations consist of modules from lower levels of the hierarchy.
Additional metabolic networks: High-modularity partitions of Mycoplasma pneumoniae and Ureaplasma parvum show substantial degeneracy, including variation in the composition of their largest modules.The reconstructed modularity functions use 1199 sampled partitions for each network.
Additional metabolic networks: Across the three metabolic networks, merging all but the largest groups does not eliminate non-trivial distances because partitions with k ≤9 groups are insufficiently common.The coarsening analyses therefore indicate that degeneracy extends beyond rearrangements of the smallest modules.
Additional metabolic networks: The fraction of retained mean pairwise variation of information is not guaranteed to decrease monotonically as more groups are retained.The paper explains this with a distance decomposition involving within-region and between-region contributions.