Performance of modularity maximization in practical contexts

Benjamin H. Good, Yves-Alexandre de Montjoye, and Aaron Clauset
Phys. Rev. E 81, 046106 – Published 15 April 2010

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.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
7 More
  • Received 1 October 2009

DOI:https://doi.org/10.1103/PhysRevE.81.046106

©2010 American Physical Society

Authors & Affiliations

Benjamin H. Good1,2,*, Yves-Alexandre de Montjoye3,2,†, and Aaron Clauset2,‡

  • 1Department of Physics, Swarthmore College, Swarthmore, Pennsylvania 19081, USA
  • 2Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA
  • 3Department of Applied Mathematics, Université Catholique de Louvain, 4 Avenue Georges Lemaitre, B-1348 Louvain-la-Neuve, Belgium

  • *conkerll@gmail.com
  • yvesalexandre@demontjoye.com
  • aaronc@santafe.edu

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 81, Iss. 4 — April 2010

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×