Fast label propagation algorithm based on node centrality and community similarity

doi:10.11772/j.issn.1001-9081.2017102927

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

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

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

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

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

Abstract

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:

TP301.6

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.

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

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 5

Recommended Articles

Metrics

[1]	ZHENG Wenping, YUE Xiangdou, YANG Gui. Improved label propagation algorithm based on random walk [J]. Journal of Computer Applications, 2020, 40(12): 3423-3429.
[2]	WANG Shasha, FENG Ziliang, FU Keren. Saliency detection method based on graph node centrality and spatial autocorrelation [J]. Journal of Computer Applications, 2018, 38(12): 3547-3556.
[3]	WANG Yan, HUANG Faliang, YUAN Chang'an. Semi-synchronous communities detection algorithm based on label influence [J]. Journal of Computer Applications, 2016, 36(6): 1573-1578.
[4]	TAN Chunni, ZHANG Yumei, ZHANG Jiatong, WU Xiaojun. Community detection algorithm based on signal adaptive transmission [J]. Journal of Computer Applications, 2015, 35(6): 1552-1554.
[5]	SHI Mengyu, ZHOU Yong, XING Yan. Community detection by label propagation with LeaderRank method [J]. Journal of Computer Applications, 2015, 35(2): 448-451.