《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (4): 1162-1169.DOI: 10.11772/j.issn.1001-9081.2021071183

• CCF第36届中国计算机应用大会 (CCF NCCA 2021) • 上一篇    

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

陈晶1,2,3, 刘江川1, 魏娜娜1()   

  1. 1.燕山大学 信息科学与工程学院,河北 秦皇岛 066004
    2.河北省计算机虚拟技术与系统集成重点实验室(燕山大学),河北 秦皇岛 066004
    3.河北省软件工程重点实验室(燕山大学),河北 秦皇岛 066004
  • 收稿日期:2021-07-08 修回日期:2021-09-02 接受日期:2021-09-03 发布日期:2021-09-13 出版日期:2022-04-10
  • 通讯作者: 魏娜娜
  • 作者简介:陈晶(1976—),女,河北秦皇岛人,副教授,博士,CCF会员,主要研究方向:对等网络、Web服务、社交网络分析
    刘江川(1996—),男,河北石家庄人,硕士研究生,主要研究方向:社区发现
  • 基金资助:
    国家自然科学基金资助项目(62172352);河北省自然科学基金资助项目(F2019203157);河北省高等学校科学技术研究项目(ZD2019004)

Overlapping community detection algorithm combining K-shell and label entropy

Jing CHEN1,2,3, Jiangchuan LIU1, Nana WEI1()   

  1. 1.School 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.Hebei Key Laboratory of Software Engineering (Yanshan University),Qinhuangdao Hebei 066004,China
  • Received:2021-07-08 Revised:2021-09-02 Accepted:2021-09-03 Online:2021-09-13 Published:2022-04-10
  • Contact: Nana WEI
  • About author:CHEN Jing, born in 1976, Ph. D., associate professor. Her research interests include peer-to-peer networks, Web service, social network analysis.
    LIU Jiangchuan, born in 1996, M. S. candidate. His research interests include community detection.
  • Supported by:
    National Natural Science Foundation of China(62172352);Natural Science Foundation of Hebei Province(F2019203157);Science and Technology Research Project of Hebei Province Higher Education(ZD2019004)

摘要:

针对标签传播算法稳定性不足、准确性较差的问题,提出了融合K-shell和标签熵的标签传播重叠社区发现算法OCKELP。首先,采用K-shell算法减少了标签初始化时间,并利用标签熵的更新序列提高了算法的稳定性;其次,引入综合影响力进行标签选择,并将社区层次信息和节点局部信息融合提高了算法的准确性。在真实网络数据集上,OCKELP相较于重叠社区发现算法(COPRA)、基于多核心标签传播的重叠社区识别方法(OMKLP)、SLPA的模块度最大提升分别约68.64%、53.99%、42.29%,在人工网络数据集的归一化互信息(NMI)值上,OCKELP相较于其他三种算法也有着明显优势,且随着重叠节点隶属社区数量的增加可以挖掘出社区的真实结构。

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

Abstract:

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.

Key words: label propagation, label entropy, overlapping community, comprehensive influence, community level

中图分类号: