基于多核心标签传播的复杂网络重叠社区识别方法

doi:10.11959/j.issn.1000-436x.2017028

通信学报 ›› 2017, Vol. 38 ›› Issue (2): 53-66.doi: 10.11959/j.issn.1000-436x.2017028

基于多核心标签传播的复杂网络重叠社区识别方法

邓琨¹(),李文平¹,余法红¹,张健沛²

¹ 嘉兴学院数理与信息工程学院，浙江嘉兴 314001
² 哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨 150001

出版日期:2017-02-01 发布日期:2017-07-20
作者简介:邓琨（1980-），男，黑龙江哈尔滨人，博士，嘉兴学院讲师，主要研究方向为数据挖掘、复杂网络结构分析等。|李文平（1979-），男，贵州大方人，博士，嘉兴学院讲师，主要研究方向为数据挖掘、隐私保护等。|余法红（1977-），男，湖北监利人，嘉兴学院讲师，主要研究方向为复杂网络、智能计算、大数据分析等。|张健沛（1956-），男，黑龙江哈尔滨人，博士，哈尔滨工程大学教授、博士生导师，主要研究方向为数据库理论与应用、数据挖掘、复杂网络等。
基金资助:
国家自然科学基金资助项目(61672179);国家自然科学基金资助项目(61370083);国家自然科学基金资助项目(61402126);教育部人文社会科学研究青年基金资助项目(15YJCZH088);浙江省自然科学基金资助项目(LY16F020027);浙江省教育厅科研基金资助项目(Y201636127);浙江省教育厅科研基金资助项目(Y201533771)

Overlapping community detection in complex networks based on multi kernel label propagation

Kun DENG¹(),Wen-ping LI¹,Fa-hong YU¹,Jian-pei ZHANG²

¹ College of Mathematics Physics and Information Engineering,Jiaxing University,Jiaxing 314001,China
² College of Computer Science and Technology,Harbin Engineering University,Harbin 150001,China

Online:2017-02-01 Published:2017-07-20
Supported by:
The National Natural Science Foundation of China(61672179);The National Natural Science Foundation of China(61370083);The National Natural Science Foundation of China(61402126);The Hu-manity and Social Science Youth Foundation of Ministry of Education of China(15YJCZH088);Zhejiang Provincial Natural Science Foundation of China(LY16F020027);Zhejiang Provincial Education Department Research Foundation of China(Y201636127);Zhejiang Provincial Education Department Research Foundation of China(Y201533771)

摘要/Abstract

摘要：

针对传统基于标签传播的重叠社区识别方法存在较强的随机性，以及需要预设相关阈值来辅助完成社区识别等缺陷，提出基于多核心标签传播的重叠社区识别方法(OMKLP)。在分析节点度以及节点与邻居节点的局部覆盖密度后提出核心节点评价模型，并在此基础上给出局部核心节点识别方法；基于局部核心节点，提出新的面向重叠社区的异步标签传播策略，该策略能够快速地识别出社区内部节点与边界节点，以获得重叠社区结构；提出重叠节点分析方法，进一步提高识别重叠节点准确度。OMKLP 算法无需掌握任何先验知识，仅在掌握网络基本信息(点、边)基础上，便能够准确识别出重叠社区结构，从而有效解决了传统标签传播算法所存在的缺陷。在基准网络和真实网络上进行测试，并与多个经典算法进行对比分析，实验结果验证了所提算法的有效性和可行性。

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

Abstract:

In view of the strong randomness and pre-setting the related threshold of traditional overlapping community detection method based on label propagation,overlapping community detection in complex networks based on multi kernel label propagation (OMKLP) was proposed.Evaluation model of kernel nodes was proposed after analyzing the node's degree and local covering density of nodes and their neighbor nodes.And on this basis,the detection method of local kernel nodes was also presented.Based on local kernel nodes,a new asynchronous label propagation strategy ori-ented to overlapping community was proposed,which can rapidly distinguish inner nodes and outer nodes of communi-ties so as to obtain overlapping community structure.The analysis method of overlapping nodes was proposed to increase the accuracy of detecting overlapping nodes.Without any prior knowledge,only on the basis of the basic network infor-mation (nodes and links),the algorithm can detect the structure of overlapping communities accurately.Therefore,it ef-fectively solved the defect of the traditional label propagation algorithm.The algorithm was tested over benchmark net-works and real-world networks and also compared with some classic algorithms.The experiment results verify the valid-ity and feasibility of OMKLP.

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

