Statistical mechanics of community detection
Open accessAbstract
Starting from a general ansatz, we show how community detection can be interpreted as finding the ground state of an infinite range spin glass. Our approach applies to weighted and directed networks alike. It contains the ad hoc introduced quality function from [J. Reichardt and S. Bornholdt, Phys. Rev. Lett. 93, 218701 (2004)] and the modularity Q as defined by Newman and Girvan [Phys. Rev. E 69, 026113 (2004)] as special cases. The community structure of the network is interpreted as the spin configuration that minimizes the energy of the spin glass with the spin states being the community indices. We elucidate the properties of the ground state configuration to give a concise definition of communities as cohesive subgroups in networks that is adaptive to the specific class of network under study. Further, we show how hierarchies and overlap in the community structure can be detected. Computationally efficient local update rules for optimization procedures to find the ground state are given. We show how the ansatz may be used to discover the community around a given node without detecting all communities in the full network and we give benchmarks for the performance of this extension. Finally, we give expectation values for the modularity of random graphs, which can be used in the assessment of statistical significance of community structure.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
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?
The modules in Fig. 2 were obtained with the Louvain algorithm, and similar modules are obtained when spectral clustering is used.
“The modules in Fig. 2 were obtained with the Louvain algorithm for graph clustering38, which is designed to maximize modularity. Similar modules are obtained when spectral clustering39 is used”
From Predicting modular functions and neural coding of behavior from a synaptic wiring diagram (2024) · cites this paper as [38]
Cites
Social Network Analysis: Methods and Applications
Wasserman, S., & Faust, K. (1994) · doi:10.1017/cbo9780511815478 · Cited by 17,557 · see citing works
Finding and evaluating community structure in networks
Newman, M. E. J., & Girvan, M. (2004) · Physical Review E · doi:10.1103/physreve.69.026113 · Cited by 13,931 · see citing works
Information theory and statistical mechanics
Jaynes, E. T. (1957) · Physical Review · doi:10.1103/physrev.106.620 · Cited by 12,931 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293 · see citing works
From Louvain to Leiden: guaranteeing well-connected communities
Traag, V. A., Waltman, L., & van Eck, N. J. (2019) · Scientific Reports · doi:10.1038/s41598-019-41695-z · Cited by 5,635 · see citing works
Single-cell transcriptomics of 20 mouse organs creates a Tabula Muris
The Tabula Muris Consortium, coordination, O., coordination, L., processing, O. C. A., sequencing, L. P. A., analysis, C. D., annotation, C. T., Writing group, Supplemental text writing group, & Principal investigators (2018) · Nature · doi:10.1038/s41586-018-0590-4 · Cited by 3,326 · see citing works
Critical phenomena in complex networks
Dorogovtsev, S. N., Goltsev, A. V., & Mendes, J. F. F. (2008) · Reviews of Modern Physics · doi:10.1103/revmodphys.80.1275 · Cited by 2,220 · see citing works
Current best practices in single-cell RNA-seq analysis: a tutorial
Luecken, M. D., & Theis, F. J. (2019) · Molecular Systems Biology · doi:10.15252/msb.20188746 · Cited by 2,231 · see citing works
Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
Mucha, P. J., Richardson, T., Macon, K., Porter, M. A., & Onnela, J.-P. (2010) · Science · doi:10.1126/science.1184819 · Cited by 2,123 · see citing works
Comorbidity: a network perspective
Cramer, A. O. J., Waldorp, L. J., van der Maas, H. L. J., & Borsboom, D. (2010) · Behavioral and Brain Sciences · doi:10.1017/s0140525x09991567 · Cited by 1,575 · see citing works
Sporns, O., & Betzel, R. F. (2016) · Annual Review of Psychology · doi:10.1146/annurev-psych-122414-033634 · Cited by 1,334 · see citing works
Performance of modularity maximization in practical contexts
Good, B. H., de Montjoye, Y.-A., & Clauset, A. (2010) · Physical Review E · doi:10.1103/physreve.81.046106 · Cited by 937 · see citing works
Controllability of structural brain networks
Gu, S., Pasqualetti, F., Cieslak, M., Telesford, Q. K., Yu, A. B., Kahn, A. E., Medaglia, J. D., Vettel, J. M., Miller, M. B., Grafton, S. T., et al. (2015) · Nature Communications · doi:10.1038/ncomms9414 · Cited by 912 · see citing works
Mental Disorders as Causal Systems: A Network Approach to Posttraumatic Stress Disorder
McNally, R. J., Robinaugh, D. J., Wu, G. W. Y., Wang, L., Deserno, M. K., & Borsboom, D. (2015) · Clinical Psychological Science · doi:10.1177/2167702614553230 · Cited by 592 · see citing works
Single-nucleus and single-cell transcriptomes compared in matched cortical cell types
Bakken, T. E., Hodge, R. D., Miller, J. A., Yao, Z., Nguyen, T. N., Aevermann, B., Barkan, E., Bertagnolli, D., Casper, T., Dee, N., et al. (2018) · PLoS ONE · doi:10.1371/journal.pone.0209648 · Cited by 608 · see citing works
Dynamics and Control of Diseases in Networks with Community Structure
Salathé, M., & Jones, J. H. (2010) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1000736 · Cited by 586 · see citing works
Salathé, M., & Khandelwal, S. (2011) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1002199 · Cited by 530 · see citing works
Alexander-Bloch, A. F., Gogtay, N., Meunier, D., Birn, R., Clasen, L., Lalonde, F., Lenroot, R., Giedd, J., & Bullmore, E. T. (2010) · Frontiers in Systems Neuroscience · doi:10.3389/fnsys.2010.00147 · Cited by 480 · see citing works
Robust detection of dynamic community structure in networks
Bassett, D. S., Porter, M. A., Wymbs, N. F., Grafton, S. T., Carlson, J. M., & Mucha, P. J. (2013) · Chaos: An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/1.4790830 · Cited by 425 · see citing works
Task-Based Core-Periphery Organization of Human Brain Dynamics
Bassett, D. S., Wymbs, N. F., Rombach, M. P., Porter, M. A., Mucha, P. J., & Grafton, S. T. (2013) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1003171 · Cited by 356 · see citing works
Robustness of community structure in networks
Karrer, B., Levina, E., & Newman, M. E. J. (2008) · Physical Review E · doi:10.1103/physreve.77.046119 · Cited by 350 · see citing works
Betzel, R. F., Fukushima, M., He, Y., Zuo, X.-N., & Sporns, O. (2016) · NeuroImage · doi:10.1016/j.neuroimage.2015.12.001 · Cited by 249 · see citing works
Wiring cost and topological participation of the mouse brain connectome
Rubinov, M., Ypma, R. J. F., Watson, C., & Bullmore, E. T. (2015) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1420315112 · Cited by 219 · see citing works
Network analysis of persistent complex bereavement disorder in conjugally bereaved adults.
Robinaugh, D. J., LeBlanc, N. J., Vuletich, H. A., & McNally, R. J. (2014) · Journal of Abnormal Psychology · doi:10.1037/abn0000002 · Cited by 219 · see citing works
Heeren, A., & McNally, R. J. (2016) · Journal of Anxiety Disorders · doi:10.1016/j.janxdis.2016.06.009 · Cited by 170 · see citing works
Jiao, Y., Widschwendter, M., & Teschendorff, A. E. (2014) · Bioinformatics · doi:10.1093/bioinformatics/btu316 · Cited by 148 · see citing works
Detecting hierarchical genome folding with network modularity
Norton, H. K., Emerson, D. J., Huang, H., Kim, J., Titus, K. R., Gu, S., Bassett, D. S., & Phillips-Cremins, J. E. (2018) · Nature Methods · doi:10.1038/nmeth.4560 · Cited by 146 · see citing works
Malgaroli, M., Maccallum, F., & Bonanno, G. A. (2018) · Psychological Medicine · doi:10.1017/s0033291718001769 · Cited by 116 · see citing works
Spontaneous emergence of modularity in cellular networks
Solé, R. V., & Valverde, S. (2008) · Journal of The Royal Society Interface · doi:10.1098/rsif.2007.1108 · Cited by 102 · see citing works
Detecting heterogeneity in single-cell RNA-Seq data by non-negative matrix factorization
Zhu, X., Ching, T., Pan, X., Weissman, S. M., & Garmire, L. (2017) · PeerJ · doi:10.7717/peerj.2888 · Cited by 86 · see citing works
Comparing connectomes across subjects and populations at different scales
Meskaldji, D. E., Fischi-Gomez, E., Griffa, A., Hagmann, P., Morgenthaler, S., & Thiran, J.-P. (2013) · NeuroImage · doi:10.1016/j.neuroimage.2013.04.084 · Cited by 77 · see citing works
Scholtens, D. M., Bain, J. R., Reisetter, A. C., Muehlbauer, M. J., Nodzenski, M., Stevens, R. D., Ilkayeva, O., Lowe, L. P., Metzger, B. E., Newgard, C. B., et al. (2016) · Diabetes · doi:10.2337/db15-1748 · Cited by 69 · see citing works
Lohse, C., Bassett, D. S., Lim, K. O., & Carlson, J. M. (2014) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1003712 · Cited by 62 · see citing works
A network approach to hypersexuality: insights and clinical implications
Werner, M., Štulhofer, A., Waldorp, L., & Jurin, T. (2018) · The Journal of Sexual Medicine · doi:10.1016/j.jsxm.2018.01.009 · Cited by 58 · see citing works
Midha, A., Pan, H., Abarca, C., Andle, J., Carapeto, P., Bonner-Weir, S., & Aguayo-Mazzucato, C. (2021) · Diabetes · doi:10.2337/db20-0553 · Cited by 58 · see citing works
Reconfiguration of Cortical Networks in MDD Uncovered by Multiscale Community Detection with fMRI
He, Y., Lim, S., Fortunato, S., Sporns, O., Zhang, L., Qiu, J., Xie, P., & Zuo, X.-N. (2018) · Cerebral Cortex · doi:10.1093/cercor/bhx335 · Cited by 54 · see citing works
Magnetic eigenmaps for community detection in directed networks
Fanuel, M., Alaíz, C. M., & Suykens, J. A. K. (2017) · Physical Review E · doi:10.1103/physreve.95.022302 · Cited by 50 · see citing works
Does mindfulness change the mind? A novel psychonectome perspective based on Network Analysis
Roca, P., Diez, G. G., Castellanos, N., & Vazquez, C. (2019) · PLOS ONE · doi:10.1371/journal.pone.0219793 · Cited by 37 · see citing works
Jiang, X., Wu, Y., Zhang, K., Bőthe, B., Hong, Y., & Chen, L. (2022) · Journal of Behavioral Addictions · doi:10.1556/2006.2022.00065 · Cited by 31 · see citing works
Predicting modular functions and neural coding of behavior from a synaptic wiring diagram
Vishwanathan, A., Sood, A., Wu, J., Ramirez, A. D., Yang, R., Kemnitz, N., Ih, D., Turner, N., Lee, K., Tartavull, I., et al. (2024) · Nature Neuroscience · doi:10.1038/s41593-024-01784-3 · Cited by 25 · see citing works
Deserno, M. K., Bathelt, J., Groenman, A. P., & Geurts, H. M. (2023) · European Child & Adolescent Psychiatry · doi:10.1007/s00787-022-01986-9 · Cited by 22 · see citing works
Convergent Evolutionary Paths in Biological and Technological Networks
Solé, R. V., Valverde, S., & Rodriguez-Caso, C. (2011) · Evolution: Education and Outreach · doi:10.1007/s12052-011-0346-1 · Cited by 20 · see citing works
- Authors
- Reichardt, J., & Bornholdt, S.
- Affiliations
- University of Bremen (DE)
- Venue
- Physical Review E
- Publisher
- American Physical Society (APS)
- Published
- 2006-07-18
- Volume
- 74
- Issue
- 1
- Pages
- 016110-016110
- ISSN
- 1539-3755 (ISSN-L)
- 1550-2376
- OpenAlex
- W2025543856
- Cited by
- 2,048
- References
- 3
- Citations by year
- 2026: 71 · 2025: 115 · 2024: 112 · 2023: 130 · 2022: 155 · 2021: 169 · 2020: 157 · 2019: 122 · 2018: 136 · 2017: 136 · 2016: 116 · 2015: 100 · 2014: 93 · 2013: 101 · 2012: 78
- FWCI
- 22.07
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Physical Review E (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Opinion Dynamics and Social Influence
- Physical Sciences › Computer Science › Artificial Intelligence › Advanced Clustering Algorithms Research
- Keywords
- community detection, ground state, modularity, quality function, weighted networks, directed graphs, community structure, community hierarchy, random graphs, cohesive subgroups
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
