作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2022, Vol. 48 ›› Issue (5): 104-111. doi: 10.19678/j.issn.1000-3428.0061474

• 人工智能与模式识别 • 上一篇    下一篇

基于节点引力与鱼记忆的社区检测算法

孙福禄, 王宇嘉, 刘子怡   

  1. 上海工程技术大学 电子电气工程学院, 上海 201620
  • 收稿日期:2021-04-26 修回日期:2021-06-04 发布日期:2021-06-17
  • 作者简介:孙福禄(1996—),男,硕士研究生,主研方向为社区检测、进化计算;王宇嘉,副教授、博士;刘子怡,硕士研究生。
  • 基金资助:
    国家自然科学基金(61403249)。

Community Detection Algorithm Based on Node Gravity and Fish Memory

SUN Fulu, WANG Yujia, LIU Ziyi   

  1. School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China
  • Received:2021-04-26 Revised:2021-06-04 Published:2021-06-17

摘要: 标签传播算法是高效且具代表性的社团检测算法,其中不包含必需调节适应的相关参数,是大型网络社团检测的首选算法。标签传播算法具有较低的时间复杂度,但其随机性较强,且在标签传播过程中存在不确定性因素,影响了社区检测的准确性和稳定性。针对上述问题,提出一种基于节点引力和鱼记忆标签存储策略的社区检测算法CDA-GM。通过融入节点信息熵的k-shell排序策略增强社区检测的准确性,利用节点间的引力更新标签,减小标签传播的随机性。在此基础上,引入鱼记忆节点标签存储策略,避免出现标签震荡,增强标签传播的稳定性。选择人工网络和真实世界网络数据集进行实验,结果表明,该算法能够显著提高社区检测质量,获得准确的社区结构,与COPRA、SLPA、DLPA和COPRAPC算法相比,其标准化互信息值平均提高0.01、0.18、0.12、0.02,社区模块度平均提高0.04、0.02、0.07、0.01。

关键词: 社区检测, 标签传播, 节点引力, 鱼记忆, 节点信息熵

Abstract: The label propagation algorithm is an efficient and representative community detection algorithm.The algorithm lacks relevant parameters that must be adjusted. It is the preferred algorithm for community detection in large networks.The tag propagation algorithm has low time complexity, but it suffers from uncertainty and randomness in the tag propagation process, which affects the accuracy and stability of community detection.A community detection algorithm, CDA-GM, based on node gravity and node label storage strategy of fish memory, is proposed to alleviate this problem.The accuracy of community detection is enhanced by the k-shell sorting strategy incorporating node information entropy, while the gravitational force between nodes is used to update labels to improve the randomness of label propagation.The node-label storage strategy of fish memory is introduced to avoid label oscillations and enhance the stability of label propagation.Artificial network dataset and real-world network dataset are selected, and the proposed algorithm is compared with four other label propagation algorithms.Experimental result shows that the algorithm significantly improves the community detection quality and obtain an accurate community structure.Compared with COPRA, SLPA, DLPA, and COPRAPC, its Normalized Mutual Information(NMI) is improved by 0.01, 0.18, 0.12, 0.02, on average, and its community modularity is improved by 0.04, 0.02, 0.07, 0.01, on average.

Key words: community detection, label propagation, node gravity, fish memory, node information entropy

中图分类号: