Full-text links:
Download:
- Other formats
Current browse context:
physics.data-an
< prev | next >
new | recent | 0910
Change to browse by:
cond-mat
cond-mat.dis-nn
physics
physics.soc-ph
q-bio
q-bio.MN
q-bio.QM
cond-mat.dis-nn
physics
physics.soc-ph
q-bio
q-bio.MN
q-bio.QM
References & Citations
- NASA ADS
5 blog links
(what is this?)Bookmark
(what is this?)Physics > Data Analysis, Statistics and Probability
Title: The performance of modularity maximization in practical contexts
Authors:
Benjamin H. Good,
Yves-Alexandre de Montjoye,
Aaron Clauset
(Submitted on 1 Oct 2009 (v1), last revised 1 Apr 2010 (this version, v2))
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 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.
Comments: | 20 pages, 14 figures, 6 appendices; code available at this http URL |
Subjects: | Data Analysis, Statistics and Probability (physics.data-an); Disordered Systems and Neural Networks (cond-mat.dis-nn); Physics and Society (physics.soc-ph); Molecular Networks (q-bio.MN); Quantitative Methods (q-bio.QM) |
Journal reference: | Phys. Rev. E 81, 046106 (2010) |
DOI: | 10.1103/PhysRevE.81.046106 |
Cite as: | arXiv:0910.0165 [physics.data-an] |
(or arXiv:0910.0165v2 [physics.data-an] for this version) |
Submission history
From: Aaron Clauset [view email][v1] Thu, 1 Oct 2009 13:06:41 GMT (1542kb,D)
[v2] Thu, 1 Apr 2010 10:44:26 GMT (1234kb,D)
Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)