摘要： 随着网络规模的不断增大,在时间复杂度上具有明显优势的标签传播算法受到广泛关注,但是其内在机制存在不确定性和随机性，导致社团发现结果不够准确和稳定。为此,提出一种新的改进标签传播算法。在K-shell分解算法的基础上,构造节点重要性计算方法,利用节点重要性分析标签传播算法中的标签传播能力,通过节点重要性排序和标签传播能力制定新的标签更新策略,得出最终的社团划分结果。在人工网络和真实网络上的实验结果表明,该算法有较高的准确性和稳定性。

关键词: 复杂网络, 社团发现, 标签传播, K-shell分解, 节点重要性

Abstract: With the increasing scale of the network,the Label Propagation Algorithm(LPA) has obvious advantages in the time complexity,but its internal mechanism is uncertain and random which leads to unaccurate and unsteadiness community discovery results.This paper presents an improved LPA algorithm.It constructs a new calculation method of node importance based on the K-shell decomposition algorithm,then uses the node importance analysis the label propagation ability in the label propagation algorithm,finally utilizes the node importance and label propagation ability to develop new label update strategy,and obtains the final results.Experimental results on artificial and real networks show that the algorithm has high accuracy and stability.

Key words: complex network, community discovery, label propagation, K-shell decomposition, node importance

中图分类号: 

• TP391