一种新的基于标签传播的复杂网络重叠社区识别算法  

A novel algorithm for overlapping community detection based on label propagation in complex networks

作　　者：邓琨[1,2] 李文平 陈丽[1] 刘星妍[1] DENG Kun;LI Wen-ping;CHEN Li;LIU Xing-yan(College of Mathematics Physics and Information Engineering,Jiaxing University,Jiaxing 314001,China;School of Computing,Media and the Arts,Teesside University,Middlesbrough TS13BX,UK)

机构地区：[1]嘉兴学院数理与信息工程学院,浙江嘉兴314001 [2]蒂赛德大学计算、媒体与艺术学院,米德尔斯伯勒TS13BX

出　　处：《控制与决策》2020年第11期2733-2742,共10页Control and Decision

基　　金：教育部人文社会科学研究青年基金项目(17YJCZH033,15YJCZH088);国家自然科学基金项目(61672179,61370083);浙江省自然科学基金项目(LY15F020040);浙江省教育厅科研基金项目(Y201636127);浙江省教育科学规划课题项目(2020SCG046)。

摘　　要：针对现有基于标签传播的复杂网络重叠社区识别方法所存在的社区识别精度不稳定,以及随机性较强等缺陷,提出一种新的基于标签传播的复杂网络重叠社区识别算法NOCDLP(a novel algorithm for overlapping community detection based on label propagation).该算法首先搜索网络中若干以度较高节点为中心的完全子图,并以这些完全子图为起点进行标签传播;其次通过分析节点与社区连接强度以及社区接纳某节点后的社区内部连接紧密度情况给出节点归属社区强度函数,以此作为标签传播的依据提高社区的识别精度;再次,在标签传播过程中,NOCDLP算法设置标签传播控制标记,以避免标签传播算法随机性较强的缺陷;最后,在已形成的社区中通过整理重叠节点获得更准确的重叠社区结构.算法在人工网络与真实网络中完成测试,同时与多个经典算法进行对比分析,实验结果验证了NOCDLP算法是有效的、可行的.Existing label propagation based overlapping community detection algorithms are limited,in terms of lacking accuracy,exhibiting high randomness,etc.,when applied to complex networks.To overcome these limitations,this paper proposes a novel algorithm for overlapping community detection based on label propagation(NOCDLP).In the algorithm,we first search for a number of complete subgraphs centered on nodes with higher degrees in a network and initiate the label propagation starting from these subgraphs.Then,a function to specify the bonds between nodes and communities is generated,by analyzing the strength of connections between nodes and communities,and the internal closeness of a particular community after a certain node is adopted.By introducing this function,the accuracy of community detection is increased significantly.Subsequently,in the process of label propagation,NOCDLP sets control marks to alleviate the high randomness in community detection.Finally,the algorithm cleans up overlapping nodes to improve the accuracy of the overlapping community structures generated.This algorithm is tested in both artificial and real-world networks.The experimental results show that the proposed algorithm is practical and more efficient in comparison with multiple classical algorithms.

关 键 词：复杂网络 社区结构 社区识别 标签传播 重叠节点 

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