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

Overlapping community detection algorithm combining K-shell and label entropy

针对标签传播算法稳定性不足、准确性较差的问题,提出了融合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.