中图分类号:

TP391

邓琨,李文平,余法红,张健沛. 基于多核心标签传播的复杂网络重叠社区识别方法[J]. 通信学报, 2017, 38(2): 53-66.

Kun DENG,Wen-ping LI,Fa-hong YU,Jian-pei ZHANG. Overlapping community detection in complex networks based on multi kernel label propagation[J]. Journal on Communications, 2017, 38(2): 53-66.

图/表 15

图1

图2

图3

表1

各算法的时间复杂度对比"

序号	算法	时间复杂度
1	LFM	O(n² )
2	COPRA	$O (s m \log (\frac{s m}{n}))$
3	LC	$O (n k_{\max}^{2})$
4	SLPA	O(tm)
5	OMKLP	O(jnk²)

表1

表2

图4

图5

图6

图7

表3

表4

图8

图9

图10

图11

参考文献 37

[1]	WATTS D J , STROGATZ S H . Collective dynamics of “small-world”networks[J]. Nature, 1998,393(84): 440-442.
[2]	BARABáSI A L , ALBERT R . Emergence of scaling in random networks[J]. Science, 1999,286(5439): 509-512.
[3]	金弟, 刘大有, 杨博 ,等. 基于局部探测的快速复杂网络聚类算法[J]. 电子学报, 2011,39(11): 2540-2546.
	JIN D , LIU D Y , YANG B ,et al. Fast complex network clustering algorithm using local detention[J]. Acta Electronica Sinica, 2011,39(11): 2540-2546.
[4]	WANG Z , ZHANG J . In search of the biological significance of modular structures in protein networks[J]. Plos Computational Biology, 2007,3(6): 1011-1021.
[5]	FARUTIN V , ROBISON K , LIGHTCAP E ,et al. Edge-count probabilities for the identification of local protein communities and their organization[J]. Proteins Structure Function and Bioinformatics, 2006,62(3): 800-818.
[6]	QIAN C , CAO J D , LU J Q ,et al. Adaptive bridge control strategy for opinion evolution on social networks[J]. Chaos:An Interdisciplinary Journal of Nonlinear Science, 2011,21(2):025116
[7]	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.
[8]	NEWMAN M E J , GIRVAN M . Finding and evaluating community structure in networks[J]. Physical Review E, 2004,69(2):026113.
[9]	NEWMAN M E J . Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004,69(6):066133.
[10]	BLONDEL V D , GUILLAUME J L , LAMBIOTTE R ,et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics Theory and Experiment, 2008,10:10008.
[11]	RAGHAVAN U N , ALBERT R , KUMARA S . Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E, 2007,76(3):036106
[12]	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-818.
[13]	SHEN H W , CHENG X Q , GUO J F . Quantifying and identifying the overlapping community structure in networks[J]. Journal of Statistical Mechanics-Theory and Experiment, 2009,53(7):07042.
[14]	ZHANG Z W , WANG Z Y . Mining overlapping and hierarchical communities in complex networks[J]. Physica A:Statistical Mechanics and its Applications, 2015,421: 25-33.
[15]	AHN Y Y , BAGROW J P , LEHMANN S . Link communities reveal multiscale complexity in networks[J]. Nature, 2010,466(7307): 761-764.
[16]	MENG F , ZHANG F , ZHU M ,et al. Incremental density-based link clustering algorithm for community detection in dynamic networks[J]. Mathematical Problems in Engineering, 2016,2016(6): 1-11.
[17]	KIM P , KIM S . Detecting overlapping and hierarchical communities in complex network using interaction-based edge clustering[J]. Physica A:Statistical Mechanics and its Applications, 2015,417: 46-56.
[18]	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.
[19]	WANG M , YANG S , WU L . Improved community mining method based on LFM and EAGLE[J]. Computer Science and Information Systems, 2016,13(2): 515-530.
[20]	CAO X , WANG X , JIN D ,et al. The (un)supervised detection of overlapping communities as well as hubs and outliers via (bayesian) NMF[C]// International Conference on World Wide Web Companion. 2014: 233-234.
[21]	常振超, 陈鸿昶, 黄瑞阳 ,等. 基于非负矩阵分解的半监督动态社团检测[J]. 通信学报, 2016,37(2): 132-142.
	CHANG Z C , CHEN H C , HUANG R Y ,et al. Semi-supervised dynamic community detection bused on nonnegative matrix factoriza-tion[J]. Journal on Communications, 2016,37(2): 132-142.
