基于节点重要性与相似性的标签传播算法

Label Propagation Algorithm Based on Node Importance and Similarity

标签传播算法是一种常用的社区发现方法,具有近似线性的时间复杂度,但该算法存在随机性和不稳定性.为了解决标签传播算法存在的准确性低和稳定性差的问题,本文提出了基于节点重要性与相似性的标签传播算法(Label Propagation Algorithm based on node Importance and Similarity, LPA_IS).首先,基于节点重要性提出种子节点集和算法更新序列的获取方法.其次,利用节点重要性与相似性提出了一种计算标签综合影响力的方法,任意节点根据其邻居标签的综合影响力更新自身的标签.在真实网络和人工合成网络上进行实验,结果表明,与其它5种典型标签传播类算法对比, LPA_IS算法能够在一定程度上提高算法的准确性和稳定性,并且能够减少算法的迭代次数.

The label propagation algorithm, a commonly used community discovery method, has approximately linear time complexity but randomness and instability. To solve the problems of low accuracy and poor stability of the label propagation algorithm, this study proposes an improved Label Propagation Algorithm based on node Importance and Similarity(LPA_IS). First, based on node importance, a method is proposed to obtain the seed node set and the algorithm update sequence. Second, a method is proposed with node importance and similarity to calculate the comprehensive influence of labels. Any node updates its own label according to the comprehensive influence of its neighbor labels.Experiments on real networks and synthetic networks have shown that compared with five typical label propagation algorithms, LPA_IS can improve the accuracy and stability to a certain extent and reduce the iterations.