Overlapping community detection in networks
Top Cited Papers
- 30 August 2013
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
- Vol. 45 (4), 1-35
- https://doi.org/10.1145/2501654.2501657
Abstract
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.Keywords
Other Versions
Funding Information
- Office of Naval Research (N00014-09-1-0607)
- U.S. Army Research Laboratory
This publication has 84 references indexed in Scilit:
- Finding Statistically Significant Communities in NetworksPLOS ONE, 2011
- Community Landscapes: An Integrative Approach to Determine Overlapping Network Module Hierarchy, Identify Key Nodes and Predict Network DynamicsPLOS ONE, 2010
- Link communities reveal multiscale complexity in networksNature, 2010
- WGCNA: an R package for weighted correlation network analysisBMC Bioinformatics, 2008
- Synchronization Interfaces and Overlapping Communities in Complex NetworksPhysical Review Letters, 2008
- Maps of random walks on complex networks reveal community structureProceedings of the National Academy of Sciences of the United States of America, 2008
- Mixture models and exploratory analysis in networksProceedings of the National Academy of Sciences of the United States of America, 2007
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005
- Comparing partitionsJournal of Classification, 1985
- On cliques in graphsIsrael Journal of Mathematics, 1965