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

doi:10.11772/j.issn.1001-9081.2017102927

计算机应用 ›› 2018, Vol. 38 ›› Issue (5): 1320-1326.DOI: 10.11772/j.issn.1001-9081.2017102927

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

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

1. 河北工业大学计算机科学与软件学院, 天津 300401;
2. 河北省大数据实验室(河北工业大学), 天津 300401

收稿日期:2017-12-14 修回日期:2017-12-14 出版日期:2018-05-10 发布日期:2018-05-24
通讯作者: 顾军华
作者简介:顾军华(1966-),男,河北赵县人,教授,博士,CCF会员,主要研究方向:智能信息处理、数据挖掘;霍士杰(1993-),男,河北石家庄人,硕士研究生,CCF会员,主要研究方向:数据挖掘、计算机仿真;王守彬(1994-),男,河南商丘人,硕士研究生,主要研究方向:数据挖掘、计算机仿真;田喆(1994-),男,天津人,硕士研究生,主要研究方向:数据挖掘。
基金资助:
天津市科技计划项目（16ZXHLSF0023）；河北省科技计划项目（17210305D）。

Fast label propagation algorithm based on node centrality and community similarity

GU Junhua^1,2, HUO Shijie^1,2, WANG Shoubin^1,2, TIAN Zhe^1,2

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).

摘要/Abstract

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

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

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

中图分类号:

TP301.6

顾军华, 霍士杰, 王守彬, 田喆. 基于节点中心性和社区相似性的快速标签传播算法[J]. 计算机应用, 2018, 38(5): 1320-1326.

GU Junhua, HUO Shijie, WANG Shoubin, TIAN Zhe. Fast label propagation algorithm based on node centrality and community similarity[J]. Journal of Computer Applications, 2018, 38(5): 1320-1326.

参考文献

[1] RAGHAVAN U N, ALBERT R, KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E, 2007, 76(3):96-106.
[2] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12):7821-7826.
[3] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6):66-73.
[4] PONS P, LATAPY M. Computing communities in large networks using random walks[J]. Journal of Graph Algorithms and Applications, 2006, 10(2):191-218.
[5] XING Y, MENG F, ZHOU Y, et al. A node influence based label propagation algorithm for community detection in networks[J]. The Scientific World Journal, 2014, 2014(5):210-223.
[6] SUN H, LIU J, HUANG J, et al. CenLP:a centrality-based label propagation algorithm for community detection in networks[J]. Physica A:Statistical Mechanics and its Applications, 2015, 436(15):767-780.
[7] MA T, XIA Z. An improved label propagation algorithm based on node importance and random walk for community detection[J]. Modern Physics Letters B, 2017, 31(14):98-116.
[8] ZHANG X, CHEN S, JIA J, et al. An improved label propagation algorithm based on the similarity matrix using random walk[J]. International Journal of Modern Physics B, 2016, 30(16):93-108.
[9] LESKOVEC J, KLEINBERG J, FALOUTSOS C. Graph evolution:densification and shrinking diameters[J]. ACM Transactions on Knowledge Discovery from Data, 2007, 1(1):2-9.
[10] ZHANG X, FEI S, SONG C, et al. Label propagation algorithm based on local cycles for community detection[J]. International Journal of Modern Physics B, 2015, 29(5):15-28.
[11] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6):66-78.
[12] ZHOU K, MARTIN A, PAN Q, et al. Evidential label propagation algorithm for graphs[C]//Proceedings of the 201619th International Conference on Information Fusion. Piscataway, NJ:IEEE, 2016:1316-1323.
[13] LIU S, ZHU F, LIU H, et al. A core leader based label propagation algorithm for community detection[J]. China Communications, 2016, 13(12):97-106.
[14] LI W, HUANG C, WANG M, et al. Stepping community detection algorithm based on label propagation and similarity[J]. Physica A:Statistical Mechanics and its Applications, 2017, 472:145-155.
[15] SHANG R, ZHANG W, JIAO L, et al. Circularly searching core nodes based label propagation algorithm for community detection[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2016, 30(8):24-46.
[16] LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E, 2008, 78(4):46-61.
[17] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6):66-78.

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

Fast label propagation algorithm based on node centrality and community similarity

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

[1]	秦丽, 郝志刚, 李国亮. 国家食品安全标准图谱的构建及关联性分析[J]. 计算机应用, 2021, 41(4): 1005-1011.
[2]	郑文萍, 岳香豆, 杨贵. 基于随机游走的改进标签传播算法[J]. 计算机应用, 2020, 40(12): 3423-3429.
[3]	王莎莎, 冯子亮, 傅可人. 基于图节点中心性和空间自相关的显著性检测方法[J]. 计算机应用, 2018, 38(12): 3547-3556.
[4]	石梦雨, 周勇, 邢艳. 基于LeaderRank的标签传播社区发现算法[J]. 计算机应用, 2015, 35(2): 448-451.