基于标签传播与多指标的重叠社区检测算法

doi:10.11772/j.issn.1001-9081.2023030393

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (S2): 105-110.DOI: 10.11772/j.issn.1001-9081.2023030393

• 数据科学与技术 • 上一篇

基于标签传播与多指标的重叠社区检测算法

王明月¹^,², 邹晓红¹^,², 陈晶³(), 许成伟¹^,²

^1.燕山大学信息科学与工程学院, 河北秦皇岛 066004
^2.河北省计算机虚拟技术与系统集成重点实验室(燕山大学), 河北秦皇岛 066004
^3.广东海洋大学数学与计算机学院, 广东湛江 524088

收稿日期:2023-04-10 修回日期:2023-06-22 接受日期:2023-07-04 发布日期:2024-01-09 出版日期:2023-12-31
通讯作者: 陈晶
作者简介:王明月（1996—），女，河北秦皇岛人，硕士，主要研究方向：社区发现
邹晓红（1967—），女，吉林吉林人，教授，博士，主要研究方向：图挖掘、社会网络
陈晶（1976—），女，河北秦皇岛人，教授，博士，CCF会员，主要研究方向：对等网络、Web服务
许成伟（1997—），男，黑龙江齐齐哈尔人，硕士，主要研究方向：社交网络。
基金资助:
国家自然科学基金资助项目(62172352);中央政府引导地方科技发展基金资助项目(ZD2019004);河北省创新能力提升计划项目(22567626H)

Overlapping community detection algorithm based on label propagation and multiple metrics

Mingyue WANG¹^,², Xiaohong ZOU¹^,², Jing CHEN³(), Chengwei XU¹^,²

^1.College of Information Science and Engineering，Yanshan University，Qinhuangdao Hebei 066004，China
^2.Key Laboratory of Computer Virtual Technology and System Integration of Hebei Province （Yanshan University），Qinhuangdao Hebei 066004，China
^3.School of Mathematics and Computer Science，Guangdong Ocean University，Zhanjiang Guangdong 524088，China

Received:2023-04-10 Revised:2023-06-22 Accepted:2023-07-04 Online:2024-01-09 Published:2023-12-31
Contact: Jing CHEN

摘要/Abstract

摘要：

为解决标签传播的社区检测算法容易产生怪物社区和不稳定社区划分的问题，以标签熵为基础，提出一种重叠社区检测算法LEKA（Label Entropy and K-shell Algorithm in overlapping community），综合考虑了标签初始化、标签更新和标签传播的各个阶段。首先，利用K-shell算法对节点进行初始化以获取节点的层次信息；其次，依据标签熵升序依次更新节点标签，在选择标签时综合节点间的层次信息和节点间的影响，在存在多个候选标签的情况下基于节点标签权重进行选取。在真实网络数据集上的实验结果表明，LEKA在运行时间较短的情况下，重叠模块度EQ（ExtendQ）相较于OCKELP（Overlapping Community detection algorithm based on K-shell and label Entropy in Label Propagation）提高了2.3%~13.2%，具有较高的准确性和稳定性，更适合挖掘网络中的重叠社区结构。

关键词: 重叠社区检测, 标签熵, 节点影响力, 标签权重, 标签传播

Abstract:

In order to solve the problem that the community detection algorithm of label propagation is easy to produce monster communities and instable community division， an overlapping community discovery algorithm LEKA （Label Entropy and K-shell Algorithm in overlapping community） based on label entropy was proposed， in which all stages of label initialization， label update and label propagation were considered. Firstly， K-shell algorithm was used to initialize nodes and obtain the hierarchical information of nodes. Secondly， node labels were updated according to the ascending order of label entropy. When selecting labels， the hierarchical information and influence between nodes were integrated. When there were multiple candidate labels， the labels were selected based on the weights of node labels. Experimental results on real network datasets show that LEKA performs well in situations where the runtime is short， compared to OCKELP （Overlapping Community detection algorithm based on K-shell and label Entropy in Label Propagation）， the overlapping module degree EQ （ExtendQ） is improved by 2.3% to 13.2%. LEKA has higher accuracy and stability and is more suitable for mining overlapping community structures in networks.

Key words: overlapping community detection, label entropy, node influence, label weight, label propagation

中图分类号:

TP399

王明月, 邹晓红, 陈晶, 许成伟. 基于标签传播与多指标的重叠社区检测算法[J]. 计算机应用, 2023, 43(S2): 105-110.

Mingyue WANG, Xiaohong ZOU, Jing CHEN, Chengwei XU. Overlapping community detection algorithm based on label propagation and multiple metrics[J]. Journal of Computer Applications, 2023, 43(S2): 105-110.

图/表 5

参考文献 30

