基于LeaderRank的标签传播社区发现算法

Community detection by label propagation with LeaderRank method

针对标签传播算法(LPA)结果的不稳定性,提出一种改进的基于标签传播的社区发现算法。该算法引入LeaderRank的概念来量化网络节点的影响力和重要性;然后按照节点重要程度从高到低选择若干核心节点;最后按照顺序分别以每个核心节点为中心向外逐层进行标签更新,直到不再出现标签变化为止,从而解决了原始算法对节点随机排序造成的结果不稳定性。以LFR基准网络和真实网络为实验数据,与几个现有标签传播算法进行比较,社区划分结果的标准化互信息(NMI)和模块度(Modularity)均高于对比算法。理论分析和实验结果表明所提算法不仅有效地增强了社区发现结果的稳定性,同时提高了准确率。

Focusing on the instability of Label Propagation Algorithm （LPA）, an advanced label propagation algorithm for community detection was proposed. It introduced the concept of LeaderRank score to quantify the importance of nodes, and chose some core nodes according to the node importance in descending order, then updated labels layer by layer outward centered on every core node respectively, until no node changed its label any more. Thus the instability caused by the random ranking of nodes was solved. Compared with several existing label propagation algorithms on LFR benchmark networks and real networks, both of the Normalized Mutual Information （NMI） and modularity of community detection result of the proposed algorithm were higher. The theoretical analysis and experimental results demonstrate that the proposed algorithm not only improves the stability effectively, but also increases the accuracy.