基于边标签传播的复杂网络社区识别方法

doi:10.3969/j.issn.0372-2112.2015.06.012

电子学报 ›› 2015, Vol. 43 ›› Issue (6): 1113-1118.DOI: 10.3969/j.issn.0372-2112.2015.06.012

基于边标签传播的复杂网络社区识别方法

张健沛¹, 邓琨¹, 杨静¹, 刘星妍²

1. 哈尔滨工程大学计算机科学与技术学院, 黑龙江哈尔滨 150001;
2. 黑龙江省电子信息产品监督检验院, 黑龙江哈尔滨 150090

收稿日期:2014-03-31 修回日期:2014-05-21 出版日期:2015-06-25
- 通讯作者:
- 邓琨
- 作者简介:
- 张健沛 男,1956年生于黑龙江哈尔滨.哈尔滨工程大学计算机科学与技术学院教授、博士生导师.主要研究方向为数据库与知识工程、数据挖掘、复杂网络分析等. E-mail:zhangjianpei@hrbeu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61370083,No.61073043,No.61073041,No.61402126); 高等学校博士学科点专项科研基金 (No.20112304110011,No.20122304110012); 哈尔滨市科技创新人才研究专项资金 (优秀学科带头人) (No.2011RFXXG015)

Community Detection in Complex Networks Based on Link Label Propagation

ZHANG Jian-pei¹, DENG Kun¹, YANG Jing¹, LIU Xing-yan²

1. College of Computer Science and Technology, Harbin Engineering University, Harbin, Heilongjiang 150001, China;
2. Heilongjiang Province Electronic and Information Products Supervision Inspection Institute, Harbin, Heilongjiang 150090, China

Received:2014-03-31 Revised:2014-05-21 Online:2015-06-25 Published:2015-06-25

摘要/Abstract

摘要：

针对传统基于标签传播的复杂网络重叠社区识别算法难以准确识别重叠节点的缺陷,本文通过分析边与其邻居边的关系,提出用来评估边归属社区的归属密度函数及归属倾向性函数,并在此基础上设计一种基于边标签传播的重叠社区识别方法(OLLP).该方法首先以每条边连接2个节点中度高的节点标签作为该边的标签;然后通过分析边的归属密度与归属倾向性迭代更新边标签,最终标签相同的边属于同一社区.在基准网络与真实网络数据集上进行测试,并与多个具有代表性的算法进行比较,实验结果表明了OLLP算法的有效性和可行性.

关键词: 复杂网络, 重叠社区识别, 标签传播

Abstract:

Since traditional overlapping community detection methods in complex networks based on label propagation that could not detect overlapping nodes accurately, this paper presented link attribution density and link attribution orientation functions through analyzing the relationship between each link and its neighbor links to assess the attribution community of each link.On this basis, overlapping community detection method based on link label propagation (OLLP) was designed.Firstly, OLLP used the label of every link to the node label which possesses the higher degree when connected by the link, and then updated the label repeatedly through analyzing attribution density and attribution orientation of the link.Finally, identical label links were attributed to the same community.By testing on both synthetic and real-world networks, and comparing with multiple representative algorithms, the experimental results verify the validity and feasibility of OLLP.

Key words: complex networks, overlapping community detection, label propagation

中图分类号:

TP391.4

张健沛, 邓琨, 杨静, 刘星妍. 基于边标签传播的复杂网络社区识别方法[J]. 电子学报, 2015, 43(6): 1113-1118.

ZHANG Jian-pei, DENG Kun, YANG Jing, LIU Xing-yan. Community Detection in Complex Networks Based on Link Label Propagation[J]. Acta Electronica Sinica, 2015, 43(6): 1113-1118.

参考文献

