The DOI matches its Crossref record; 31 of the 31 references it cites were found in a registry or an index.
Empirical comparison of algorithms for network community detection
Abstract
Detecting clusters or communities in large real-world graphs such as large social or information networks is a problem of considerable interest. In practice, one typically chooses an objective function that captures the intuition of a network cluster as set of nodes with better internal connectivity than external connectivity, and then one applies approximation algorithms or heuristics to extract sets of nodes that are related to the objective function and that look like good communities for the application of interest.In this paper, we explore a range of network community detection methods in order to compare them and to understand their relative performance and the systematic biases in the clusters they identify. We evaluate several common objective functions that are used to formalize the notion of a network community, and we examine several different classes of approximation algorithms that aim to optimize such objective functions. In addition, rather than simply fixing an objective and asking for an approximation to the best cluster of any size, we consider a size-resolved version of the optimization problem. Considering community quality as a function of its size provides a much finer lens with which to examine community detection algorithms, since objective functions and approximation algorithms often have non-obvious size-dependent behavior.
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
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
Normalized cuts and image segmentation
Shi, J., & Malik, J. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.868688 · 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
Modularity and community structure in networks
Newman, M. E. J. (2006) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0601602103 · Cited by 12,256
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293 · cited 1×
“Using a particular measure of network community quality f ( S ) , e.g. , conductance or one of the other measures described in Section 4, we then define the network community profile (NCP) [27, 26] that characterizes the quality of network communities as a function of their size.”
BackgroundFinding 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
A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
Karypis, G., & Kumar, V. (1998) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827595287997 · Cited by 5,762
Chung, F. (1996) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/092 · Cited by 5,524
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
Defining and identifying communities in networks
Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., & Parisi, D. (2004) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0400054101 · Cited by 2,450 · cited 5×
“A “network community” (also sometimes referred to as a module or cluster) is typically thought of as a group of nodes with more and/or better interactions amongst its members than between its members and the remainder of the network [30, 16].”
BackgroundMethodInfluential
Cited by
Chen, M., Mao, S., & Liu, Y. (2014) · Mobile Networks and Applications · doi:10.1007/s11036-013-0489-0 · Cited by 2,913
Graph based anomaly detection and description: a survey
Akoglu, L., Tong, H., & Koutra, D. (2015) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-014-0365-y · Cited by 1,504
“…Dhillon et al., 2003], and its distributed variants [Papadimitriou and Sun, 2008]; dynamic community detection algorithms Tantipathananandh and Berger-Wolf [2009, 2011], Tantipathananandh et al. [2007], and empirical comparison of methods for network community detection [Leskovec et al., 2010].”
BackgroundDefining and evaluating network communities based on ground-truth
Yang, J., & Leskovec, J. (2015) · Knowledge and Information Systems · doi:10.1007/s10115-013-0693-z · Cited by 1,411
Self-citationToward Scalable Systems for Big Data Analytics: A Technology Tutorial
Hu, H., Wen, Y., Chua, T.-S., & Li, X. (2014) · IEEE Access · doi:10.1109/access.2014.2332453 · Cited by 1,099
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
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
Defining and evaluating network communities based on ground-truth
Yang, J., & Leskovec, J. (2012) · Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics · doi:10.1145/2350190.2350193 · Cited by 762
Self-citationNetwork Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec
Qiu, J., Dong, Y., Ma, H., Li, J., Wang, K., & Tang, J. (2018) · Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining · doi:10.1145/3159652.3159706 · Cited by 717
From hairballs to hypotheses–biological insights from microbial networks
Röttjers, L., & Faust, K. (2018) · FEMS Microbiology Reviews · doi:10.1093/femsre/fuy030 · Cited by 714
Spatio-Temporal Data Mining: A Survey of Problems and Methods
Atluri, G., Karpatne, A., & Kumar, V. (2019) · ACM Computing Surveys · doi:10.1145/3161602 · Cited by 461
The 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
Leveraging social media networks for classification
Tang, L., & Liu, H. (2011) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-010-0210-x · Cited by 360
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
Self-citationLike like alike: joint friendship and interest propagation in social networks
Yang, S.-H., Long, B., Smola, A., Sadagopan, N., Zheng, Z., & Zha, H. (2011) · Proceedings of the 20th international conference on World wide web · doi:10.1145/1963405.1963481 · Cited by 359
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 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
Efficient community detection in large networks using content and links
Ruan, Y., Fuhry, D., & Parthasarathy, S. (2013) · Proceedings of the 22nd international conference on World Wide Web · doi:10.1145/2488388.2488483 · Cited by 304
An analysis of social network-based Sybil defenses
Viswanath, B., Post, A., Gummadi, K. P., & Mislove, A. (2010) · Proceedings of the ACM SIGCOMM 2010 conference · doi:10.1145/1851182.1851226 · Cited by 304
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
A Survey of Social-Based Routing in Delay Tolerant Networks: Positive and Negative Social Effects
Zhu, Y., Xu, B., Shi, X., & Wang, Y. (2013) · IEEE Communications Surveys & Tutorials · doi:10.1109/surv.2012.032612.00004 · Cited by 295
Influence-Based Community Partition With Sandwich Method for Social Networks
Ni, Q., Guo, J., Wu, W., & Wang, H. (2023) · IEEE Transactions on Computational Social Systems · doi:10.1109/tcss.2022.3148411 · Cited by 265
An 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
Deep Autoencoder-like Nonnegative Matrix Factorization for Community Detection
Ye, F., Chen, C., & Zheng, Z. (2018) · Proceedings of the 27th ACM International Conference on Information and Knowledge Management · doi:10.1145/3269206.3271697 · Cited by 263
A Survey of Information Cascade Analysis: Models, Predictions, and Recent Advances
Zhou, F., Xu, X., Trajcevski, G., & Zhang, K. (2022) · ACM Computing Surveys · doi:10.1145/3433000 · Cited by 259
Defining and Evaluating Network Communities Based on Ground-Truth
Yang, J., & Leskovec, J. (2012) · 2012 IEEE 12th International Conference on Data Mining · doi:10.1109/icdm.2012.138 · Cited by 254
Self-citationEmergency 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
Finding and characterizing communities in multidimensional networks
Berlingerio, M., Coscia, M., & Giannotti, F. (2011) · 2011 International Conference on Advances in Social Networks Analysis and Mining · doi:10.1109/asonam.2011.104 · Cited by 122
Big Data and the danger of being precisely inaccurate
McFarland, D. A., & McFarland, H. R. (2015) · Big Data & Society · doi:10.1177/2053951715602495 · Cited by 81
Metadata
- Authors
- Leskovec, J., Lang, K. J., & Mahoney, M.
- Venue
- Proceedings of the 19th international conference on World wide web
- Publisher
- ACM
- Published
- 2010-04-26
- Pages
- 631-640
- OpenAlex
- W2111002549
- Cited by
- 918
- References
- 31
- FWCI
- 44.98
- Type
- conference paper
- Language
- en
- Open access
- closed
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.