《计算机应用研究》|Application Research of Computers

基于种子节点选择的重叠社区发现算法

Overlapping community detection algorithm based on selection of seed nodes

免费全文下载 (已被下载 次)  
获取PDF全文
作者 齐金山,梁循,王怡
机构 1.中国人民大学 信息学院,北京 100872;2.淮阴师范学院 计算机科学与技术学院,江苏 淮安 223300
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2017)12-3534-04
DOI 10.3969/j.issn.1001-3695.2017.12.003
摘要 针对目前从局部社区扩展成全局社区时有关算法的种子节点选择不合理的情形,提出了一种基于种子节点选择的重叠社区发现算法。首先根据影响力函数找出局部影响力最大的节点,由这些节点构成的种子集合较好地分布在整个网络中,然后以这些种子点构造初始社区,根据设定的吸引度函数选择性地添加节点来进行社区扩展。实验结果表明,该算法在真实网络上进行测试时能够有效地挖掘网络中的重叠社区。
关键词 重叠社区;局部社区;吸引度函数;社区扩展
基金项目 国家自然科学基金资助项目(71271211,71531012)
北京市自然科学基金资助项目(4132067)
中国人民大学品牌计划资助项目(10XNI029)
本文URL http://www.arocmag.com/article/01-2017-12-003.html
英文标题 Overlapping community detection algorithm based on selection of seed nodes
作者英文名 Qi Jinshan, Liang Xun, Wang Yi
机构英文名 1.SchoolofInformation,RenminUniversityofChina,Beijing100872,China;2.SchoolofComputerScience&Technology,HuaiyinNormalUniversity,Huai'anJiangsu223300,China
英文摘要 In view of the unreasonable selection in seed algorithm from the local community expanding into a global community at present, this paper proposed an overlapping community detection algorithm based on selection of the seed nodes. The algorithm used the influence function to find out the strongest nodes in local node influences, which structured the seeds distributing throughout the network. And then utilized these seeds to construct the initial community, selectively added nodes to expand the community according to the set attraction function. The experimental results show that the algorithm tested in a real network can effectively dig out overlapping community in the network.
英文关键词 overlapping community; local community; attraction function; community expansion
参考文献 查看稿件参考文献
  [1] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities in large networks[J] . Journal of Statistical Mechanics Theory & Experiment, 2008, 2008(10):155-168.
[2] Shiga M, Takigawa I, Mamitsuka H. A spectral clustering approach to optimally combining numerical vectors with a modular network[C] //Proc of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2007:647-656.
[3] White S, Smyth P. A spectral clustering approach to finding communities in graph[C] //Proc of SIAM International Conference on Data Mining. 2005:76-84.
[4] Donetti L, Muoz M A. Improved spectral algorithm for the detection of network communities[C] //Proc of the 8th Granada Seminar on Computational and Statistical Physics. 2005:104-107.
[5] Jiang J Q, Dress A W M, Yang Genke. A spectral clustering-based framework for detecting community structures in complex networks[J] . Applied Mathematics Letters, 2009, 22(9):1479-1482.
[6] Newman M E. Fast algorithm for detecting community structure in networks[J] . Physical Review E:Statistical Nonlinear & Soft Matter Physics, 2004, 69(6):066133.
[7] Clauset A, Newman M E, Moore C. Finding community structure in very large networks[J] . Physical Review E:Statistical Nonlinear & Soft Matter Physics, 2005, 70(6):264-277.
[8] Guimera R, Amaral L A N. Functional cartography of complex metabolic networks[J] . Nature, 2005, 433(7028):895-900.
[9] Palla G, Derenyi I, Farkas I, et al. Uncovering the overlapping community structures of complex networks in nature and society[J] . Nature, 2005, 435(7043):814-818.
[10] Kumpula J M, Kivel M, Kaski K, et al. Sequential algorithm for fast clique percolation[J] . Physical Review E:Statistical Nonlinear & Soft Matter Physics, 2008, 78(2):1815-1824.
[11] Farkas I, Abel D, Palla G, et al. Weighted network modules[J] . New Journal of Physics, 2007, 9(6):180.
[12] Gregory S. Finding overlapping communities in networks by label propagation[J] . New Journal of Physics, , 2009, 12(10):2011-2024.
[13] Ahn Y Y, Bagrow J P, Lehmann S. Link communities reveal muhiscale complexity in networks[J] . Nature, 2010, 466(7307):761-764.
[14] Ball B, Karrer B, Newman M E. Efficient and principled method for detecting communities in networks[J] . Physical Review E:Statistical Nonlinear & Soft Matter Physics, 2011, 84(3):109-134.
[15] Kim Y, Jeong H. Map equation for link communities[J] . Physical Review E:Statistical Nonlinear & Soft Matter Physics, 2011, 84(2):1402-1409.
[16] Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure of complex networks[J] . New Journal of Physics, 2009, 11(3):19-44.
[17] 淦文燕, 赫南, 李德毅, 等. 一种基于拓扑势的网络社区发现方法[J] . 软件学报, 2009, 20(8):2241-2254.
[18] Wang Zhixiao, Li Zechao, Ding Xiaofang, et al. Overlapping community detection based on node location analysis[J] . Knowledge-Based Systems, 2016, 105:225-235.
[19] 许加书, 韩忠愿, 顾惠健. 基于节点拓扑结构和属性的重叠社区检测算法[J] . 计算机应用研究, 2016, 33(12):3615-3619.
[20] Shen Huawei, Cheng Xueqi, Cai Kai, et al. Detect overlapping and hierarchical community structure in networks[J] . Physica A:Statistical Mechanics & Its Applications, 2008, 388(8):1706-1712.
[21] Gargi U, Lu Wenjun, Mirrokni V S, et al. Large-scale community detection on Youtube for topic discovery and exploration[C] //Proc of the 5th International Conference on Weblogs and Social Media. 2011:486-489.
[22] Coscia M, Rossetti G, Giannotti F, et al. DEMON:a local-first discovery method for overlapping communities[C] //Proc of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2012:615-623.
[23] Chen Qiong, Fang Ming. An efficient algorithm for community detection in complex networks[C] //Proc of the 6th Workshop on Social Network Mining and Analysis. 2012.
[24] Whang J J, Gleich D F, Dhillon I S. Overlapping community detection using seed set expansion[C] //Proc of ACM International Confe-rence on Conference on Information & Knowledge Management. New York:ACM Press, 2013:2099-2108.
[25] Andersen R, Lang K J. Communities from seed sets[C] //Proc of International Conference on World Wide Web. New York:ACM Press, 2006:223-232.
收稿日期 2016/9/5
修回日期 2016/10/31
页码 3534-3537,3568
中图分类号 TP301.6
文献标志码 A