Overlapping Community Detection in Networks: the State of the Art and Comparative Study

Overlapping Community Detection in Networks: the State of the Art and Comparative Study

vol. 45, no. 4, 2013 (In press) | JIERUI XIE, STEPHEN KELLEY and BOLESLAW K. SZYMANSKI
This paper reviews the state of the art in overlapping community detection algorithms, quality measures, and benchmarks. It provides a thorough comparison of fourteen algorithms, including community-level evaluation and a framework for assessing the ability to detect overlapping nodes. After considering community-level detection performance using Normalized Mutual Information, the Omega index, and node-level performance using F-score, the following conclusions are reached: for low overlapping density networks, SLPA, OSLOM, Game, and COPRA perform better than other tested algorithms. For high overlapping density and diversity networks, SLPA and Game provide relatively stable performance. However, detection in such networks is still not fully resolved. A common feature in real-world networks is the relatively small fraction of overlapping nodes (typically less than 30%), each belonging to only 2 or 3 communities. The paper discusses various algorithms for overlapping community detection, including clique percolation, line graph and link partitioning, local expansion and optimization, fuzzy detection, agent-based and dynamical algorithms, and others. It also presents evaluation criteria such as Normalized Mutual Information and Omega Index, and benchmarks like the LFR model, which introduces heterogeneity into degree and community size distributions. The paper evaluates the performance of different algorithms on synthetic networks, finding that SLPA, OSLOM, and Game perform well in various scenarios. The results highlight the importance of considering overlapping structures in community detection and the need for further research to improve detection accuracy in complex networks.This paper reviews the state of the art in overlapping community detection algorithms, quality measures, and benchmarks. It provides a thorough comparison of fourteen algorithms, including community-level evaluation and a framework for assessing the ability to detect overlapping nodes. After considering community-level detection performance using Normalized Mutual Information, the Omega index, and node-level performance using F-score, the following conclusions are reached: for low overlapping density networks, SLPA, OSLOM, Game, and COPRA perform better than other tested algorithms. For high overlapping density and diversity networks, SLPA and Game provide relatively stable performance. However, detection in such networks is still not fully resolved. A common feature in real-world networks is the relatively small fraction of overlapping nodes (typically less than 30%), each belonging to only 2 or 3 communities. The paper discusses various algorithms for overlapping community detection, including clique percolation, line graph and link partitioning, local expansion and optimization, fuzzy detection, agent-based and dynamical algorithms, and others. It also presents evaluation criteria such as Normalized Mutual Information and Omega Index, and benchmarks like the LFR model, which introduces heterogeneity into degree and community size distributions. The paper evaluates the performance of different algorithms on synthetic networks, finding that SLPA, OSLOM, and Game perform well in various scenarios. The results highlight the importance of considering overlapping structures in community detection and the need for further research to improve detection accuracy in complex networks.
Reach us at info@study.space