1	第 52次《中国互联网络发展状况统计报告》发布：我国网民规模达 10.79亿人［EB/OL］. ［2023-06-21］..
2	骆志刚，丁凡，将晓舟，等.复杂网络社团发现算法研究新进展［J］.国防科技大学学报，2011，33（1）：47-52. 10.3969/j.issn.1001-2486.2011.01.011
3	刘大有，金弟，何东晓，等.复杂网络社区挖掘综述［J］.计算机研究与发展，2013，50（10）：2140-2154.
4	SAIF S M， SAMIE M E， HAMZEH A. A subgraphs-density based overlapping community detection algorithm for large-scale complex networks［J］. Computing， 2023， 105（1）： 151-185. 10.1007/s00607-022-01121-1
5	SATHYAKALA M， SANGEETHA M. Retraction Note to： a weak clique based multi objective genetic algorithm for overlapping community detection in complex networks［J］. Journal of Ambient Intelligence and Humanized Computing， 2023， 14 （Supp1）： S259. 10.1007/s12652-022-04054-x
6	LIN L， YUAN P， LI R H， et al. Query-centered temporal community search via time-constrained personalized PageRank ［EB/OL］. ［2023-01-22］. . 10.14778/3583140.3583150
7	LIU H， LI G. Overlapping community detection method based on network representation learning and density peaks［J］. IEEE Access， 2020， 8： 226506-226514. 10.1109/access.2020.3041472
8	LI C， CHEN H， LI T. An overlapping community detection algorithm based on density peaks and label propagation［C］// Proceedings of the 16th International Conference on Intelligent Systems and Knowledge Engineering. Piscataway： IEEE， 2021： 561-564. 10.1109/iske54062.2021.9755358
9	JAGUZOVIĆ M， GRBIĆ M， ÐUKANOVIĆ M， et al. Identification of protein complexes by overlapping community detection algorithms： A comparative study ［C］// Proceedings of the 21st International Symposium INFOTEH-JAHORINA. Piscataway： IEEE， 2022： 1-6. 10.1109/infoteh53737.2022.9751314
10	JIA J， DU X， LIU P. Local optimization overlapping community discovery algorithm combining attribute features［C］// Proceedings of the 6th International Conference on Intelligent Computing and Signal Processing. Piscataway： IEEE， 2021： 350-355. 10.1109/icsp51882.2021.9409003
11	GREGORY S. Finding overlapping communities in networks by label propagation［J］. New Journal of Physics， 2009， 12（10）：2011-2024. 10.1088/1367-2630/12/10/103018
12	GOLDENBERG J， LIBAI B， MULLER E. Talk of the network： A complex systems look at the underlying process of word-of-mouth［J］. Marketing Letters， 2001， 12： 211-223. 10.1023/a:1011122126881
13	陈旭. 动态社交网络的重叠社区检测与社区演化分析方法研究［D］.大连：大连海事大学，2020：1-68.
14	WANG H， QIU S， MI H， et al. A node label overlapping community division algorithm based on entropy conversion［C］// Proceedings of the 7th International Conference on Intelligent Computing and Signal Processing. Piscataway： IEEE， 2022： 326-329. 10.1109/icsp54964.2022.9778359
15	TANG Z， LI C， TANG Y. An efficient method based on label propagation for overlapping community detection［C］// Proceedings of the IEEE 24th International Conference on Computer Supported Cooperative Work in Design. Piscataway： IEEE， 2021： 168-173. 10.1109/cscwd49262.2021.9437855
16	YANG S， CAO J. A multi-label propagation algorithm with the double-layer filtering strategy for overlapping community detection［J］. IEEE Access， 2022， 10： 33037-33047. 10.1109/access.2022.3161553
17	BAI H， SHI L， LIU L， et al. An overlap community propagation algorithm based on topics and community structure in social networks［C］// Proceedings of the 20th International Conference on Ubiquitous Computing and Communications. Piscataway： IEEE， 2021： 331-338. 10.1109/iucc-cit-dsci-smartcns55181.2021.00061
18	姜浩. 复杂网络中重叠社区发现算法的研究与应用［D］.昆明：云南财经大学，2019：1-56.
19	韩瑞. 基于标签传播的动态重叠社区发现算法［D］.哈尔滨：哈尔滨工程大学，2020：1-73.
20	吴清寿，陈荣旺，余文森，等.融合标签预处理与节点影响力的重叠社区发现算法［J］.计算机应用，2020，40（12）：3578-3585. 10.15888/j.cnki.csa.007712
21	JAYAPRAKASH R. CLCLP： Overlapping community detection in networks using a combination of link community and label propagation algorithm［J］// IOP Conference Series： Materials Science and Engineering， 2022， 1258（1）： No.012048. 10.1088/1757-899x/1258/1/012048
22	YU H， MA R， CHAO J， et al. An overlapping community detection approach based on DeepWalk and improved label propagation［J］. IEEE Transactions on Computational Social Systems， 2022， 10（1）： 311-321. 10.1109/tcss.2022.3152579
23	ZHAO Y， LI S， CHEN X. Community detection using label propagation in entropic order［C］// Proceedings of the IEEE 12th International Conference on Computer and Information Technology. Piscataway： IEEE， 2012： 18-24. 10.1109/cit.2012.30
24	陈旭，张俊，等.基于标签传播的重叠社区检测算法［J］.计算机应用与软件，2022，39（4）：326-331. 10.3969/j.issn.1000-386x.2022.04.050
25	DANON L， DIAZ-GUILERA A， DUCH J， et al. Comparing community structure identification［J］. Journal of Statistical Mechanics： Theory and Experiment， 2005， 2005（9）：No.09008. 10.1088/1742-5468/2005/09/p09008
26	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. 10.1016/j.physa.2008.12.021
27	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）： No.033015. 10.1088/1367-2630/11/3/033015
28	LANCICHINETTI A， FORTUNATO S， RADICCHI F. Benchmark graphs for testing community detection algorithms［J］. Physical Review E， 2008， 78（4）： No.046110. 10.1103/physreve.78.046110
29	陈晶，刘江川，魏娜娜.融合K-shell和标签熵的重叠社区检测算法［J］.计算机应用，2022，42（4）：1162-1169.
30	LU M， ZHANG Z， QU Z， et al. LPANNI： Overlapping community detection using label propagation in large-scale complex networks［J］. IEEE Transactions on Knowledge and Data Engineering， 2018， 31（9）： 1736-1749. 10.1109/tkde.2018.2866424

数据集	节点数	边数	描述
Football	115	613	足球比赛网络
Facebook	4 039	88 234	Facebook社交圈
Internet	22 963	48 436	互联网快照网络

数据集	节点数	边数	描述
Football	115	613	足球比赛网络
Facebook	4 039	88 234	Facebook社交圈
Internet	22 963	48 436	互联网快照网络

算法	Football	Facebook	Internet
LEKA	0.602 8	0.802 9	0.412 2
OCKELP	0.567 2	0.709 5	0.403 0
LPANNI	0.597 8	0.816 5	0.402 0
COPRA	0.536 4	0.750 2	0.331 1
SLPA	0.549 4	0.772 5	0.329 0

算法	Football	Facebook	Internet
LEKA	0.602 8	0.802 9	0.412 2
OCKELP	0.567 2	0.709 5	0.403 0
LPANNI	0.597 8	0.816 5	0.402 0
COPRA	0.536 4	0.750 2	0.331 1
SLPA	0.549 4	0.772 5	0.329 0

[1]	陈晶, 刘江川, 魏娜娜. 融合K-shell和标签熵的重叠社区发现算法[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1162-1169.
[2]	吕亚丽, 苗钧重, 胡玮昕. 基于标签进行度量学习的图半监督学习算法[J]. 计算机应用, 2020, 40(12): 3430-3436.
[3]	郑文萍, 岳香豆, 杨贵. 基于随机游走的改进标签传播算法[J]. 计算机应用, 2020, 40(12): 3423-3429.
[4]	吴清寿, 陈荣旺, 余文森, 刘耿耿. 融合标签预处理与节点影响力的重叠社区发现算法[J]. 计算机应用, 2020, 40(12): 3578-3585.
[5]	雷曼, 龚琴, 王纪超, 王保群. 基于标签权重的协同过滤推荐算法[J]. 计算机应用, 2019, 39(3): 634-638.
[6]	顾军华, 霍士杰, 王守彬, 田喆. 基于节点中心性和社区相似性的快速标签传播算法[J]. 计算机应用, 2018, 38(5): 1320-1326.
[7]	汪焱, 黄发良, 元昌安. 基于标签影响力的半同步社区发现算法[J]. 计算机应用, 2016, 36(6): 1573-1578.
[8]	黄泳航, 汤庸, 李春英, 汤志康, 刘继伟. 基于社区划分的学术论文推荐模型[J]. 计算机应用, 2016, 36(5): 1279-1283.
[9]	李春英, 汤庸, 汤志康, 黄泳航, 袁成哲, 赵剑冬. 面向大规模学术社交网络的社区发现模型[J]. 计算机应用, 2015, 35(9): 2565-2568.
[10]	石梦雨, 周勇, 邢艳. 基于LeaderRank的标签传播社区发现算法[J]. 计算机应用, 2015, 35(2): 448-451.
[11]	石立新张俊星. 基于势函数的标签传播社区发现算法[J]. 计算机应用, 2014, 34(3): 738-741.
[12]	常晓龙张晖. 融合语素特征的中文褒贬词典构建[J]. 计算机应用, 2012, 32(07): 2033-2037.

基于标签传播与多指标的重叠社区检测算法

Overlapping community detection algorithm based on label propagation and multiple metrics

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 30

相关文章 12

编辑推荐

Metrics

网络	n	k	maxk	mu	minc	maxc	on	om
R1	1 000	10	50	0.1	10	50	100	［2，8］
R2	1 000	10	50	0.3	10	50	100	［2，8］
R3	5 000	10	50	0.1	20	100	500	［2，8］
R4	5 000	10	50	0.3	20	100	500	［2，8］
R5	10 000	20	100	0.1	20	100	2 000	［2，8］
R6	10 000	20	100	0.3	20	100	2 000	［2，8］