[22]	HE D , WANG H , JIN D ,et al. A model framework for the enhancement of community detection in complex networks[J]. Physica A Statistical Mechanics ＆ Its Applications, 2016,461: 602-612.
[23]	GREGORY S . Finding overlapping communities in networks by label propagation[J]. New Journal of Physics, 2010,12(10):103018.
[24]	XIE J R , SZYMANSKI B K , LIU X . Slpa:uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[C]// IEEE ICDM Workshop on DMCCI. IEEE,Vancouver,Canada, 2011: 344-349.
[25]	CHEN Q , WU T T . A method for local community detection by finding maximal-degree nodes[C]// 9th International Conference on Machine Learning and Cybernetics. 2010: 8-13.
[26]	ZHANG T , WU B . A method for local community detection by finding core nodes[C]// International Conference on Advances in Social Networks Analysis and Mining,IEEE. Istanbul,Turkey, 2012: 1171-1176.
[27]	LEUNG I X , HUI P LIò P ,et al. Towards real-time community detection in large networks[J]. Physical Review E, 2009,79(2): 853-857.
[28]	XIE J , KELLEY S , SZYMANSKI B K . Overlapping community detection in networks:the state of the art and comparative study[J]. Acm Computing Surveys, 2011,45(4): 115-123.
[29]	LANCICHINETTI A , FORTUNATO S , RADICCHI F . Benchmark graphs for testing community detection algorithms[J]. Physical Review E, 2008,78(4):046110.
[30]	ZACHARY W W . An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977,33(4): 452-473.
[31]	LUSSEAU D . The emergent properties of a dolphin social network[J]. Proceedings of the Royal Society B:Biological Sciences, 2003,270(S2): 186-188.
[32]	KNUTH D E . The Stanford graphbase:a platform for combinatorial computing[EB/OL]. .
[33]	NEWMAN M E J . Modularity and community structure in networks[J]. Proceedings of the National Academy of Science, 2006,103(23): 8577-8582.
[34]	GUIMERA R , DANON L DIAZ-GUILERA A ,et al. Self-similar community structure in a network of human interactions[J]. Physical Review E, 2003,68(6):065103.
[35]	NEWMAN M E J . Network data from mark Newman's home page[EB/OL]. .
[36]	NEWMAN M E J . Finding community structure in networks using the eigenvectors of matrices[J]. Physical review E, 2006,74(3):036104.
[37]	BOGU?á M , PASTOR-SATORRAS R , DíAZ-GUILERA A ,et al. Models of social networks based on social distance attachment[J]. Physical Review E, 2004,70(5):056122. 056-122.

网络	O_n	O_m	μ
R1	20	2	0.1～0.4
R2	100	2	0.1～0.4
R3	20	2～6	0.1
R4	20	2～6	0.3

网络	节点	边	平均度	描述
Karate	34	78	4.59	空手道俱乐部网络^[30]
Dolphins	62	159	5.13	海豚社会网络^[31]
Lesmis	77	254	6.6	悲惨世界关系网络^[32]
Polbooks	105	441	8.4	美国政治之书网络^[33]
Email	1 133	5 451	9.62	电子邮件交往网络^[34]
Polblogs	1 490	19 022	25.53	美国大选博客网络^[35]
Netscience	1 588	2 742	3.45	作者合作网络^[36]
PGP	0 680	24 316	4.55	信任网络^[37]
Internet	22 963	48 436	4.22	互联网快照网络^[35]

