基于影响力与种子扩展的重叠社区发现

doi:10.3969/j.issn.0372-2112.2019.01.020

电子学报 ›› 2019, Vol. 47 ›› Issue (1): 153-160.DOI: 10.3969/j.issn.0372-2112.2019.01.020

基于影响力与种子扩展的重叠社区发现

於志勇^1,2,3, 陈基杰^1,2,3, 郭昆^1,2,3, 陈羽中^1,2,3, 许倩⁴

1. 福州大学数学与计算机科学学院, 福建福州 350116;
2. 福建省网络计算与智能信息处理重点实验室, 福建福州 350116;
3. 空间数据挖掘与信息共享教育部重点实验室, 福建福州 350116;
4. 国网信通亿力科技有限责任公司, 福建福州 350003

收稿日期:2018-01-29 修回日期:2018-07-11 出版日期:2019-01-25
- 通讯作者:
- 郭昆
- 作者简介:
- 於志勇 男,1982年生于湖北黄梅.现为福州大学数学与计算机科学学院副教授.研究方向为移动社会网络、普适计算.E-mail:yuzhiyong@fzu.edu.cn;陈基杰 男,1993年生于福建三明.现为福州大学数学与计算机科学学院研究生.研究方向为数据挖掘、社交网络.E-mail:jackie_cute@163.com;陈羽中 男,1979年生于福建福州.现为福州大学数学与计算机科学学院教授.研究方向为云计算虚拟化技术、网络信息安全.E-mail:yzchen@fzu.edu.cn;许倩女,1984年生于福建惠安.现为国网信通亿力科技有限责任公司业务咨询师.研究方向为大数据挖掘、通信、软件工程.E-mail:150332181@qq.com
- 基金资助:
- 国家自然科学基金 (No.61300104，No.61772136，No.61672158）; 福建省高校杰出青年科学基金 (No.JA12016）; 福建省高等学校新世纪优秀人才支持计划 (No.JA13021）; 福建省杰出青年科学基金 (No.2014J06017，No.2015J06014）; 福建省科技创新平台计划 (No.2009J1007，No.2014H2005）; 福建省自然科学基金 (No.2013J01230，No.2014J01232）; 福建省高校产学合作项目 (No.2014H6014，No.2017H6008）; 海西政务大数据应用协同创新中心

Overlapping Community Detection Based on Influence and Seeds Extension

YU Zhi-yong^1,2,3, CHEN Ji-jie^1,2,3, GUO Kun^1,2,3, CHEN Yu-zhong^1,2,3, XU Qian⁴

1. College of Mathematics and Computer Sciences, Fuzhou University, Fuzhou, Fujian 350116, China;
2. Fujian Provincial Key Laboratory of Network Computing and Intelligent Information Processing, Fuzhou, Fujian 350116, China;
3. Ministry of Education Key Laboratory of Spatial Data Mining & Information Sharing, Fuzhou, Fujian 350116, China;
4. State Grid Info-Telecom Great Power Science and Technology Co. Ltd., Fuzhou, Fujian 350003, China

Received:2018-01-29 Revised:2018-07-11 Online:2019-01-25 Published:2019-01-25

摘要/Abstract

摘要： 社区发现作为复杂社交网络中一个重要的研究方向.针对目前基于种子节点的算法在种子选取与扩展等方面的不足，提出了一种基于影响力与种子扩展的重叠社区发现算法（Influence Seeds Extension Overlapping Community Detection，简称i-SEOCD算法）.首先，利用节点影响力策略找出具有紧密结构的种子社区.其次，从这些种子社区出发，计算社区邻居集节点与社区的相似度，并取出相似度超过设定阈值的节点.然后，采用优化自适应函数的策略来扩展社区.最后，对网络中的自由节点进行社区隶属划分，进而实现了整个网络的重叠社区结构挖掘.在真实社交网络和人工生成网络上实验表明，i-SEOCD算法能够准确、快速地发现复杂网络中的重叠社区结构.

关键词: 局部社区发现, 种子扩展, 节点影响力, 重叠社区

Abstract: Community detection is a significant research direction in the research of social networks.To improve the quality of seeds selection and expansion,we propose an influence seeds extension overlapping community detection (i-SEOCD) algorithm for overlapping community detection.First,i-SEOCD uses a node influence strategy to find the seed communities with tight structures.Second,on the basis of the seed communities,we calculate the similarity among communities and their neighbor nodes.The nodes whose similarity is greater than a predefined threshold are selected.Third,the strategy of optimizing a self-adaptive function is adopted to expand the communities.Finally,the free nodes in the network are assigned to their corresponding communities in order to find out all the overlapping community structures.Experiments on the real and artificial networks show that i-SEOCD is capable of discovering overlapping communities in complex social networks efficiently.

Key words: local community detection, seeds extension, node influence, overlapping community

中图分类号:

TP393

於志勇, 陈基杰, 郭昆, 陈羽中, 许倩. 基于影响力与种子扩展的重叠社区发现[J]. 电子学报, 2019, 47(1): 153-160.

YU Zhi-yong, CHEN Ji-jie, GUO Kun, CHEN Yu-zhong, XU Qian. Overlapping Community Detection Based on Influence and Seeds Extension[J]. Acta Electronica Sinica, 2019, 47(1): 153-160.

参考文献

[1] Newman M E.The structure of scientific collaboration networks[J].Proceedings of the National Academy of Sciences of the United States of America,2001,98(2):404-409.
[2] Fortunato S.Community detection in graphs[J].Physics Reports,2012,486(3):75-174.
[3] Radicchi F,Castellano C,Cecconi F,et al.Defining and identifying communities in networks[J].Proceedings of theNational Academy of Sciences of the United States of America,2003,101(9):2658.
[4] Girvan M,Newman M E.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[5] Luxburg,Ulrike.A tutorial on spectral clustering[J].Statistics & Computing,2007,17(4):395-416.
[6] Palla G,Derényi I,Farkas I,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814.
[7] Kim Y,Jeong H.Map equation for link communities[J].Physical Review E,2011,84(2):026110.
[8] Xie J,Szymanski B K.Towards linear time overlapping community detection in social networks[A].Pacific-Asia Conference on Knowledge Discovery and Data Mining[C].Springer,Berlin,Heidelberg,2012.25-36.
[9] Lancichinetti A,Fortunato S,Kertész J.Detecting the overlapping and hierarchical community structure in complex networks[J].New Journal of Physics,2009,11(3):033015.
[10] Coscia M,Rossetti G,Giannotti F,et al.Demon:a local-first discovery method for overlapping communities[A].Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].ACM,2012.615-623.
[11] Su Y,Wang B,Zhang X.A seed-expanding method based on random walks for community detection in networks with ambiguous community structures[J].Scientific Reports,2017,7:41830.
[12] Chen Q,Wu T T,Fang M.Detecting local community structures in complex networks based on local degree central nodes[J].Physica A:Statistical Mechanics and Its Applications,2013,392(3):529-537.
[13] Whang J J,Gleich D F,Dhillon I S.Overlapping community detection using neighborhood-inflated seed expansion[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(5):1272-1284.
[14] Cravino N,Figueira Á.Community detection by local influence[A].Advances in Information Systems and Technologies[M].Springer,Berlin,Heidelberg,2013.193-200.
[15] Wang X,Liu G,Li J.Overlapping community detection based on structural centrality in complex networks[J].IEEE Access,2017,5:25258-25269.
[16] Jaccard P.Etude de la distribution florale dans une portion des Alpes et du Jura[J].Bulletin De La Societe Vaudoise Des Sciences Naturelles,1901,37(142):547-579.
[17] Zachary W W.An information flow model for conflict and fission in small groups[J].Journal of anthropological research,1977,33(4):452-473.
[18] Lusseau D,Schneider K,Boisseau O J,et al.The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.
[19] Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical review E,2004,69(2):026113.
[20] Gleiser P M,Danon L.Community structure in jazz[J].Advances in Complex Systems,2003,6(04):565-573.
[21] Leskovec J,Kleinberg J,Faloutsos C.Graph evolution:densification and shrinking diameters[J].ACM Transactions on Knowledge Discovery from Data (TKDD),2007,1(1):2.
[22] Lancichinetti A,Fortunato S,Radicchi F.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4):046110.
[23] Shen H,Cheng X,Cai K,et al.Detect overlapping and hierarchical community structure in networks[J].Physica A:Statistical Mechanics and Its Applications,2009,388(8):1706-1712.
[24] Danon L,Diaz-Guilera A,Duch J,et al.Comparing community structure identification[J].Journal of Statistical Mechanics:Theory and Experiment,2005,2005(09):P09008.

基于影响力与种子扩展的重叠社区发现

Overlapping Community Detection Based on Influence and Seeds Extension

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

编辑推荐

Metrics

[1]	李辉, 张建朋, 陈福才. 基于流式分析的大规模网络重叠社区发现算法[J]. 电子学报, 2022, 50(8): 1951-1958.
[2]	刘露, 胡封晔, 牛亮, 彭涛. 异质网络中基于节点影响力的相似度度量方法[J]. 电子学报, 2019, 47(9): 1929-1936.
[3]	潘剑飞, 董一鸿, 陈华辉, 钱江波, 戴明洋. 基于结构紧密性的重叠社区发现算法[J]. 电子学报, 2019, 47(1): 145-152.
[4]	马慧芳, 谢蒙, 何廷年, 蔺想红. 基于核心标签的可重叠微博网络社区划分方法[J]. 电子学报, 2017, 45(4): 769-776.
[5]	国琳, 左万利, 彭涛. 基于隶属度的社会化网络重叠社区发现及动态集群演化分析[J]. 电子学报, 2016, 44(3): 587-594.
[6]	李泽鹏, 左杨, 王宏宇. 基于社交网络结构的节点影响力度量方法[J]. 电子学报, 2016, 44(12): 2967-2974.
[7]	刘世超, 朱福喜, 冯曦. 复杂网络的重叠社区及社区间的结构洞识别[J]. 电子学报, 2016, 44(11): 2600-2606.
[8]	王诗懿, 董一鸿, 李志超, 陈华辉, 钱江波. 大规模复杂网络下重叠社区的识别[J]. 电子学报, 2015, 43(8): 1575-1582.
[9]	张桂杰, 张健沛, 杨静, 辛宇. 基于链接相似性聚类的重叠社区识别[J]. 电子学报, 2015, 43(7): 1329-1335.
[10]	张健沛, 邓琨, 杨静, 刘星妍. 基于边标签传播的复杂网络社区识别方法[J]. 电子学报, 2015, 43(6): 1113-1118.
[11]	李泓波, 张健沛, 杨静, 白劲波, 初妍. 基于拓扑势的重叠社区及社区间结构洞识别——兼论结构洞理论视角下网络的脆弱性[J]. 电子学报, 2014, 42(1): 62-69.
[12]	张健沛, 李泓波, 杨静, 白劲波, 张乐君, 初妍. 基于归属不确定性的变规模网络重叠社区识别[J]. 电子学报, 2012, 40(12): 2512-2518.