Detecting Overlapping Communities Based on Community Cores in Complex Networks
SHANG Ming-Sheng1, CHEN Duan-Bing1, ZHOU Tao1,2
1Web Sciences Center, School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 610054 2Department of Modern Physics, University of Science and Technology of China, Hefei 230026
Detecting Overlapping Communities Based on Community Cores in Complex Networks
SHANG Ming-Sheng1, CHEN Duan-Bing1, ZHOU Tao1,2
1Web Sciences Center, School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 610054 2Department of Modern Physics, University of Science and Technology of China, Hefei 230026
摘要The identification of communities is significant for the understanding of network structures and functions. Since some nodes naturally belong to several communities, the study of overlapping community structures has attracted increasing attention recently, and many algorithms have been designed to detect overlapping communities. We propose a new algorithm. The main idea is first to find the core of a community by detecting maximal cliques and then merging some tight community cores to form the community. Experimental results on two real networks demonstrate that the present algorithm is more accurate for detecting overlapping community structures, compared with some well-known results and methods.
Abstract:The identification of communities is significant for the understanding of network structures and functions. Since some nodes naturally belong to several communities, the study of overlapping community structures has attracted increasing attention recently, and many algorithms have been designed to detect overlapping communities. We propose a new algorithm. The main idea is first to find the core of a community by detecting maximal cliques and then merging some tight community cores to form the community. Experimental results on two real networks demonstrate that the present algorithm is more accurate for detecting overlapping community structures, compared with some well-known results and methods.
SHANG Ming-Sheng;CHEN Duan-Bing;ZHOU Tao;. Detecting Overlapping Communities Based on Community Cores in Complex Networks[J]. 中国物理快报, 2010, 27(5): 58901-058901.
SHANG Ming-Sheng, CHEN Duan-Bing, ZHOU Tao,. Detecting Overlapping Communities Based on Community Cores in Complex Networks. Chin. Phys. Lett., 2010, 27(5): 58901-058901.
[1] Newman M E J 2003 SIAM Rev. 45 167 [2] Albert R and Barabasi A L 2002 Rev. Mod. Phys. 74 47 [3] Strogatz S H 2001 Nature 410 268 [4] Fortunato S 2010 Phys. Rep. 486 75 [5] Fiedler M 1973 Czech Math. J. 23 298 [6] Kernighan B W and Lin S 1970 Bell. Syst. Tech. J. 49 291 [7] Newman M E J and Girvan M 2004 Phys. Rev. E 69 026113 [8] Newman M E J 2004 Phys. Rev. E 69 066133 [9] Clauset A, Newman M E J and Moore C 2004 Phys. Rev. E 70 066111 [10] Xiang B, Chen E H and Zhou T 2009 Studies in Computational Intelligence (Catania, Italy 26--27 May 2009) 207 73 [11] Ruan J H and Zhang W X 2008 Phys. Rev. E 77 016104 [12] Duch J and Arenas A 2005 Phys. Rev. E 72 027104 [13] Wang X T, Chen G R and Lu H T 2007 Physica A 384 667 [14] Newman M E J 2006 Phys. Rev. E 74 036104 [15] Chen D B, Fu Y and Shang M S 2009 Physica A 388 2741 [16] Palla G, Derényi I, Farkas I and Vicsek T 2005 Nature 435 814 [17] Evans T S and Lambiotte R 2009 Phys. Rev. E 80 016105 [18] Shen H W, Cheng X Q and Guo J F 2009 J. Stat. Mech. P07042 [19] Zhang S, Wang R S and Zhang X S 2007 Physica A 374 483 [20] Chen D B, Fu Y and Shang M S 2009 Proc. Global Congress on Intelligent Systems (Xiamen, China 19--21 May 2009) p 244 [21] Gregory S 2009 Studies in Computational Intelligence (Catania, Italy 26--27 May 2009) 207 47 [22] Girvan M and Newman M E J 2002 Proc. Natl. Acad. Sci. U.S.A. 99 7821 [23] Zachary W W 1977 J. Anth. Res. 33 452 [24] Xiao W K, Ren J, Qi F, Song Z W, Zhu M X, Yang H F, Jin H Y, Wang B H and Zhou T 2007 Phys. Rev. E 76 037102 [25] Yang H X, Wang B H, Liu J G, Han X P and Zhou T 2008 Chin. Phys. Lett. 25 2718 [26] Shi J J, Wang Y L and He D R 2009 Chin. Phys. Lett. 26 078902 [27] Zhou Y Z, Liu Z H and Zhou J 2007 Chin. Phys. Lett. 24 581 [28] Fortunato S and Barthelemy M 2007 Proc. Natl. Acad. Sci. U.S.A. 104 36 [29] Nicosia V, Mangioni G, Carchiolo V and Malgeri M 2009 J. Stat. Mech. P03024 [30] Shang M S and Zhang Z K 2009 Chin. Phys. Lett. 26 118903 [31] Zhou T, Kuscsik Z,Liu J G, Medo M, Wakeling J R and Zhang Y C 2010 Proc. Natl. Acad. Sci. U.S.A. 107 451199