The DOI matches its Crossref record; 55 of the 55 references it cites were found in a registry or an index.
Community detection algorithms: A comparative analysis
Open accessAbstract
Uncovering the community structure exhibited by real networks is a crucial step toward an understanding of complex systems that goes beyond the local organization of their constituents. Many algorithms have been proposed so far, but none of them has been subjected to strict tests to evaluate their performance. Most of the sporadic tests performed so far involved small networks with known community structure and/or artificial graphs with a simplified structure, which is very uncommon in real systems. Here we test several methods against a recently introduced class of benchmark graphs, with heterogeneous distributions of degree and community size. The methods are also tested against the benchmark by Girvan and Newman [Proc. Natl. Acad. Sci. U.S.A. 99, 7821 (2002)] and on random graphs. As a result of our analysis, three recent algorithms introduced by Rosvall and Bergstrom [Proc. Natl. Acad. Sci. U.S.A. 104, 7327 (2007); Proc. Natl. Acad. Sci. U.S.A. 105, 1118 (2008)], Blondel [J. Stat. Mech.: Theory Exp. (2008), P10008], and Ronhovde and Nussinov [Phys. Rev. E 80, 016109 (2009)] have an excellent performance, with the additional advantage of low computational complexity, which enables one to analyze large systems.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Maximum Likelihood from Incomplete Data Via the EM Algorithm
Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1977.tb01600.x · Cited by 50,444
Collective dynamics of ‘small-world’ networks
Watts, D. J., & Strogatz, S. H. (1998) · Nature · doi:10.1038/30918 · Cited by 43,060
Fast unfolding of communities in large networks
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E. (2008) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2008/10/p10008 · Cited by 21,424
The Structure and Function of Complex Networks
Newman, M. E. J. (2003) · SIAM Review · doi:10.1137/s003614450342480 · Cited by 18,719
Community structure in social and biological networks
Girvan, M., & Newman, M. E. J. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.122653799 · Cited by 15,502
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
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293
Self-citationComplex networks: structure and dynamics
BOCCALETTI, S., LATORA, V, MORENO, Y., CHAVEZ, M., & HWANG, D. (2006) · Physics Reports · doi:10.1016/j.physrep.2005.10.009 · Cited by 11,010
Finding community structure in very large networks
Clauset, A., Newman, M. E. J., & Moore, C. (2004) · Physical Review E · doi:10.1103/physreve.70.066111 · Cited by 7,390
Network motifs: simple building blocks of complex networks.
Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., & Alon, U. (2002) · Science · doi:10.1126/science.298.5594.824 · Cited by 7,368
Cited by
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293
Self-citationFrom 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
“It was found to be one of the fastest and best performing algorithms in comparative analyses 11,12 , and it is one of the most-cited works in the community detection literature.”
BackgroundMethodFunctional Network Organization of the Human Brain
Power, J. D., Cohen, A. L., Nelson, S. M., Wig, G. S., Barnes, K. A., Church, J. A., Vogel, A. C., Laumann, T. O., Miezin, F. M., Schlaggar, B. L., et al. (2011) · Neuron · doi:10.1016/j.neuron.2011.09.006 · Cited by 4,124
Newman, M. (2018) · doi:10.1093/oso/9780198805090.001.0001 · Cited by 2,297
Community detection in networks: a user guide
Fortunato, S., & Hric, D. (2016) · Physics Reports · doi:10.1016/j.physrep.2016.09.002 · Cited by 2,086
Self-citationLink communities reveal multiscale complexity in networks
Ahn, Y.-Y., Bagrow, J. P., & Lehmann, S. (2010) · Nature · doi:10.1038/nature09182 · Cited by 1,949
Leskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2009) · Internet Mathematics · doi:10.1080/15427951.2009.10129177 · Cited by 1,872
Sporns, O., & Betzel, R. F. (2016) · Annual Review of Psychology · doi:10.1146/annurev-psych-122414-033634 · Cited by 1,334
Finding Statistically Significant Communities in Networks
Lancichinetti, A., Radicchi, F., Ramasco, J. J., & Fortunato, S. (2011) · PLoS ONE · doi:10.1371/journal.pone.0018961 · Cited by 1,187
Self-citationChallenges in unsupervised clustering of single-cell RNA-seq data
Kiselev, V. Y., Andrews, T. S., & Hemberg, M. (2019) · Nature Reviews Genetics · doi:10.1038/s41576-018-0088-9 · Cited by 1,160
Microbial Interkingdom Interactions in Roots Promote Arabidopsis Survival
Durán, P., Thiergart, T., Garrido-Oter, R., Agler, M., Kemen, E., Schulze-Lefert, P., & Hacquard, S. (2018) · Cell · doi:10.1016/j.cell.2018.10.020 · Cited by 1,037
Overlapping community detection in networks: The state-of-the-art and comparative study
Xie, J., Kelley, S., & Szymanski, B. K. (2013) · ACM Computing Surveys · doi:10.1145/2501654.2501657 · Cited by 930
Empirical comparison of algorithms for network community detection
Leskovec, J., Lang, K. J., & Mahoney, M. (2010) · Proceedings of the 19th international conference on World wide web · doi:10.1145/1772690.1772755 · Cited by 918
The Role of Gender in Scholarly Authorship
West, J. D., Jacquet, J., King, M. M., Correll, S. J., & Bergstrom, C. T. (2013) · PLoS ONE · doi:10.1371/journal.pone.0066212 · Cited by 892
Overlapping Community Detection in Networks: the State of the Art and Comparative Study
Xie, J., Kelley, S., & Szymanski, B. K. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1110.5813 · Cited by 865
A Comprehensive Survey on Graph Anomaly Detection With Deep Learning
Ma, X., Wu, J., Xue, S., Yang, J., Zhou, C., Sheng, Q. Z., Xiong, H., & Akoglu, L. (2023) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2021.3118815 · Cited by 835
Hallquist, M. N., Hwang, K., & Luna, B. (2013) · NeuroImage · doi:10.1016/j.neuroimage.2013.05.116 · Cited by 753
Finding overlapping communities in networks by label propagation
Gregory, S. (2010) · New Journal of Physics · doi:10.1088/1367-2630/12/10/103018 · Cited by 806
Consensus clustering in complex networks
Lancichinetti, A., & Fortunato, S. (2012) · Scientific Reports · doi:10.1038/srep00336 · Cited by 795
Self-citationCommunities, modules and large-scale structure in networks
Newman, M. E. J. (2012) · Nature Physics · doi:10.1038/nphys2162 · Cited by 787
Decelle, A., Krzakala, F., Moore, C., & Zdeborová, L. (2011) · Physical Review E · doi:10.1103/physreve.84.066106 · Cited by 747
A Comparative Analysis of Community Detection Algorithms on Artificial Networks
Yang, Z., Algesheimer, R., & Tessone, C. J. (2016) · Zurich Open Repository and Archive (University of Zurich) · doi:10.5167/uzh-127494 · Cited by 685
Hierarchical modularity in human brain functional networks
Meunier, D. (2009) · Frontiers in Neuroinformatics · doi:10.3389/neuro.11.037.2009 · Cited by 667
Jusup, M., Holme, P., Kanazawa, K., Takayasu, M., Romić, I., Wang, Z., Geček, S., Lipić, T., Podobnik, B., Wang, L., et al. (2022) · Physics Reports · doi:10.1016/j.physrep.2021.10.005 · Cited by 643
Community detection in Social Media: Performance and application considerations
Papadopoulos, S., Kompatsiaris, Y., Vakali, A., & Spyridonos, P. (2012) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-011-0224-z · Cited by 615
Tradition and Innovation in Scientists’ Research Strategies
Foster, J. G., Rzhetsky, A., & Evans, J. A. (2015) · American Sociological Review · doi:10.1177/0003122415601618 · Cited by 613
Social Media Mining: An Introduction
Zafarani, R., Abbasi, M. A., & Liu, H. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9781139088510 · Cited by 592
A Comparative Analysis of Community Detection Algorithms on Artificial Networks
Yang, Z., Algesheimer, R., & Tessone, C. J. (2016) · Scientific Reports · doi:10.1038/srep30750 · Cited by 578
The modular and integrative functional architecture of the human brain
Bertolero, M. A., Yeo, B. T. T., & D’Esposito, M. (2015) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1510619112 · Cited by 565
CellNet: Network Biology Applied to Stem Cell Engineering
Cahan, P., Li, H., Morris, S. A., Lummertz da Rocha, E., Daley, G. Q., & Collins, J. J. (2014) · Cell · doi:10.1016/j.cell.2014.07.020 · Cited by 530
Detecting the dynamics of urban structure through spatial network analysis
Zhong, C., Arisona, S. M., Huang, X., Batty, M., & Schmitt, G. (2014) · International Journal of Geographical Information Science · doi:10.1080/13658816.2014.914521 · Cited by 523
Community detection in networks: A multidisciplinary review
Javed, M. A., Younis, M. S., Latif, S., Qadir, J., & Baig, A. (2018) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2018.02.011 · Cited by 499
Limits of modularity maximization in community detection
Lancichinetti, A., & Fortunato, S. (2011) · Physical Review E · doi:10.1103/physreve.84.066122 · Cited by 495
Self-citationThe ground truth about metadata and community detection in networks
Peel, L., Larremore, D. B., & Clauset, A. (2017) · Science Advances · doi:10.1126/sciadv.1602548 · Cited by 449
Memory in network flows and its effects on spreading dynamics and community detection
Rosvall, M., Esquivel, A. V., Lancichinetti, A., West, J. D., & Lambiotte, R. (2014) · Nature Communications · doi:10.1038/ncomms5630 · Cited by 395
Self-citationRosvall, M., & Bergstrom, C. T. (2011) · PLoS ONE · doi:10.1371/journal.pone.0018209 · Cited by 393
Ghiassian, S. D., Menche, J., & Barabási, A.-L. (2015) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1004120 · Cited by 388
Efficient and principled method for detecting communities in networks
Ball, B., Karrer, B., & Newman, M. E. J. (2011) · Physical Review E · doi:10.1103/physreve.84.036103 · Cited by 386
Anomaly detection in dynamic networks: a survey
Ranshous, S., Shen, S., Koutra, D., Harenberg, S., Faloutsos, C., & Samatova, N. F. (2015) · WIREs Computational Statistics · doi:10.1002/wics.1347 · Cited by 379
Discovering social circles in ego networks
Mcauley, J., & Leskovec, J. (2014) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/2556612 · Cited by 366
A classification for community discovery methods in complex networks
Coscia, M., Giannotti, F., & Pedreschi, D. (2011) · Statistical Analysis and Data Mining: The ASA Data Science Journal · doi:10.1002/sam.10133 · Cited by 353
Narrow scope for resolution-limit-free community detection
Traag, V. A., Van Dooren, P., & Nesterov, Y. (2011) · Physical Review E · doi:10.1103/physreve.84.016114 · Cited by 353
Kovács, I. A., Palotai, R., Szalay, M. S., & Csermely, P. (2010) · PLoS ONE · doi:10.1371/journal.pone.0012528 · Cited by 338
The contribution of network organization and integration to the development of cognitive control
Marek, S., Hwang, K., Foran, W., Hallquist, M. N., & Luna, B. (2015) · PLOS Biology · doi:10.1371/journal.pbio.1002328 · Cited by 337
Springer Handbook of Science and Technology Indicators
(2019) · Springer Handbooks · doi:10.1007/978-3-030-02511-3 · Cited by 300
Metrics for Community Analysis: A Survey
Chakraborty, T., Dalmia, A., Mukherjee, A., & Ganguly, N. (2018) · ACM Computing Surveys · doi:10.1145/3091106 · Cited by 296
Community-Affiliation Graph Model for Overlapping Network Community Detection
Yang, J., & Leskovec, J. (2012) · 2012 IEEE 12th International Conference on Data Mining · doi:10.1109/icdm.2012.139 · Cited by 293
Scalable Computing: Practice and Experience
(2013) · Scalable Computing Practice and Experience · doi:10.12694/issn.1895-1767 · Cited by 280
Men Set Their Own Cites High: Gender and Self-citation across Fields and over Time
King, M. M., Bergstrom, C. T., Correll, S. J., Jacquet, J., & West, J. D. (2017) · Socius: Sociological Research for a Dynamic World · doi:10.1177/2378023117738903 · Cited by 275
“However, these two papers illustrate alternative paths to the same end: at one extreme, papers with many authors citing even a few papers with many of the same authors; at another extreme, sole-authored papers citing many previous papers.”
BackgroundMethodDetecting highly overlapping community structure by greedy clique expansion
Lee, C., Reid, F., McDaid, A. F., & Hurley, N. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1002.1827 · Cited by 271
Characterizing the Community Structure of Complex Networks
Lancichinetti, A., Kivelä, M., Saramäki, J., & Fortunato, S. (2010) · PLoS ONE · doi:10.1371/journal.pone.0011976 · Cited by 267
Self-citationAn Evolutionary Multiobjective Approach for Community Discovery in Dynamic Networks
Folino, F., & Pizzuti, C. (2014) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2013.131 · Cited by 265
Graph-based Natural Language Processing and Information Retrieval
Mihalcea, R., & Radev, D. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9780511976247 · Cited by 259
Dehling, T., Gao, F., Schneider, S., & Sunyaev, A. (2015) · JMIR mHealth and uHealth · doi:10.2196/mhealth.3672 · Cited by 243
Emergency information diffusion on online social media during storm Cindy in U.S.
Kim, J., Bae, J., & Hastak, M. (2018) · International Journal of Information Management · doi:10.1016/j.ijinfomgt.2018.02.003 · Cited by 166
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
Zhao, T., & Schranz, M. E. (2019) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1801757116 · Cited by 120
Gaiteri, C., Chen, M., Szymanski, B., Kuzmin, K., Xie, J., Lee, C., Blanche, T., Chaibub Neto, E., Huang, S.-C., Grabowski, T., et al. (2015) · Scientific Reports · doi:10.1038/srep16361 · Cited by 76
Verkhivker, G. M., Agajanian, S., Hu, G., & Tao, P. (2020) · Frontiers in Molecular Biosciences · doi:10.3389/fmolb.2020.00136 · Cited by 76
Petrican, R., Taylor, M. J., & Grady, C. L. (2017) · NeuroImage · doi:10.1016/j.neuroimage.2017.09.025 · Cited by 43
Distributed temporal graph analytics with GRADOOP
Rost, C., Gomez, K., Täschner, M., Fritzsche, P., Schons, L., Christ, L., Adameit, T., Junghanns, M., & Rahm, E. (2022) · The VLDB Journal · doi:10.1007/s00778-021-00667-4 · Cited by 39
The Impact of Random Models on Clustering Similarity
Gates, A. J., & Ahn, Y.-Y. (2017) · doi:10.1101/196840 · Cited by 24
Darius, P. (2022) · Social Network Analysis and Mining · doi:10.1007/s13278-022-00958-w · Cited by 22
Metadata
- Authors
- Lancichinetti, A., & Fortunato, S.
- Venue
- Physical Review E
- Publisher
- American Physical Society (APS)
- Published
- 2009-11-30
- Volume
- 80
- Issue
- 5
- Pages
- 056117-056117
- ISSN
- 1539-3755 (ISSN-L)
- 1550-2376
- OpenAlex
- W1995996823
- Cited by
- 2,177
- References
- 55
- FWCI
- 62.31
- Type
- journal article
- Language
- en
- Open access
- green
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.