网络	OMKLP	CFINDER	LFM	COPRA	SLPA	LC
Karate	0.367 9	0.107 2	0.214 6	0.323 9	0.347 2	0.122 0
Dolphins	0.519 1	0.288 5	0.237 4	0.420 6	0.387 9	0.151 4
Lesmis	0.433 8	0.185 5	0.481 2	0.477 9	0.320 9	0.248 4
Polbooks	0.484 2	0.430 4	0.347 6	0.458 6	0.456 8	0.219 8
Email	0.307 9	0.264 1	0.182 2	0.352 3	0.183 7	0.026 1
Polblogs	0.196 3	—	0.192 2	—	0.007	0.015
Netscience	0.910 9	0.590 5	0.259 9	0.718 6	0.712 6	0.719 2
PGP	0.700 8	—	—	0.433 5	0.692 8	0.160 1
Internet	0.185 3	—	0.195 8	0.034 5	0.116 1	0.023 4

基于多核心标签传播的复杂网络重叠社区识别方法

Overlapping community detection in complex networks based on multi kernel label propagation

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 37

相关文章 15

Metrics

推荐阅读 0

[1]	孙雁飞, 尹嘉峥, 亓晋, 胡筱旋, 陈梦婷, 董振江. 基于动态图嵌入的车联网拓扑控制[J]. 通信学报, 2022, 43(6): 133-142.
[2]	顾秋阳, 吴宝, 池仁勇. 基于高阶路径相似度的复杂网络链路预测方法[J]. 通信学报, 2021, 42(7): 61-69.
[3]	顾秋阳, 吴宝, 孙兆洋, 池仁勇. 基于改进灰狼优化的复杂网络重要节点识别算法[J]. 通信学报, 2021, 42(6): 72-83.
[4]	韩涛, 贺威, 代俊, 左勇, 杨旸, 葛晓虎. 基于无标度网络的车联网连通性研究[J]. 通信学报, 2021, 42(4): 100-108.
[5]	朱近康, 柴名扬, 周武旸. 面向B5G/6G的三三三网络体系架构和优化学习机制[J]. 通信学报, 2021, 42(4): 62-75.
[6]	张胜,戴维凯,吴锋,蓝文祥. 基于分形特性的复杂网络全局效率估计方法[J]. 通信学报, 2020, 41(7): 204-212.
[7]	吴翼腾,于洪涛,黄瑞阳,李华巍. 采用组合方法进行链路预测的理论极限研究[J]. 通信学报, 2020, 41(6): 34-50.
[8]	刘树新,李星,陈鸿昶,王凯. 基于资源传输匹配度的复杂网络链路预测方法[J]. 通信学报, 2020, 41(6): 70-79.
[9]	项英倬,徐正国,游凌. 基于节点通信行为时序的指控信息流挖掘算法[J]. 通信学报, 2019, 40(9): 51-60.
[10]	李凤华,陈天柱,王震,张林杰,史国振,郭云川. 复杂网络环境下跨网访问控制机制[J]. 通信学报, 2018, 39(2): 1-10.
[11]	陈晶,万云. 社交网络中基于模块度最大化的标签传播算法的研究[J]. 通信学报, 2017, 38(2): 25-33.
[12]	张洛什,王大伟,薛一波. 基于流感知的复杂网络应用识别模型[J]. 通信学报, 2015, 36(3): 161-169.
[13]	郭昆,郭文忠,邱启荣,张歧山. 基于局部近邻传播及用户特征的社区识别算法[J]. 通信学报, 2015, 36(2): 68-79.
[14]	刘君,乔建志. 复杂网络中k-核与网络聚集系数的关联性研究[J]. 通信学报, 2015, 36(1): 224-229.
[15]	牛建伟,戴彬,童超,霍冠英,彭井. 基于Laplace矩阵Jordan型的复杂网络聚类算法[J]. 通信学报, 2014, 35(3): 11-21.