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

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

Abstract

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

CLC Number:

TP391

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.

Figures/Tables 15

序号	算法	时间复杂度
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²)

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

网络	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

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 15

References 37

Related Articles 11

Metrics

Recommended 0

[1]	Yang GAO, Hongli ZHANG. Survey on community detection method based on random walk [J]. Journal on Communications, 2023, 44(6): 198-210.
[2]	Yancui SHI,Yuan WANG,Qing ZHAO,Xiankun ZHANG. Research status of community detection based on local expansion [J]. Journal on Communications, 2019, 40(1): 149-162.
[3]	Qiang LIU,Yan JIA,Binxing FANG,Bin ZHOU,Yue HU,Jiuming HUANG. Research on the scalability of parallel community detection algorithms [J]. Journal on Communications, 2018, 39(4): 13-20.
[4]	Jing CHEN,Yun WAN. Research on label propagation algorithm based on modularity maximization in the social network [J]. Journal on Communications, 2017, 38(2): 25-33.
[5]	Zhen-chao CHANG,Hong-chang CHEN,Rui-yang HUANG,Hong-tao YU,Yang LIU. Semi-supervised dynamic community detection based on non-negative matrix factorization [J]. Journal on Communications, 2016, 37(2): 132-143.
[6]	Kun GUO,Wen-zhong GUO,Qi-rong QIU,Qi-shan ZHANG. Community detection algorithm based on local affinity propagation and user profile [J]. Journal on Communications, 2015, 36(2): 68-79.
[7]	. Improved shuffled frog-leaping algorithm based network community detection method [J]. Journal on Communications, 2014, 35(Z2): 8-52.
[8]	Tong WANG,Xin-lin ZHAO. Improved shuffled frog-leaping algorithm based network community detection method [J]. Journal on Communications, 2014, 35(Z2): 48-52.
[9]	. Privacy leakage in online social networks based on public information [J]. Journal on Communications, 2013, 34(Z1): 25-196.
[10]	Shao-qing LV,Yu-qing ZHANG,Ping NI. Privacy leakage in online social networks based on public information [J]. Journal on Communications, 2013, 34(Z1): 190-196.
[11]	UYe X,HAOHai Z,UWei-ji S,HANGWen-bo Z,HANGXin Z,ANGZu-wei W. Analysis on IP-based density of Internet [J]. Journal on Communications, 2005, 26(11): 125-131.