The DOI matches its Crossref record; 96 of the 96 references it cites were found in a registry or an index.
Overlapping community detection in networks: The state-of-the-art and comparative study
Open accessAbstract
This article reviews the state-of-the-art in overlapping community detection algorithms, quality measures, and benchmarks. A thorough comparison of different algorithms (a total of fourteen) is provided. In addition to community-level evaluation, we propose a framework for evaluating algorithms' ability to detect overlapping nodes, which helps to assess overdetection and underdetection. After considering community-level detection performance measured by normalized mutual information, the Omega index, and node-level detection performance measured by F-score, we reached the following conclusions. For low overlapping density networks, SLPA, OSLOM, Game, and COPRA offer better performance than the other tested algorithms. For networks with high overlapping density and high overlapping diversity, both SLPA and Game provide relatively stable performance. However, test results also suggest that the detection in such networks is still not yet fully resolved. A common feature observed by various algorithms in real-world networks is the relatively small fraction of overlapping nodes (typically less than 30%), each of which belongs to only 2 or 3 communities.
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
WGCNA: an R package for weighted correlation network analysis
Langfelder, P., & Horvath, S. (2008) · BMC Bioinformatics · doi:10.1186/1471-2105-9-559 · Cited by 27,252
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 · cited 3×
“In the GN benchmark · 15 [Girvan and Newman 2002], equal size communities are embedded into a network for a given expected degree and a given mixing parameter µ that measures the ratio of internal connections to outgoing connections.”
BackgroundFortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293
Hubert, L., & Arabie, P. (1985) · Journal of Classification · doi:10.1007/bf01908075 · Cited by 8,219
Clustering by Passing Messages Between Data Points
Frey, B. J., & Dueck, D. (2007) · Science · doi:10.1126/science.1136800 · Cited by 6,758
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 · cited 2×
“Empirically, small values of k (typically between 3 and 6) have been shown to give good results [Palla et al. 2005; Lancichinetti and Fortunato 2009; Gregory 2010].”
BackgroundMethodFinding community structure in networks using the eigenvectors of matrices
Newman, M. E. J. (2006) · Physical Review E · doi:10.1103/physreve.74.036104 · Cited by 4,761
Maps of random walks on complex networks reveal community structure
Rosvall, M., & Bergstrom, C. T. (2008) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0706851105 · Cited by 4,583
Ankerst, M. (1999) · doi:10.1145/304181.304187 · Cited by 3,982
Near linear time algorithm to detect community structures in large-scale networks
Raghavan, U. N., Albert, R., & Kumara, S. (2007) · Physical Review E · doi:10.1103/physreve.76.036106 · Cited by 3,502
Benchmark graphs for testing community detection algorithms
Lancichinetti, A., Fortunato, S., & Radicchi, F. (2008) · Physical Review E · doi:10.1103/physreve.78.046110 · Cited by 3,051
Comparing community structure identification
Danon, L., Díaz-Guilera, A., Duch, J., & Arenas, A. (2005) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2005/09/p09008 · Cited by 2,872
Graph evolution: Densification and shrinking diameters
Leskovec, J., Kleinberg, J., & Faloutsos, C. (2007) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1217299.1217301 · Cited by 2,461
Community detection algorithms: A comparative analysis
Lancichinetti, A., & Fortunato, S. (2009) · Physical Review E · doi:10.1103/physreve.80.056117 · Cited by 2,177
Clustering and preferential attachment in growing networks
Newman, M. E. J. (2001) · Physical Review E · doi:10.1103/physreve.64.025102 · Cited by 2,093
Statistical mechanics of community detection
Reichardt, J., & Bornholdt, S. (2006) · Physical Review E · doi:10.1103/physreve.74.016110 · Cited by 2,048
The dynamics of viral marketing
Leskovec, J., Adamic, L. A., & Huberman, B. A. (2007) · ACM Transactions on the Web · doi:10.1145/1232722.1232727 · Cited by 2,032
Link communities reveal multiscale complexity in networks
Ahn, Y.-Y., Bagrow, J. P., & Lehmann, S. (2010) · Nature · doi:10.1038/nature09182 · Cited by 1,949
Detecting the overlapping and hierarchical community structure in complex networks
Lancichinetti, A., Fortunato, S., & Kertész, J. (2009) · New Journal of Physics · doi:10.1088/1367-2630/11/3/033015 · Cited by 1,941
Leskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2009) · Internet Mathematics · doi:10.1080/15427951.2009.10129177 · Cited by 1,872
OPTICS: ordering points to identify the clustering structure
Ankerst, M., Breunig, M. M., Kriegel, H.-P., & Sander, J. (1999) · Proceedings of the 1999 ACM SIGMOD international conference on Management of data · doi:10.1145/304182.304187 · Cited by 1,335
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
Estimation and Prediction for Stochastic Blockstructures
Nowicki, K., & Snijders, T. A. B. (2001) · Journal of the American Statistical Association · doi:10.1198/016214501753208735 · Cited by 1,148
Trust Management for the Semantic Web
Richardson, M., Agrawal, R., & Domingos, P. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-39718-2_23 · Cited by 982
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
Modularity from fluctuations in random graphs and complex networks
Guimerà, R., Sales-Pardo, M., & Amaral, L. A. N. (2004) · Physical Review E · doi:10.1103/physreve.70.025101 · Cited by 894
Synchronization Reveals Topological Scales in Complex Networks
Arenas, A., Díaz-Guilera, A., & Pérez-Vicente, C. J. (2006) · Physical Review Letters · doi:10.1103/physrevlett.96.114102 · Cited by 848
Moon, J. W., & Moser, L. (1965) · Israel Journal of Mathematics · doi:10.1007/bf02760024 · Cited by 837
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
Models of social networks based on social distance attachment
Boguñá, M., Pastor-Satorras, R., Díaz-Guilera, A., & Arenas, A. (2004) · Physical Review E · doi:10.1103/physreve.70.056122 · Cited by 769
Matei, R., Iamnitchi, A., & Foster, P. (2002) · IEEE Internet Computing · doi:10.1109/4236.978369 · Cited by 766
Detect overlapping and hierarchical community structure in networks
Shen, H., Cheng, X., Cai, K., & Hu, M.-B. (2009) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2008.12.021 · Cited by 723
Line graphs, link partitions, and overlapping communities
Evans, T. S., & Lambiotte, R. (2009) · Physical Review E · doi:10.1103/physreve.80.016105 · Cited by 615
Detecting Fuzzy Community Structures in Complex Networks with a Potts Model
Reichardt, J., & Bornholdt, S. (2004) · Physical Review Letters · doi:10.1103/physrevlett.93.218701 · Cited by 593
Mixture models and exploratory analysis in networks
Newman, M. E. J., & Leicht, E. A. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0610537104 · Cited by 554
Superparamagnetic Clustering of Data
Blatt, M., Wiseman, S., & Domany, E. (1996) · Physical Review Letters · doi:10.1103/physrevlett.76.3251 · Cited by 537
Identification of overlapping community structure in complex networks using fuzzy -means clustering
Zhang, S., Wang, R.-S., & Zhang, X.-S. (2007) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2006.07.023 · Cited by 530
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
Self-citationProceedings of the 26th International Conference on Data Engineering, ICDE 2010
Li, F., Moro, M. M., Ghandeharizadeh, S., Haritsa, J. R., Weikum, G., Carey, M. J., Casati, F., Chang, E. Y., Manolescu, I., Mehrotra, S., et al. (2010) · Max Planck Institute for Plasma Physics · Cited by 452
Fuzzy communities and the concept of bridgeness in complex networks
Nepusz, T., Petróczi, A., Négyessy, L., & Bazsó, F. (2008) · Physical Review E · doi:10.1103/physreve.77.016107 · Cited by 421
A Spectral Clustering Approach To Finding Communities in Graphs
White, S., & Smyth, P. (2005) · Proceedings of the 2005 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972757.25 · Cited by 404
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
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
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
Extending the definition of modularity of directed graphs with overlapping communitiesPreprint
Nicosia, V., Mangioni, G., Carchiolo, V., & Malgeri, M. (2009) · Cited by 350
Extending the definition of modularity to directed graphs with overlapping communities
Nicosia, V, Mangioni, G., Carchiolo, V, & Malgeri, M. (2009) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2009/03/p03024 · Cited by 346
Kovács, I. A., Palotai, R., Szalay, M. S., & Csermely, P. (2010) · PLoS ONE · doi:10.1371/journal.pone.0012528 · Cited by 338
An Algorithm to Find Overlapping Community Structure in Networks
Gregory, S. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-74976-9_12 · Cited by 302
Graph Evolution: Densification and Shrinking Diameters
Leskovec, J., Kleinberg, J. M., & Faloutsos, C. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.physics/0603229 · Cited by 300
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
Self-citationDetecting 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
Overlapping stochastic block models with application to the French political blogosphere
Latouche, P., Birmelé, E., & Ambroise, C. (2011) · The Annals of Applied Statistics · doi:10.1214/10-aoas382 · Cited by 256
Farkas, I., Ábel, D., Palla, G., & Vicsek, T. (2007) · New Journal of Physics · doi:10.1088/1367-2630/9/6/180 · Cited by 251
Multiresolution community detection for megascale networks by information-based replica correlations
Ronhovde, P., & Nussinov, Z. (2009) · Physical Review E · doi:10.1103/physreve.80.016109 · Cited by 245
Sequential algorithm for fast clique percolation
Kumpula, J. M., Kivelä, M., Kaski, K., & Saramäki, J. (2008) · Physical Review E · doi:10.1103/physreve.78.026109 · Cited by 230
Assessing the relevance of node features for network structure
Bianconi, G., Pin, P., & Marsili, M. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0811511106 · Cited by 221
Campello, R. J. G. B. (2007) · Pattern Recognition Letters · doi:10.1016/j.patrec.2006.11.010 · Cited by 217
A game-theoretic framework to identify overlapping communities in social networks
Chen, W., Liu, Z., Sun, X., & Wang, Y. (2010) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-010-0186-6 · Cited by 215
Fuzzy overlapping communities in networks
Gregory, S. (2011) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2011/02/p02017 · Cited by 208
Clique graphs and overlapping communities
Evans, T. (2010) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2010/12/p12037 · Cited by 202
Proceedings of the 2003 SIAM International Conference on Data Mining
(2003) · doi:10.1137/1.9781611972733 · Cited by 198
Random graphs with arbitrary degree distributions and their applications
Newman, M. E. J., Strogatz, S. H., & Watts, D. J. (2011) · The Structure and Dynamics of Networks · doi:10.1515/9781400841356.269 · Cited by 188
Identifying communities within energy landscapes
Massen, C. P., & Doye, J. P. K. (2005) · Physical Review E · doi:10.1103/physreve.71.046101 · Cited by 176
A Fast Algorithm to Find Overlapping Communities in Networks
Gregory, S. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-87479-9_45 · Cited by 174
Detection of Overlapping Communities in Dynamical Social Networks
Cazabet, R., Amblard, F., & Hanachi, C. (2010) · doi:10.1109/socialcom.2010.51 · Cited by 174
FINDING COMMUNITIES BY CLUSTERING A GRAPH INTO OVERLAPPING SUBGRAPHS
Baumes, J., Goldberg, M., Krishnamoorthy, M. S., Magdon‐Ismail, M., & Preston, N. (2005) · IADIS AC · Cited by 170
Community detection using a neighborhood strength driven Label Propagation Algorithm
Xie, J., & Szymanski, B. K. (2011) · 2011 IEEE Network Science Workshop · doi:10.1109/nsw.2011.6004645 · Cited by 161
Self-citationCollins, L. M., & Dent, C. W. (1988) · Multivariate Behavioral Research · doi:10.1207/s15327906mbr2302_6 · Cited by 161
Line graphs of weighted networks for overlapping communities
Evans, T., & Lambiotte, R. (2010) · The European Physical Journal B · doi:10.1140/epjb/e2010-00261-8 · Cited by 144
Detecting Highly Overlapping Communities with Model-Based Overlapping Seed Expansion
McDaid, A. F., & Hurley, N. (2010) · IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) · doi:10.1109/asonam.2010.77 · Cited by 143
Finding instabilities in the community structure of complex networks
Gfeller, D., Chappelier, J.-C., & Rios, P. D. L. (2005) · Physical Review E · doi:10.1103/physreve.72.056135 · Cited by 140
Quantifying and identifying the overlapping community structure in networks
Shen, H., Cheng, X., & Guo, J. (2009) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2009/07/p07042 · Cited by 140
Uncovering fuzzy community structure in complex networks
Zhang, S., Wang, R., & Zhang, X.-S. (2007) · Physical Review E · doi:10.1103/physreve.76.046103 · Cited by 138
A Critical Point for Random Graphs with a Given Degree Sequence
Molloy, M. S. O., & Reed, B. A. (2011) · Princeton University Press eBooks · doi:10.1515/9781400841356.240 · Cited by 136
Detecting overlapping communities of weighted networks via a local algorithm
Chen, D., Shang, M., Lv, Z., & Fu, Y. (2010) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2010.05.046 · Cited by 135
When are networks truly modular?
Reichardt, J., & Bornholdt, S. (2006) · Physica D Nonlinear Phenomena · doi:10.1016/j.physd.2006.09.009 · Cited by 127
Parallel community detection on large networks with propinquity dynamics
Zhang, Y., Wang, J., Wang, Y., & Zhou, L. (2009) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1557019.1557127 · Cited by 126
The Naming Game in social networks: community formation and consensus engineering
Lu, Q., Korniss, G., & Szymanski, B. K. (2009) · Journal of Economic Interaction and Coordination · doi:10.1007/s11403-009-0057-7 · Cited by 110
Self-citationSynchronization Interfaces and Overlapping Communities in Complex Networks
Li, D., Leyva, I., Almendral, J. A., Sendiña–Nadal, I., Buldú, J. M., Havlin, S., & Boccaletti, S. (2008) · Physical Review Letters · doi:10.1103/physrevlett.101.168701 · Cited by 110
Finding Overlapping Communities Using Disjoint Community Detection Algorithms
Gregory, S. (2009) · Studies in computational intelligence · doi:10.1007/978-3-642-01206-8_5 · Cited by 97
Handbook of Optimization in Complex Networks
(2011) · Springer optimization and its applications · doi:10.1007/978-1-4614-0754-6 · Cited by 91
Havemann, F., Heinz, M., Struck, A., & Gläser, J. (2011) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2011/01/p01023 · Cited by 90
A Markov random walk under constraint for discovering overlapping communities in complex networks
Jin, D., Yang, B., Baquero, C., Liu, D., He, D., & Liu, J. (2011) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2011/05/p05031 · Cited by 86
Map equation for link communities
Kim, Y., & Jeong, H. (2011) · Physical Review E · doi:10.1103/physreve.84.026110 · Cited by 83
Simple probabilistic algorithm for detecting community structure
Ren, W., Yan, G., Liao, X., & Xiao, L. (2009) · Physical Review E · doi:10.1103/physreve.79.036111 · Cited by 75
Clearing the FOG: Fuzzy, overlapping groups for social networks
Davis, G. B., & Carley, K. M. (2008) · Social Networks · doi:10.1016/j.socnet.2008.03.001 · Cited by 74
A Fuzzy Variant of the Rand Index for Comparing Clustering Structures
Hüllermeier, E., & Rifqi, M. (2009) · HAL · Cited by 68
Multiplicative Mixture Models for Overlapping Clustering
Fu, Q., & Banerjee, A. (2008) · Proceedings · doi:10.1109/icdm.2008.103 · Cited by 52
Adjusting from disjoint to overlapping community detection of complex networks
Wang, X., Jiao, L., & Wu, J. (2009) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2009.08.032 · Cited by 51
Defining and Discovering Communities in Social Networks
Kelley, S., Goldberg, M., Magdon‐Ismail, M., Mertsalov, K., & Wallace, A. (2011) · Springer optimization and its applications · doi:10.1007/978-1-4614-0754-6_6 · Cited by 50
Self-citationThermodynamics of Community StructurePreprint
Massen, C. P., & Doye, J. P. K. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.cond-mat/0610077 · Cited by 45
Overlapping Community Detection by Collective Friendship Group Inference
Rees, B. S., & Gallagher, K. B. (2010) · IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) · doi:10.1109/asonam.2010.28 · Cited by 41
Detecting overlapping community structure of networks based on vertex–vertex correlations
Zarei, M., Izadi, D., & Samani, K. A. (2009) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2009/11/p11013 · Cited by 36
Overlapping Community Search for social networks
Padrol, A., Perarnau, G., Pfeifle, J., & Muntés-Mulero, V. (2010) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2010.5447860 · Cited by 35
Partitioning Breaks Communities
Reid, F., McDaid, A. F., & Hurley, N. (2011) · IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) · doi:10.1109/asonam.2011.36 · Cited by 21
Overlapping Community Detection by Kernel-Based Fuzzy Affinity Propagation
Ding, F., Luo, Z., Shi, J., & Fang, X. (2010) · International Workshop on Intelligent Systems and Applications (ISA) · doi:10.1109/iwisa.2010.5473438 · Cited by 20
Cited by
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
Defining 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
Challenges 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
Social big data: recent achievements and new challenges
Bello-Orgaz, G., Jung, J. J., & Camacho, D. (2016) · Information Fusion · doi:10.1016/j.inffus.2015.08.005 · Cited by 846
“[58] reviewed the state of the art in overlapping comunity detection algorithms.”
BackgroundCommunity Detection in Networks with Node Attributes
Yang, J., McAuley, J., & Leskovec, J. (2013) · 2013 IEEE 13th International Conference on Data Mining · doi:10.1109/icdm.2013.167 · Cited by 575
Metadata
- Authors
- Xie, J., Kelley, S., & Szymanski, B. K.
- Venue
- ACM Computing Surveys
- Published
- 2013-08
- Volume
- 45
- Issue
- 4
- Pages
- 1-35
- ISSN
- 0360-0300 (ISSN-L)
- 1557-7341
- OpenAlex
- W4292081303
- Cited by
- 930
- References
- 96
- FWCI
- 53.81
- 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.