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 different algorithms and proposes a framework to evaluate their ability to detect overlapping nodes, which helps assess over-detection and under-detection. The study finds that for low overlapping density networks, SLPA, OSLOM, Game, and COPRA perform better than other tested algorithms. For high overlapping density and diversity networks, both SLPA and Game show relatively stable performance, but the detection remains challenging. The paper also notes that in real-world networks, the fraction of overlapping nodes is typically less than 30%, and each node belongs to only 2 or 3 communities. The evaluation criteria used include Normalized Mutual Information (NMI) and the Omega index, which are adapted for overlapping communities. The paper discusses various benchmark networks, such as the GN benchmark and the LFR benchmark, and presents empirical results on synthetic networks to compare the performance of different algorithms.This paper reviews the state-of-the-art in overlapping community detection algorithms, quality measures, and benchmarks. It provides a thorough comparison of fourteen different algorithms and proposes a framework to evaluate their ability to detect overlapping nodes, which helps assess over-detection and under-detection. The study finds that for low overlapping density networks, SLPA, OSLOM, Game, and COPRA perform better than other tested algorithms. For high overlapping density and diversity networks, both SLPA and Game show relatively stable performance, but the detection remains challenging. The paper also notes that in real-world networks, the fraction of overlapping nodes is typically less than 30%, and each node belongs to only 2 or 3 communities. The evaluation criteria used include Normalized Mutual Information (NMI) and the Omega index, which are adapted for overlapping communities. The paper discusses various benchmark networks, such as the GN benchmark and the LFR benchmark, and presents empirical results on synthetic networks to compare the performance of different algorithms.