基于节点影响力的理性节点标签传播算法

计算机工程与科学 ›› 2022, Vol. 44 ›› Issue (04): 713-722.

基于节点影响力的理性节点标签传播算法

皇甫斐斐1，杨阳2，邓晓懿2,3

(1.华侨大学外国语学院,福建泉州 362021；2.华侨大学现代应用统计与大数据研究中心,福建厦门 361021；
3.新泽西州立罗格斯大学罗格斯商学院,新泽西纽瓦克 07102)

收稿日期:2020-08-26 修回日期:2021-01-25 接受日期:2022-04-25 出版日期:2022-04-25 发布日期:2022-04-20
基金资助:
国家自然科学基金(71401058)；福建省自然科学基金(2020J01077);福建省社会科学规划项目(FJ2020B047)

A rational label propagation algorithm based on node influence

HUANGFU Fei-fei1,YANG Yang2,DENG Xiao-yi2,3

(1.College of Foreign Languages,Huaqiao University,Quanzhou 362021,China;
2.Research Center for Modern Applied Statistics & Big Data,Huaqiao University,Xiamen 361021,China;
3.Rutgers Business School,Rutgers,the State University of New Jersey,Newark,New Jersey 07102,USA)

Received:2020-08-26 Revised:2021-01-25 Accepted:2022-04-25 Online:2022-04-25 Published:2022-04-20

摘要/Abstract

摘要： 社区发现能够揭示真实社会网络的拓扑结构和重要节点。由于具有线性时间复杂度，无需定义目标函数及目标参数，标签传播算法(LPA)作为经典社区发现算法被广泛应用在学术和实践领域。针对LPA算法更新顺序的无序性和标签选择的随机性,提出基于节点影响力的理性节点标签传播算法(RLPBNI)。将节点影响力排序作为更新顺序，引入理性节点概念进行标签选择，并定义重叠度进行社区再降维。实验结果表明，与其他对比算法相比,RLPBNI算法不但可有效提高社区划分精度，且更容易发现混合程度较高的网络中隐藏的社区。

关键词: 社区发现；标签传播, 节点影响力；理性节点；复杂网络

Abstract: Community discovery can reveal the topology and important nodes of real social networks. Due to its linear time complexity and no need to define objective functions and objective parameters, Label Propagation Algorithm (LPA) is widely used in academic and practical fields as a classic community discovery algorithm. Aiming at the update disorder of LPA algorithm and the randomness of label selection, a Rational Node Label Propagation Algorithm Based on Node Influence (RLPBNI) is proposed. The algorithm takes the node influence ranking as the update order, introduces the concept of rational nodes for label selection, and defines the overlap degree for community dimensionality reduction. The analysis of the experimental results shows that, compared with other comparative algorithms, the RLPBNI algorithm can not only effectively improve the accuracy of community division, but also more easily discover hidden communities in networks with a high degree of mixing.

Key words: community detection, label propagation, node influence, rational node, complex network

皇甫斐斐, 杨阳, 邓晓懿, . 基于节点影响力的理性节点标签传播算法[J]. 计算机工程与科学, 2022, 44(04): 713-722.

HUANGFU Fei-fei, YANG Yang, DENG Xiao-yi, . A rational label propagation algorithm based on node influence[J]. Computer Engineering & Science, 2022, 44(04): 713-722.