Performance of modularity maximization in practical contexts

Benjamin H. Good, Yves-Alexandre de Montjoye, Aaron ClausetPhysical 2010 · DOI · arXiv

Abstract: 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 Qmax 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.

Introduction

In network science, identifying "modules"—groups of nodes more densely connected to each other than to the rest of the network—is a fundamental task. The most prevalent method for this is maximizing the Modularity ($Q$) score. However, practitioners often encounter two significant issues: the "resolution limit," where small, distinct modules are merged into larger ones, and the inconsistency of results across different optimization algorithms. This research provides a rigorous characterization of why modularity behaves this way, revealing a "glassy" landscape dominated by a vast, rugged plateau of competitive solutions rather than a single clear peak.

The Resolution Limit and Network Structure

The resolution limit is a systematic deviation caused by the "random graph" null model inherent in the $Q$ formula. When the actual inter-module connectivity does not align with the null model's expectations, modularity maximization forces modules to merge, even when they are topologically distinct.

A ring network used to illustrate the resolution limit of modularity maximization, where small modules are often merged into larger ones by the algorithm.

Methods and Landscape Mapping

To understand the modularity function's behavior, the authors employed a multi-pronged approach:

  • Landscape Mapping: Using Simulated Annealing (SA) to sample the space of high-scoring partitions.
  • Distance Metrics: Utilizing Variation of Information (VI) to quantify the structural differences between partitions.
  • Visualization: Applying Curvilinear Component Analysis (CCA) to project the high-dimensional space of partitions into 3D landscapes, making the "ruggedness" of the modularity function visible.

Key Insights: Exponential Degeneracy

The study reveals that the modularity function $Q$ is "glassy," typically lacking a clear global maximum. Instead, it admits an exponential number of distinct high-scoring solutions. For a network with $k$ modules, there are at least $2^{k-1}$ competitive partitions. These "degenerate" solutions often fundamentally disagree on basic structural properties, such as the composition of the largest modules or the overall distribution of module sizes.

The modularity landscape Q for a metabolic network, visualized via CCA, showing extreme degeneracy and a rugged plateau of high-scoring solutions (yellow dots).

Empirical Results in Metabolic Networks

Testing these concepts on real-world metabolic networks (e.g., Treponema pallidum), the authors found that even when the largest modules are preserved, the remaining structural diversity can account for nearly 50% of the variation between partitions. This suggests that the "noise" in modularity maximization affects the core backbone of the identified structure, not just the periphery.

Conclusion

Modularity maximization is an "unforgiving" tool due to its sensitivity to sampling fluctuations and its reliance on a mean-field null model. The authors suggest that instead of searching for a single maximum, researchers should sample many high-scoring solutions to find a consensus or move toward more statistically principled generative approaches, such as Stochastic Block Models.

Summary updated

Abstract

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 Qmax 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.
BibTeX
@inproceedings{good2010performance,
  author = {Benjamin H. Good and Yves-Alexandre de Montjoye and Aaron Clauset},
  title = {{Performance of modularity maximization in practical contexts}},
  booktitle = {Physical},
  year = {2010},
  doi = {10.1103/physreve.81.046106},
}
Figure