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

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

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

CLC Number: 

• TP301.6