融合K-shell和标签熵的重叠社区发现算法  

Overlapping community detection algorithm combining K-shell and label entropy

作　　者：陈晶[1,2,3] 刘江川 魏娜娜 CHEN Jing;LIU Jiangchuan;WEI Nana(School of Information Science and Engineering,Yanshan University,Qinhuangdao Hebei 066004,China;Key Laboratory of Computer Virtual Technology and System Integration of Hebei Province(Yanshan University),Qinhuangdao Hebei 066004,China;Hebei Key Laboratory of Software Engineering(Yanshan University),Qinhuangdao Hebei 066004,China)

机构地区：[1]燕山大学信息科学与工程学院,河北秦皇岛066004 [2]河北省计算机虚拟技术与系统集成重点实验室(燕山大学),河北秦皇岛066004 [3]河北省软件工程重点实验室(燕山大学),河北秦皇岛066004

出　　处：《计算机应用》2022年第4期1162-1169,共8页journal of Computer Applications

基　　金：国家自然科学基金资助项目(62172352);河北省自然科学基金资助项目(F2019203157);河北省高等学校科学技术研究项目(ZD2019004)。

摘　　要：针对标签传播算法稳定性不足、准确性较差的问题,提出了融合K-shell和标签熵的标签传播重叠社区发现算法OCKELP。首先,采用K-shell算法减少了标签初始化时间,并利用标签熵的更新序列提高了算法的稳定性;其次,引入综合影响力进行标签选择,并将社区层次信息和节点局部信息融合提高了算法的准确性。在真实网络数据集上,OCKELP相较于重叠社区发现算法(COPRA)、基于多核心标签传播的重叠社区识别方法(OMKLP)、SLPA的模块度最大提升分别约68.64%、53.99%、42.29%,在人工网络数据集的归一化互信息(NMI)值上,OCKELP相较于其他三种算法也有着明显优势,且随着重叠节点隶属社区数量的增加可以挖掘出社区的真实结构。In order to solve the problems of insufficient stability and poor accuracy of label propagation algorithms,a label propagation overlapping community detection algorithm OCKELP(Overlapping Community detection algorithm combining K-shell and label Entropy in Label Propagation)was proposed,which combined K-shell and label entropy.Firstly,the K-shell algorithm was used to reduce the label initialization time,and the update sequence of label entropy was used to improve the stability of the algorithm.Secondly,the comprehensive influence was introduced for label selection,and the community level information and node local information were fused to improve the accuracy of the algorithm.Compared with Community Overlap PRopagation Algorithm(COPRA),Overlapping community detection in complex networks based on Multi Kernel Label Propagation(OMKLP)and Speaker-listener Label Propagation Algorithm(SLPA),OCKELP algorithm has the greatest modularity improvement of about 68.64%,53.99%and 42.29%respectively on the real network datasets.It also has obvious advantages over the other three algorithms in the Normalized Mutual Information(NMI)value of the artificial network datasets,and with the increase of the number of communities to which overlapping nodes belong,the real structures of the communities can also be excavated.

关 键 词：标签传播 标签熵 重叠社区 综合影响力 社区层次 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]