The DOI matches its Crossref record; 26 of the 26 references it cites were found in a registry or an index.
Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
Open accessAbstract
Many complex networks display a mesoscopic structure with groups of nodes sharing many links with the other nodes in their group and comparatively few with nodes of different groups. This feature is known as community structure and encodes precious information about the organization and the function of the nodes. Many algorithms have been proposed but it is not yet clear how they should be tested. Recently we have proposed a general class of undirected and unweighted benchmark graphs, with heterogeneous distributions of node degree and community size. An increasing attention has been recently devoted to develop algorithms able to consider the direction and the weight of the links, which require suitable benchmark graphs for testing. In this paper we extend the basic ideas behind our previous benchmark to generate directed and weighted networks with built-in community structure. We also consider the possibility that nodes belong to more communities, a feature occurring in real systems, such as social networks. As a practical application, we show how modularity optimization performs on our benchmark.
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
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
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
Diameter of the World-Wide Web
Albert, R., Jeong, H., & Barabási, A.-L. (1999) · Nature · doi:10.1038/43601 · Cited by 4,260
The architecture of complex weighted networks
Barrat, A., Barthélemy, M., Pastor-Satorras, R., & Vespignani, A. (2004) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0400087101 · Cited by 4,218
Functional cartography of complex metabolic networks
Guimerà, R., & Nunes Amaral, L. A. (2005) · Nature · doi:10.1038/nature03288 · Cited by 3,983
Cited by
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293
“Quality functions that, like modularity, are based on a null model such that the horizon of vertices is of the order of the size of the whole graph, are likely to be affected by a resolution limit (Fortunato, 2007).”
BackgroundMethodInfluentialSelf-citationCommunity detection algorithms: A comparative analysis
Lancichinetti, A., & Fortunato, S. (2009) · Physical Review E · doi:10.1103/physreve.80.056117 · Cited by 2,177
Self-citationCommunity 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-citationFinding 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-citationDisease-associated astrocytes in Alzheimer’s disease and aging
Habib, N., McCabe, C., Medina, S., Varshavsky, M., Kitsberg, D., Dvir-Szternfeld, R., Green, G., Dionne, D., Nguyen, L., Marshall, J. L., et al. (2020) · Nature Neuroscience · doi:10.1038/s41593-020-0624-8 · Cited by 1,009
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
Consensus clustering in complex networks
Lancichinetti, A., & Fortunato, S. (2012) · Scientific Reports · doi:10.1038/srep00336 · Cited by 795
Self-citationA 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
Clustering and community detection in directed networks: A survey
Malliaros, F. D., & Vazirgiannis, M. (2013) · Physics Reports · doi:10.1016/j.physrep.2013.08.002 · Cited by 591
Local Higher-Order Graph Clustering
Yin, H., Benson, A. R., Leskovec, J., & Gleich, D. F. (2017) · Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/3097983.3098069 · Cited by 583
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
Tracking the Evolution of Communities in Dynamic Social Networks
Greene, D., Doyle, D., & Cunningham, P. (2010) · 2010 International Conference on Advances in Social Networks Analysis and Mining · doi:10.1109/asonam.2010.17 · Cited by 537
Community Discovery in Dynamic Networks: A Survey
Rossetti, G., & Cazabet, R. (2019) · ACM Computing Surveys · doi:10.1145/3172867 · Cited by 468
Overlapping community detection using Bayesian non-negative matrix factorization
Psorakis, I., Roberts, S., Ebden, M., & Sheldon, B. (2011) · Physical Review E · doi:10.1103/physreve.83.066114 · Cited by 399
A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning
Jin, D., Yu, Z., Jiao, P., Pan, S., He, D., Wu, J., Yu, P., & Zhang, W. (2021) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2021.3104155 · Cited by 397
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 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
Community detection in social networks
Bedi, P., & Sharma, C. (2016) · WIREs Data Mining and Knowledge Discovery · doi:10.1002/widm.1178 · Cited by 346
A survey of community search over big graphs
Fang, Y., Huang, X., Qin, L., Zhang, Y., Zhang, W., Cheng, R., & Lin, X. (2020) · The VLDB Journal · doi:10.1007/s00778-019-00556-x · Cited by 339
Kovács, I. A., Palotai, R., Szalay, M. S., & Csermely, P. (2010) · PLoS ONE · doi:10.1371/journal.pone.0012528 · Cited by 338
Consistency and differences between centrality measures across distinct classes of networks
Oldham, S., Fulcher, B., Parkes, L., Arnatkevic̆iūtė, A., Suo, C., & Fornito, A. (2019) · PLOS ONE · doi:10.1371/journal.pone.0220061 · Cited by 296
Efficient discovery of overlapping communities in massive networks
Gopalan, P. K., & Blei, D. M. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1221839110 · Cited by 272
Detecting 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
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
Multicellular communities are perturbed in the aging human brain and Alzheimer’s disease
Cain, A., Taga, M., McCabe, C., Green, G. S., Hekselman, I., White, C. C., Lee, D. I., Gaur, P., Rozenblatt-Rosen, O., Zhang, F., et al. (2023) · Nature Neuroscience · doi:10.1038/s41593-023-01356-x · Cited by 142
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 average and max degrees increased as graph size increased given the increased number of nodes and were informed by prior studies (Lancichinetti and Fortunato, 2009).”
ResultMagnetic 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
Multi-cellular communities are perturbed in the aging human brain and Alzheimer’s disease
Cain, A., Taga, M., McCabe, C., Green, G., Hekselman, I., White, C. C., Lee, D. I., Gaur, P., Rozenblatt-Rosen, O., Zhang, F., et al. (2020) · doi:10.1101/2020.12.22.424084 · Cited by 143
Magnetic Eigenmaps for the visualization of directed networks
Fanuel, M., Alaíz, C. M., Fernández, Á., & Suykens, J. A. K. (2018) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2017.01.004 · Cited by 35
Community detection in network neuroscience
Betzel, R. F. (2020) · arXiv · doi:10.48550/arxiv.2011.06723 · Cited by 24
Metadata
- Authors
- Lancichinetti, A., & Fortunato, S.
- Venue
- Physical Review E
- Publisher
- American Physical Society (APS)
- Published
- 2009-07-31
- Volume
- 80
- Issue
- 1
- Pages
- 016118-016118
- ISSN
- 1539-3755 (ISSN-L)
- 1550-2376
- OpenAlex
- W1991408655
- Cited by
- 1,009
- References
- 26
- FWCI
- 25.01
- 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.