[1] 金弟, 刘大有, 杨博, 等.基于局部探测的快速复杂网络聚类算法[J].电子学报, 2011, 11(39):2540-2546. Jin Di, Liu Da-You, Yang Bo, et al.Complex network clustering algorithm using local detection[J].Acta Electronica Sinica, 2011, 11(39):2540-2546.(in Chinese)
[2] Wang Z, Zhang J.In search of the biological significance of modular structures in protein networks[J].Plos Computational Biology, 2007, 3(6):e107.
[3] Cheng J, Cao J D, Zhang W Q, et al.Influential node control strategy for opinion evolution on social networks[J].Abstract and Applied Analysis, 2013, 2013:689495.
[4] Qian C, Cao J D, Lu J, et al.Adaptive bridge control strategy for opinion evolution on social networks[J].Chaos:An Interdisciplinary Journal of Nonlinear Science, 2011, 21(2):025116.
[5] Sidiropoulos A, Pallis G, Katsaros D, et al.Prefetching in content distribution networks via web communities identification and outsourcing[J].World Wide Web, 2008, 11(1):39-70.
[6] Palla G, Derenyi I, Farkas I, et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature, 2005, 435(7043):814-818.
[7] Shi C, Cai Y N, Fu D, et al.link clustering based overlapping community detection algorithm[J].Data & Knowledge Engineering, 2013, 87(9):394-404.
[8] Ahn Y Y, Bagrow J P, Lehmann S.Link communities reveal multi-scale complexity in networks[J].Nature, 2010, 466(7307):761-764.
[9] Steve G.Finding overlapping communities in networks by label propagation[J].New Journal of Physics, 2010, 12(10):103018.
[10] Wu Z H, Lin Y F, Steve G, et al.Balanced multi-label propagation for overlapping community detection in social networks[J].Journal of Computer Science and Technology, 2012, 27(3):468-479.
[11] Xie J R, Szymanski B K, Liu X.Slpa:uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[A].Proceedings of IEEE ICDM Workshop on DMCCI[C].Vancouver:IEEE, 2011.344-349.
[12] Newman M E J.Modularity and community structure in networks[J].Proceedings of the National Academy of Sciences of the United States of America, 2006, 103(23):8577-8582.
[13] Bagrow J P, Bolt E M.Local method for detecting communities[J].Physical Review E, 2005, 72(4):046108.
[14] Lancichinetti A, Fortunato S, Kertesz J.Detecting the overlapping and hierarchical community structure in complex networks[J].New Journal of Physics, 2009, 11(3):033015.
[15] Lancichinetti A, Fortunato S, Radicchi F.Benchmark graphs for testing community detection algorithms[J].Physical Review E, 2008, 78(4):046110.
[16] Shen H W, Cheng X Q, Cai K, et al.Detect overlapping and hierarchical community structure in networks[J].physical A:Statistical Mechanics and Its Applications, 2009, 388(8):1706-1712.
[17] Newman M E J .Network Data[DB/OL].http://www-personal.umich.edu/~mejn/netdata, 2014-02-01.
[18] Steve G.Network Research[DB/OL].http://www.cs.bris.ac.uk/~steve/networks/copra, 2014-02-01.
[19] Leskovec J.SNAP[DB/OL].http://snap.stanford.edu, 2014-05-10.

基于边标签传播的复杂网络社区识别方法

Community Detection in Complex Networks Based on Link Label Propagation

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	江兵兵, 何文达, 吴兴宇, 项俊浩, 洪立斌, 盛伟国. 基于自适应图学习的半监督特征选择[J]. 电子学报, 2022, 50(7): 1643-1652.
[2]	张磊, 刘庆, 杨尚尚, 杨海鹏, 程凡, 马海平. 基于双编码的重叠社团检测多目标优化方法[J]. 电子学报, 2021, 49(11): 2101-2107.
[3]	胡钢, 高浩, 徐翔, 许丽鹏. 基于重要度传输矩阵的复杂网络节点重要性辨识方法[J]. 电子学报, 2020, 48(12): 2402-2408.
[4]	王尔申, 王玉伟, 庞涛, 曲萍萍, 姜毅. 基于边攻击成本的复杂网络鲁棒性研究[J]. 电子学报, 2018, 46(5): 1166-1172.
[5]	何鹏, 王鹏, 李兵, 胡思文. 基于多粒度软件网络模型的软件系统演化分析[J]. 电子学报, 2018, 46(2): 257-267.
[6]	刘世超, 朱福喜, 冯曦. 复杂网络的重叠社区及社区间的结构洞识别[J]. 电子学报, 2016, 44(11): 2600-2606.
[7]	王诗懿, 董一鸿, 李志超, 陈华辉, 钱江波. 大规模复杂网络下重叠社区的识别[J]. 电子学报, 2015, 43(8): 1575-1582.
[8]	国琳, 左万利. 基于兴趣图谱的用户兴趣分布分析及专家发现[J]. 电子学报, 2015, 43(8): 1561-1567.
[9]	冷作福. 基于贪婪优化技术的网络社区发现算法研究[J]. 电子学报, 2014, 42(4): 723-729.
[10]	潘伟丰, 李兵, 马于涛, 刘婧. 基于复杂软件网络的回归测试用例优先级排序[J]. 电子学报, 2012, 40(12): 2456-2465.
[11]	张健沛, 李泓波, 杨静, 白劲波, 张乐君, 初妍. 基于归属不确定性的变规模网络重叠社区识别[J]. 电子学报, 2012, 40(12): 2512-2518.
[12]	汤进;陈展展;罗斌;孙登第. 基于复杂网络和最优子序列双射的形状描述与匹配[J]. 电子学报, 2011, 39(8): 1757-1765.
[13]	金弟;刘大有;杨博;刘杰;何东晓;田野. 基于局部探测的快速复杂网络聚类算法[J]. 电子学报, 2011, 39(11): 2540-2546.
[14]	万佑红;王锁萍;蒋国平. 基于观测器的复杂网络辨识新方法研究[J]. 电子学报, 2010, 38(5): 1064-1068.
[15]	王雪松;谷阳阳;程玉虎. 基于复杂网络的时延基因调控网络构建[J]. 电子学报, 2010, 38(11): 2518-2522.