The DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index.
Benchmark graphs for testing community detection algorithms
Open accessAbstract
Community structure is one of the most important features of real networks and reveals the internal organization of the nodes. Many algorithms have been proposed but the crucial issue of testing, i.e., the question of how good an algorithm is, with respect to others, is still open. Standard tests include the analysis of simple artificial graphs with a built-in community structure, that the algorithm has to recover. However, the special graphs adopted in actual tests have a structure that does not reflect the real properties of nodes and communities found in real networks. Here we introduce a class of benchmark graphs, that account for the heterogeneity in the distributions of node degrees and of community sizes. We use this benchmark to test two popular methods of community detection, modularity optimization, and Potts model clustering. The results show that the benchmark poses a much more severe test to algorithms than standard benchmarks, revealing limits that may not be apparent at a first analysis.
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
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
Complex 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
Error and attack tolerance of complex networks
Albert, R., Jeong, H., & Barabási, A.-L. (2000) · Nature · doi:10.1038/35019019 · Cited by 7,534
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
Epidemic Spreading in Scale-Free Networks
Pastor-Satorras, R., & Vespignani, A. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.3200 · Cited by 5,731
Fast algorithm for detecting community structure in networks
Newman, M. E. J. (2004) · Physical Review E · doi:10.1103/physreve.69.066133 · Cited by 5,406
Uncovering the overlapping community structure of complex networks in nature and society
Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005) · Nature · doi:10.1038/nature03607 · Cited by 5,373
Functional cartography of complex metabolic networks
Guimerà, R., & Nunes Amaral, L. A. (2005) · Nature · doi:10.1038/nature03288 · Cited by 3,983
Resolution limit in community detection
Fortunato, S., & Barthélemy, M. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0605965104 · Cited by 3,024
Self-citation
Cited by
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293
“A realization of the LFR benchmark graphs [326], with 500 vertices.”
BackgroundMethodInfluentialSelf-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
“To study the scaling of the Louvain and the Leiden algorithm, we rely on a variant of a well-known approach for constructing benchmark networks 28 .”
MethodNewman, M. (2018) · doi:10.1093/oso/9780198805090.001.0001 · Cited by 2,297
Community detection algorithms: A comparative analysis
Lancichinetti, A., & Fortunato, S. (2009) · Physical Review E · doi:10.1103/physreve.80.056117 · Cited by 2,177
Self-citationStochastic blockmodels and community structure in networks
Karrer, B., & Newman, M. E. J. (2011) · Physical Review E · doi:10.1103/physreve.83.016107 · Cited by 2,025
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-citationNetworks beyond pairwise interactions: Structure and dynamics
Battiston, F., Cencetti, G., Iacopini, I., Latora, V., Lucas, M., Patania, A., Young, J.-G., & Petri, G. (2020) · Physics Reports · doi:10.1016/j.physrep.2020.05.004 · Cited by 1,602
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-citationLancichinetti, A., & Fortunato, S. (2009) · Physical Review E · doi:10.1103/physreve.80.016118 · Cited by 1,009
Self-citationOverlapping 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
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
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
Robustness and resilience of complex networks
Artime, O., Grassia, M., De Domenico, M., Gleeson, J. P., Makse, H. A., Mangioni, G., Perc, M., & Radicchi, F. (2024) · Nature Reviews Physics · doi:10.1038/s42254-023-00676-y · Cited by 672
Self-citationCommunity 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
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
Identifying and ranking influential spreaders in complex networks by neighborhood coreness
Bae, J., & Kim, S. (2014) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2013.10.047 · Cited by 564
Xie, J., Szymanski, B. K., & Liu, X. (2011) · 2011 IEEE 11th International Conference on Data Mining Workshops · doi:10.1109/icdmw.2011.154 · Cited by 519
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-citationAbdollahzadeh, B., Khodadadi, N., Barshandeh, S., Trojovský, P., Gharehchopogh, F. S., El-kenawy, E.-S. M., Abualigah, L., & Mirjalili, S. (2024) · Cluster Computing · doi:10.1007/s10586-023-04221-5 · Cited by 479
Community Discovery in Dynamic Networks: A Survey
Rossetti, G., & Cazabet, R. (2019) · ACM Computing Surveys · doi:10.1145/3172867 · Cited by 468
Generalized Louvain method for community detection in large networks
De Meo, P., Ferrara, E., Fiumara, G., & Provetti, A. (2011) · 2011 11th International Conference on Intelligent Systems Design and Applications · doi:10.1109/isda.2011.6121636 · Cited by 440
Community detection in networks with positive and negative links
Traag, V. A., & Bruggeman, J. (2009) · Physical Review E · doi:10.1103/physreve.80.036115 · Cited by 434
Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
Lambiotte, R., Delvenne, J.-C., & Barahona, M. (2014) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2015.2391998 · Cited by 398
Gong, M., Cai, Q., Chen, X., & Ma, L. (2014) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2013.2260862 · Cited by 394
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
The statistical physics of real-world networks
Cimini, G., Squartini, T., Saracco, F., Garlaschelli, D., Gabrielli, A., & Caldarelli, G. (2019) · Nature Reviews Physics · doi:10.1038/s42254-018-0002-6 · Cited by 378
Complex Networks: Principles, Methods and Applications
Latora, V., Nicosia, V., & Russo, G. (2017) · Cambridge University Press eBooks · doi:10.1017/9781316216002 · Cited by 372
Detecting network communities by propagating labels under constraints
Barber, M. J., & Clark, J. W. (2009) · Physical Review E · doi:10.1103/physreve.80.026129 · Cited by 355
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
A Comprehensive Survey on Community Detection With Deep Learning
Su, X., Xue, S., Liu, F., Wu, J., Yang, J., Zhou, C., Hu, W., Paris, C., Nepal, S., Jin, D., et al. (2024) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2021.3137396 · 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
Graph Spectra and the Detectability of Community Structure in Networks
Nadakuditi, R. R., & Newman, M. E. J. (2012) · Physical Review Letters · doi:10.1103/physrevlett.108.188701 · Cited by 316
Community Detection via Maximization of Modularity and Its Variants
Chen, M., Kuzmin, K., & Szymanski, B. K. (2014) · IEEE Transactions on Computational Social Systems · doi:10.1109/tcss.2014.2307458 · Cited by 301
Optimal Network Modularity for Information Diffusion
Nematzadeh, A., Ferrara, E., Flammini, A., & Ahn, Y.-Y. (2014) · Physical Review Letters · doi:10.1103/physrevlett.113.088701 · Cited by 300
Community detection in node-attributed social networks: A survey
Chunaev, P. (2020) · Computer Science Review · doi:10.1016/j.cosrev.2020.100286 · Cited by 300
Local search of communities in large graphs
Cui, W., Xiao, Y., Wang, H., & Wang, W. (2014) · Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2588555.2612179 · Cited by 299
Towards real-time community detection in large networks
Leung, I. X. Y., Hui, P., Liò, P., & Crowcroft, J. (2009) · Physical Review E · doi:10.1103/physreve.79.066107 · Cited by 289
Towards Linear Time Overlapping Community Detection in Social Networks
Xie, J., & Szymanski, B. K. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-30220-6_3 · Cited by 280
Effects of network modularity on the spread of perturbation impact in experimental metapopulations
Gilarranz, L. J., Rayfield, B., Liñán-Cembrano, G., Bascompte, J., & Gonzalez, A. (2017) · Science · doi:10.1126/science.aal4122 · Cited by 279
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
Comparing methods for comparing networks
Tantardini, M., Ieva, F., Tajoli, L., & Piccardi, C. (2019) · Scientific Reports · doi:10.1038/s41598-019-53708-y · Cited by 264
Wang, Y., Di, Z., & Fan, Y. (2011) · PLoS ONE · doi:10.1371/annotation/1935b388-2831-4fb1-b8f2-914ab91c1ddc · Cited by 130
A Monte Carlo evaluation of weighted community detection algorithms
Gates, K. M., Henry, T., Steinley, D., & Fair, D. A. (2016) · Frontiers in Neuroinformatics · doi:10.3389/fninf.2016.00045 · Cited by 106
“The first data generation algorithm is the publicly available Lancichinetti-Fortunato (LFR) benchmark approach for arriving at sparse count matrices (Lancichinetti et al., 2008).”
MethodGaiteri, 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
Multilevel Combinatorial Optimization across Quantum Architectures
Ushijima-Mwesigwa, H., Shaydulin, R., Negre, C. F. A., Mniszewski, S. M., Alexeev, Y., & Safro, I. (2021) · ACM Transactions on Quantum Computing · doi:10.1145/3425607 · Cited by 57
“the exponent for the degree distribution, βis the exponent for the community size distribution and µis the mixing parameter. For a detailed discussion of the parameters the reader is referred to Ref. [54] of node degree and community size, introduced by Lancichinetti et al. [54]. Table 2 shows the parameters used to g…”
MethodCommunity Detection in Quantum Complex Networks
Faccin, M., Migdał, P., Johnson, T. H., Bergholm, V., & Biamonte, J. D. (2014) · Physical Review X · doi:10.1103/physrevx.4.041012 · Cited by 43
“in [50], which provides a method to construct a network with heterogeneous distribution both for the node degree and for the communities dimension and a controllable inter-community connection.”
BackgroundMethodWang, T., Peng, Q., Liu, B., Liu, Y., & Wang, Y. (2020) · Frontiers in Bioengineering and Biotechnology · doi:10.3389/fbioe.2020.00418 · Cited by 27
“We used the network simulation tool LFR-benchmark (Lancichinetti et al., 2008), to generate small-to-large scale networks, with weighted and directed edges.”
MethodPredicting species emergence in simulated complex pre-biotic networks
Markovitch, O., & Krasnogor, N. (2018) · PLOS ONE · doi:10.1371/journal.pone.0192871 · Cited by 19
Quantum walks on complex networks with connection instabilities and community structure
Tsomokos, D. I. (2011) · Physical Review A · doi:10.1103/physreva.83.052315 · Cited by 18
Metadata
- Authors
- Lancichinetti, A., Fortunato, S., & Radicchi, F.
- Venue
- Physical Review E
- Publisher
- American Physical Society (APS)
- Published
- 2008-10-24
- Volume
- 78
- Issue
- 4
- Pages
- 046110-046110
- ISSN
- 1539-3755 (ISSN-L)
- 1550-2376
- OpenAlex
- W2023655578
- Cited by
- 3,051
- References
- 18
- FWCI
- 44.52
- 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.