CoChat
Sign Up
Cited by 937Complex Network Analysis TechniquesBioinformatics and Genomic NetworksAdvanced Clustering Algorithms Research

Performance of modularity maximization in practical contexts

Open access
Good, Benjamin H., de Montjoye, Yves-Alexandre, Clauset, Aaron·2010·Physical Review E
DOI 10.1103/physreve.81.046106
Open this paper in CoChat — free accountOpen PDF

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1103/physreve.81.046106

Cites

67 of 67 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • One recent study has shown that, even in relatively small networks, a large number of good solutions exist for the standard modularity criterion.

    “One recent study has shown that, even in relatively small networks, a large number of good solutions exist for the standard modularity criterion [51], [52].”

    From Spatial Guilds in the Serengeti Food Web Revealed by a Bayesian Group Model (2011) · cites this paper as [52]

  • A common method for dealing with near degeneracy of the modularity quality function is to examine statistics averaged over 100 repetitions of the optimization, with equal weight placed on each solution rather than only on unique solutions.

    “However, as of today, a common method for dealing with this degeneracy is to examine statistics averaged over the 100 repetitions of the optimization, with equal weight being placed on each solution, rather than just on the unique solutions.”

    From Dynamic reconfiguration of frontal brain networks during executive cognition in humans (2015) · cites this paper as [51]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 45

  1. [4]S. Allesina and M. Pascual, Ecology Letters 12 , 652 (2009).
  2. [7]A. Arenas, A. D´ ıaz-Guilera, and C. J. P´ erez-Vicente, Physical Review Letters 96 , 114102 (2006).
  3. [8]J. G. Restrepo, E. Ott, and B. R. Hunt, Physical Review Letters 97 , 094102 (2006).
  4. [13]A. H. Singh, D. M. Wolf, P. Wang, and A. P. Arkin, Proc. Natl. Acad. Sci. USA 105 , 7500 (2008).
  5. [15]A. W. Rives and T. Galitski, Proc. Natl. Acad. Sci. USA 100 , 1128 (2003).
  6. [16]V. Spirin and L. A. Mirny, Proc. Natl. Acad. Sci. USA 100 , 12123 (2003).
  7. [18]B. Karrer, E. Levina, and M. E. J. Newman, Physical Review E 77 , 046119 (2008).
  8. [19]S. Pinkert, J. Schultz, and J. Reichardt (2008), e-print, arXiv:0812.2184. · arXiv
  9. [22]U. Brandes, D. Delling, M. Gaertler, R. G¨ orke, M. Hoefer, Z. Nikoloski, and D. Wagner, IEEE Transactions on Knowledge and Data Engineering 20 , 172 (2008).
  10. [23]M. E. J. Newman, Physical Review E 69 , 066133 (2004).
  11. [24]A. Clauset, M. E. J. Newman, and C. Moore, Physical Review E 70 , 066111 (2004).
  12. [26]G. Agarwal and D. Kempe, European Physical Journal B 66 , 409 (2008).
  13. [27]M. E. J. Newman, Proc. Natl. Acad. Sci. USA 103 , 8577 (2006).
  14. [28]T. Richardson, P. J. Mucha, and M. A. Porter, Physical Review E 80 , 036111 (2009).
  15. [29]J. Duch and A. Arenas, Physical Review E 72 , 027104 (2005).
  16. [30]C. P. Massen and J. P. K. Doye (2006), e-print, arxiv:cond-mat/0610077. · arXiv
  17. [31]M. Sales-Pardo, R. Guimer´ a, A. A. Moreira, and L. A. N. Amaral, Proc. Natl. Acad. Sci. USA 104 , 15224 (2007).
  18. [32]S. Fortunato and M. Barth` elemy, Proc. Natl. Acad. Sci. USA 104 , 36 (2007).
  19. [33]A. Kreimer, E. Borenstein, U. Guphna, and E. Ruppin, Proc. Natl. Acad. Sci. USA 105 , 6976 (2008).
  20. [35]L. K. Branting, in Proc. 2nd Workshop on Social Network Mining and Analysis, at 14th ACM SIGKDD International Conf. on Knowledge Discovery and Data Mining (2008).
  21. [36]J. W. Berry, B. Hendrickson, R. A. LaViolette, and C. A. Phillips (2009), e-print, arXiv:0903.1072. · arXiv
  22. [37]J. Ruan and W. Zhang, Physical Review E 77 , 016104 (2008).
  23. [38]J. Reichardt and S. Bornholdt, Physical Review E 74 , 016110 (2006).
  24. [39]Z. Li, S. Zhang, R.-S. Wang, X.-S. Zhang, and L. Chen, Physical Review E 77 , 036109 (2008).
  25. [40]A. Arenas, A. Fern´ andez, and S. G´ omez, New Journal of Physics 10 , 053039 (2008).
  26. [42]A. Lancichinetti, F. Radicchi, and J. J. Ramasco (2009), e-print, arXiv:0907.3708. · arXiv
  27. [45]M. Girvan and M. E. J. Newman, Proc. Natl. Acad. Sci. USA 99 , 7821 (2002).
  28. [46]M. C. Lagomarsino, P. Jona, B. Bassetti, and H. Isambert, Proc. Natl. Acad. Sci. USA 104 , 5516 (2001).
  29. [48]P. J. Bickel and A. Chen, Proc. Natl. Acad. Sci. USA 106 , 21068 (2009).
  30. [50]M. Meil˘ a, in Proc. 22nd International Conference on Machine Learning (ICML) (2005), pp. 577-584.
  31. [54]A. Clauset, C. R. Shalizi, and M. E. J. Newman, SIAM Review 51 , 661 (2009).
  32. [56]A. Clauset, Physical Review E 72 , 026132 (2005).
  33. [58]E. Ziv, M. Middendorf, and C. H. Wiggins, Physical Review E 71 , 046117 (2005).
  34. [59]P. Pons and M. Latapy, Journal of Graph Algorithms and Applications 10 , 191 (2006).
  35. [60]M. Rosvall and C. T. Bergstrom, Proc. Natl. Acad. Sci. USA 105 , 1118 (2008).
  36. [61]R. Lambiotte, J.-C. Delvenne, and M. Barahona (2008), e-print, arXiv:0812.1770. · arXiv
  37. [62]M. Rosvall and C. T. Bergstrom, Proc. Natl. Acad. Sci. USA 104 , 7327 (2007).
  38. [63]M. E. J. Newman and E. A. Leicht, Proc. Natl. Acad. Sci. USA 104 , 9564 (2007).
  39. [64]J. M. Hofman and C. H. Wiggins, Physical Review Letters 100 , 258701 (2008).
  40. [65]E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing, Journal of Machine Learning Research 9 , 1981 (2008).
  41. [66]Y. J. Wang and G. Y. Wong, Journal of the American Statistical Association 82 , 8 (1987).
  42. [67]B. W. Kernighan and S. Lin, Bell Systems Technical Journal 49 , 291 (1970).
  43. [68]M. Stoer and F. Wagner, Journal of the ACM 44 , 585 (1997).
  44. [70]J. W. Sammon Jr., IEEE Transactions on Computers 100 , 401 (1969).
  45. [71]P. Demartines and J. Herault, in Proc. of 15th workshop GRETSI. Juan-Les-Pins France (1995).

Cited by

Sorted by citations

Related

Authors
Good, B. H., de Montjoye, Y.-A., & Clauset, A.
Affiliations
  • Swarthmore College (US)
  • Santa Fe Institute (US)
ORCID
Venue
Physical Review E
Publisher
American Physical Society (APS)
Published
2010-04-15
Volume
81
Issue
4
Pages
046106-046106
ISSN
  • 1539-3755 (ISSN-L)
  • 1550-2376
DOI
10.1103/physreve.81.046106
OpenAlex
W2061099285
Cited by
937
References
66
Citations by year
2026: 18 · 2025: 38 · 2024: 36 · 2023: 36 · 2022: 35 · 2021: 45 · 2020: 58 · 2019: 57 · 2018: 94 · 2017: 76 · 2016: 59 · 2015: 71 · 2014: 80 · 2013: 79 · 2012: 70
FWCI
52.48
Type
journal article
Language
en
Open access
Licence
link.aps.org/licenses/aps-default-license (vor)
Locations
  • Physical Review E (publishedVersion)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • Digital Access to Libraries (Université catholique de Louvain (UCL), l'Université de Namur (UNamur) and the Université Saint-Louis (USL-B)) (submittedVersion, other-oa)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Bioinformatics and Genomic Networks
  • Physical Sciences › Computer Science › Artificial Intelligence › Advanced Clustering Algorithms Research
Keywords
modularity optimization, resolution limit, network module identification, degenerate solutions, modularity function, metabolic networks, community detection
MeSH terms
Models, Theoretical

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review