Abstract The mining and discovery of overlapping and hierarchical communities is a hot topic in the area of social network research. Firstly, an algorithm, discovery of link conmunities based on extended link cluster sequence (DLC_ECS), is proposed to detect overlapping and hierarchical communities in social networks efficiently. Based on the extended link cluster sequence corresponding to community structures with various densities, the optimal link community is detected after searching for the global optimal density. The link communities are transformed into the node communities, and thus the overlapping communities can be found out. Then, hierarchical link communities extraction based on extended link cluster sequence (HLCE_ECS) is designed. Hierarchical link communities from the extended link cluster sequence is found by the proposed algorithm. The link communities are transformed into the node communities to find out the overlapping and hierarchical communities. Experimental results on are artificial and real-world datasets demonstrate that DLC_ECS algorithm significantly improves the community quality and HLCE_ECS algorithm effectively discovers meaningful hierarchical communities.
GUO Hong,HUANG Jia-Xin,GUO Kun. Discovery of Overlapping and Hierarchical Communities Based on Extended Link Cluster Sequence[J]. , 2015, 28(9): 828-838.
[1] Lin Y F, Wang T Y, Tang R, et al. An Effective Model and Algorithm for Community Detection in Social Networks. Journal of Computer Research and Development, 2012, 49(2): 337-345 (in Chinese) (林友芳,王天宇,唐 锐,等.一种有效的社会网络社区发现模型和算法.计算机研究与发展, 2012, 49(2): 337-345) [2] Jiang Y W, Jia C Y, Yu J. Overlapping Community Detection in Complex Networks Based on Cluster Prototypes. Pattern Recognition and Artificial Intelligence, 2013, 26(7): 648-659 (in Chinese) (姜雅文,贾彩燕,于 剑.基于类原型的复杂网络重叠社区发现方法.模式识别与人工智能, 2013, 26(7): 648-659) [3] Liu D Y, Jin D, He D X, et al. Community Mining in Complex Networks. Journal of Computer Research and Development, 2013, 50(10): 2140-2154 (in Chinese) (刘大有,金 弟,何东晓,等.复杂网络社区挖掘综述.计算机研究与发展, 2013, 50(10): 2140-2154) [4] Fortunato S. Community Detection in Graphs. Physical Reports, 2010, 486(2/3/4/5): 75-174 [5] Shiga M, Takigawa I, Mamitsuka H. A Spectral Approach to Clus-tering Numerical Vectors as Nodes in a Networks. Pattern Recognition, 2011, 44(2): 236-251 [6] Guimerà R, Sales-Pardo M, Amaral L A N. Modularity from Fluctuations in Random Graphs and Complex Networks. Physical Review E, 2004. DOI: 10.1103/PhysRevE.70.025101 [7] Guimerà R, Amaral L A N. Functional Cartography of Complex Metabolic Networks. Nature, 2005, 433(7028): 895-900 [8] Duch J, Arenas A. Community Detection in Complex Networks Using Extremal Optimization. Physical Review E, 2005. DOI: 10.1103/PhysRevE.72.027104 [9] Girvan M, Newman M E J. Community Structure in Social and Biological Networks. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12): 7821-7826 [10] Wu F, Huberman B A. Finding Communities in Linear Time: A Physics Approach. The European Physical Journal B: Condensed Matter and Complex Systems, 2004, 38(2): 331-338 [11] Palla G, Derènyi I, Farkas I, et al. Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society. Nature, 2005, 435(7043): 814-818 [12] Evans T S. Clique Graphs and Overlapping Communities. Journal of Statistical Mechanics: Theory and Experiment, 2010. DOI:10.1088/1742-5468/2010/12/P12037 [13] Shen H W, Cheng X Q, Cai K, et al. Detect Overlapping and Hierarchical Community Structure in Networks. Physica A: Statistical Mechanics and Its Applications, 2009, 388(8): 1706-1712 [14] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast Unfolding of Communities in Large Networks. Journal of Statistical Mecha-nics: Theory and Experiment, 2008. DOI: 10.1088/1742-5468/2008/10/P10008 [15] Lancichinetti A, Fortunato S, Kertèsz J. Detecting the Overlapping and Hierarchical Community Structure in Complex Networks. New Journal of Physics, 2009. DOI:10.1088/1367-2630/11/3/033015 [16] Lee C, Reid F, McDaid A, et al. Detecting Highly Overlapping Community Structure by Greedy Clique Expansion // Proc of the 4th International Workshop on Social Network Mining and Analysis. Washington, USA, 2010: 33-42 [17] Gregory S. Finding Overlapping Communities in Networks by Label Propagation. New Journal of Physics, 2010. DOI: 10.1088/1367-2630/12/10/103018 [18] Wu Z H, Lin Y F, Gregory S, et al. Balanced Multi-label Propagation for Overlapping Community Detection in Social Networks. Journal of Computer Science and Technology, 2012, 27(3): 468-479 [19] Pan L, Jin J, Wang C J, et al. Detecting Link Communities Based on Local Information in Social Networks. Acta Electronica Sinica, 2012, 11(40): 2255-2263 (in Chinese) (潘 磊,金 杰,王崇骏,等.社会网络中基于局部信息的边社区挖掘.电子学报, 2012, 11(40): 2255-2263) [20] Ahn Y Y, Bagrow J P, Lehmann S. Link Communities Reveal Multiscale Complexity in Networks. Nature, 2010, 466(7307): 761-764 [21] Ball B, Karrer B, Newman M E J. Efficient and Principled Method for Detecting Communities in Networks. Physical Review E, 2011. DOI: 10.1103/PhysRevE.84.036103 [22] Yu L, Wu B, Wang B X. LBLP: Link-Clustering-Based Approach for Overlapping Community Detection. Tsinghua Science and Technology, 2013, 18(4): 387-397 [23] Shi C, Cai Y N, Fu D, et al. A Link Clustering Based Over-lapping Community Detection Algorithm. Data & Knowledge Engineering, 2013, 87: 394-404 [24] Kim Y, Jeong H. Map Equation for Link Communities. Physical Review E, 2011. DOI: 10.1103/PhysRevE.84.026110 [25] Rosvall M, Bergstrom C T. Map of Random Walks on Complex Networks Reveal Community Structure. Proceedings of National Academy of Science of the United States of America, 2008, 105(4): 1118-1123 [26] Zhu M, Meng F R, Zhou Y. Density-Based Link Clustering Algorithm for Overlapping Community Detection. Journal of Computer Research and Development, 2013, 50(12): 2520-2530 (in Chinese) (朱 牧,孟凡荣,周 勇.基于链接密度聚类的重叠社区发现算法.计算机研究与发展, 2013, 50(12): 2520-2530) [27] Huang J B, Sun H L, Bortner D, et al. Mining Hierarchical Community Structure within Networks from the Density-Connected Tra-veling Orders. Journal of Software, 2011, 22(5): 951-961 (in Chinese) (黄健斌,孙鹤立,Bortner D,等.从链接密度遍历序列中挖掘网络社团的层次结构.软件学报, 2011, 22(5): 951-961) [28] Lancichnetti A, Fortunato S. Benchmarks for Testing Community Detection Algorithms on Directed and Weighted Graphs with Overlapping Communities. Physical Review E, 2009. DOI: 10.1103/PhysRevE.78.046110 [29] McAuley J, Leskovec J. Learning to Discover Social Circles in Ego Networks // Proc of the 26th Annual Conference on Information Processing Systems. Lake Tahoe, USA, 2012: 548-556 [30] Zachary W W. An Information Flow Model for Conflict and Fission in Small Groups. Journal of Anthropological Research, 1977, 33(4): 452-473 [31] Girvan M, Newman M E J. Community Structure in Social and Biological Networks. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12): 7821-7826
2015, Vol. 28 
