计算机应用 ›› 2015, Vol. 35 ›› Issue (2): 448-451.DOI: 10.11772/j.issn.1001-9081.2015.02.0448

• 人工智能 • 上一篇    下一篇

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

石梦雨, 周勇, 邢艳   

  1. 中国矿业大学 计算机科学与技术学院, 江苏 徐州 221008
  • 收稿日期:2014-09-01 修回日期:2014-11-06 出版日期:2015-02-10 发布日期:2015-02-12
  • 通讯作者: 石梦雨
  • 作者简介:石梦雨(1991-),女,安徽宿州人,硕士研究生,主要研究方向:社区发现、数据挖掘; 周勇(1974-),男,江苏徐州人,副教授,博士,CCF会员,主要研究方向:数据挖掘、智能信息处理; 邢艳(1987-),女,河北沧州人,博士研究生,CCF会员,主要研究方向:数据挖掘。
  • 基金资助:

    国家863计划项目(2012AA0622022,2012AA011004);国家自然科学基金资助项目(50674086);教育部高等学校博士学科点专项科研基金项目(20110095110010);江苏省研究生科研创新计划项目(CXZZ12_0934)。

Community detection by label propagation with LeaderRank method

SHI Mengyu, ZHOU Yong, XING Yan   

  1. School of Computer Science and Technology, China University of Mining and Technology, Xuzhou Jiangsu 221008, China
  • Received:2014-09-01 Revised:2014-11-06 Online:2015-02-10 Published:2015-02-12

摘要:

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

关键词: 标签传播算法, 不稳定性, 社区发现, LeaderRank, 节点重要性

Abstract:

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.

Key words: Label Propagation Algorithm (LPA), instability, community detection, LeaderRank, importance of nodes

中图分类号: