Journal of Computer Applications ›› 2016, Vol. 36 ›› Issue (6): 1573-1578.DOI: 10.11772/j.issn.1001-9081.2016.06.1573

Previous Articles     Next Articles

Semi-synchronous communities detection algorithm based on label influence

WANG Yan1, HUANG Faliang1, YUAN Chang'an2   

  1. 1. Faculty of Software, Fujian Normal University, Fuzhou Fujian 350108, China;
    2. Key Laboratory of Scientific Computing and Intelligent Information Processing in Universities of Guangxi, Nanning Guangxi 530023, China
  • Received:2015-11-04 Revised:2015-12-21 Online:2016-06-10 Published:2016-06-08
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61363037), the Youth Foundation of Humanities and Social Sciences of Ministry of Education (12YJCZH074), the Category A Project of Fujian Provincial Department of Education (JA13077).


汪焱1, 黄发良1, 元昌安2   

  1. 1. 福建师范大学 软件学院, 福州 350108;
    2. 科学计算与智能信息处理广西高校重点实验室, 南宁 530023
  • 通讯作者: 黄发良
  • 作者简介:汪焱(1988-),男,湖北随州人,硕士,主要研究方向:数据挖掘、社区发现;黄发良(1975-),男,湖南永州人,副教授,博士,CCF会员,主要研究方向:数据挖掘、社交媒体处理;元昌安(1964-),男,安徽肥东人,教授,博士,CCF会员,主要研究方向:数据挖掘。
  • 基金资助:

Abstract: It is a great challenge to discover communities in the fast growing large-scale interactive social information networks such as Weibo and social networks. Although Label Propagation Algorithm (LPA) has great advantage in time complexity, but its inherent multiple random strategies make the algorithm unstable. In order to solve the problem, a semi-synchronous label propagation algorithm named Influence-driven Semi-synchronous Label Propagation Algorithm (ISLPA) was proposed. The propagation oscillation was avoided effectively and the synchronous update between neighbor nodes was realized by abandoning the original random strategy and integrating node influence into label initialization, neighbor node selection and updated order determination. The experimental results from the real-world and artificial networks indicate that, in terms of validity and stability of generated communities from the networks, the proposed ISLPA outperforms the currently typical LPAs used in community detection.

Key words: community detection, Label Propagation Algorithm (LPA), semi-synchronization, node influence, oscillation

摘要: 微博网络与社交网络等的交互式社会信息网络规模的快速增长对社区发现提出巨大挑战。标签传播算法(LPA)虽然在时间复杂度上具有很大的优势,但是其内在的多种随机策略使得算法稳定性不高。针对LPA的随机问题,提出了一种基于影响力的半同步标签传播算法(ISLPA),能有效地避免振荡问题,巧妙地实现了相邻节点之间的同步更新,并结合影响力从初始标签、选择邻居节点和更新顺序三方面进行了改进,摒弃了原有的随机策略。真实网络和人工网络的实验结果表明,ISLPA具有较高的稳定性与有效性,与其他LPA相关算法相比存在明显的优势。

关键词: 社区发现, 标签传播法, 半同步, 节点影响力, 振荡

CLC Number: