Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (5): 1320-1326.DOI: 10.11772/j.issn.1001-9081.2017102927

Previous Articles     Next Articles

Fast label propagation algorithm based on node centrality and community similarity

GU Junhua1,2, HUO Shijie1,2, WANG Shoubin1,2, TIAN Zhe1,2   

  1. 1. School of Computer Science and Software, Hebei University of Technology, Tianjin 300401, China;
    2. Big Data Laboratory in Hebei Province(Hebei University of Technology), Tianjin 300401, China
  • Received:2017-12-14 Revised:2017-12-14 Online:2018-05-10 Published:2018-05-24
  • Contact: 顾军华
  • Supported by:
    This work is partially supported by the Science and Technology Project of Tianjin City (16ZXHLSF0023), the Science and Technology Project of Hebei Province (17210305D).

基于节点中心性和社区相似性的快速标签传播算法

顾军华1,2, 霍士杰1,2, 王守彬1,2, 田喆1,2   

  1. 1. 河北工业大学 计算机科学与软件学院, 天津 300401;
    2. 河北省大数据实验室(河北工业大学), 天津 300401
  • 通讯作者: 顾军华
  • 作者简介:顾军华(1966-),男,河北赵县人,教授,博士,CCF会员,主要研究方向:智能信息处理、数据挖掘;霍士杰(1993-),男,河北石家庄人,硕士研究生,CCF会员,主要研究方向:数据挖掘、计算机仿真;王守彬(1994-),男,河南商丘人,硕士研究生,主要研究方向:数据挖掘、计算机仿真;田喆(1994-),男,天津人,硕士研究生,主要研究方向:数据挖掘。
  • 基金资助:
    天津市科技计划项目(16ZXHLSF0023);河北省科技计划项目(17210305D)。

Abstract: In order to reduce unnecessary update and solve the problem of low accuracy and poor stability of Label Propagation Algorithm (LPA), a Fast Label Propagation Algorithm based on Node Centrality and Community Similarity (FNCS_LPA) was proposed. According to the node centrality measure, the nodes of a network were sorted from low to high and added into node information list, which guided the update process to avoid unnecessary update and improve the stability of community detection. The accuracy of community detection was improved by a new update rule based on community similarity. Experiments were tested on a real social networks and LFR benchmarks. Compared with LPA and three improved LPA algorithms, the execution speed is improved by almost a dozen times, the modularities of the real social networks and the Normalized Mutual Information (NMI) of LFR (Lancichinetti Fortunato Radicchi) benchmark networks with more obscure community structure were significantly improved. The experimental results show that FNCS_LPA improves the accuracy and stability of community detection on the basis of improving execution speed.

Key words: community detection algorithm, Label Propagation Algorithm (LPA), node information list, node centrality, community similarity

摘要: 为了减少标签传播算法(LPA)中不必要的更新、解决算法准确率低且稳定性差的问题,提出了基于节点中心性和社区相似性的快速标签传播算法(FNCS_LPA)。按照节点中心性度量对网络的节点从低到高进行排序后加入节点信息列表,利用节点信息列表来指导更新过程,提高社区发现的稳定性并避免不必要的更新;采取基于社区相似性的更新规则,提高了社区发现的准确率。在真实社会网络和LFR基准网络上进行实验:相比LPA和三种较好的LPA改进算法,FNCS_LPA在执行速度方面提升了几十倍,真实社会网络的模块度也相对较高,在社区结构比较模糊的LFR基准网络上的归一化互信息有明显的优势。实验结果表明FNCS_LPA在提高执行速度的基础上,提高了算法的稳定性和准确率。

关键词: 社区发现算法, 标签传播算法, 节点信息列表, 节点中心性, 社区相似性

CLC Number: