一种新的基于标签传播的复杂网络重叠社区识别算法
CSTR:
作者:
作者单位:

(1. 嘉兴学院数理与信息工程学院,浙江嘉兴314001;2. 蒂赛德大学计算、媒体与艺术学院,米德尔斯伯勒TS1 3BX)

作者简介:

通讯作者:

E-mail: dengkun@hrbeu.edu.cn.

中图分类号:

TP391

基金项目:

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


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

(1. College of Mathematics Physics and Information Engineering,Jiaxing University,Jiaxing 314001,China;2. School of Computing,Media and the Arts,Teesside University,Middlesbrough TS1 3BX,UK)

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    针对现有基于标签传播的复杂网络重叠社区识别方法所存在的社区识别精度不稳定,以及随机性较强等缺陷,提出一种新的基于标签传播的复杂网络重叠社区识别算法NOCDLP(a novel algorithm for overlapping community detection based on label propagation).该算法首先搜索网络中若干以度较高节点为中心的完全子图,并以这些完全子图为起点进行标签传播;其次通过分析节点与社区连接强度以及社区接纳某节点后的社区内部连接紧密度情况给出节点归属社区强度函数,以此作为标签传播的依据提高社区的识别精度;再次,在标签传播过程中,NOCDLP算法设置标签传播控制标记,以避免标签传播算法随机性较强的缺陷;最后,在已形成的社区中通过整理重叠节点获得更准确的重叠社区结构.算法在人工网络与真实网络中完成测试,同时与多个经典算法进行对比分析,实验结果验证了NOCDLP算法是有效的、可行的.

    Abstract:

    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.

    参考文献
    相似文献
    引证文献
引用本文

邓琨,李文平,陈丽,等.一种新的基于标签传播的复杂网络重叠社区识别算法[J].控制与决策,2020,35(11):2733-2742

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2020-10-15
  • 出版日期:
文章二维码