A Label Propagation Algorithm Based on Speed Optimization and Community Preference
Zhang Suqi1(), Gao Xing2, Huo Shijie2, Guo Jingjin2, Gu Junhua2
1(School of Information Engineering, Tianjin University of Commerce, Tianjin 300134, China) 2(School of Computer Science and Software, Hebei University of Technology, Tianjin 300401, China)
[Objective] This paper aims to reduce the unnecessary updates and improve the accuracy of Label Propagation Algorithm. [Methods] First, we used the node information list to direct the update process and increase the execution speed. Then, we proposed new updating rules based on the node preference to improve the accuracy of community detection. [Results] Compared with the classic label propagation algorithm and two improved algorithms, the proposed one significantly reduced the number of iterations on large-scale social networks, as well as improved the value of Normalized Mutual Information and F-measure of LFR benchmark network. [Limitations] The new algorithm’s updating sequence is random, which needs to be investigated in further studies. [Conclusions] The SOCP_LPA improves the accuracy of community detection and the processing speed.
张素琪, 高星, 霍士杰, 郭京津, 顾军华. 基于速度优化和社区偏向的标签传播算法*[J]. 数据分析与知识发现, 2018, 2(3): 60-69.
Zhang Suqi,Gao Xing,Huo Shijie,Guo Jingjin,Gu Junhua. A Label Propagation Algorithm Based on Speed Optimization and Community Preference. Data Analysis and Knowledge Discovery, 2018, 2(3): 60-69.
Radicchi F, Castellano C, Cecconi F, et al.Defining and Identifying Communities in Networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2004, 101(9): 2658-2663.
doi: 10.1073/pnas.0400054101
[2]
Girvan M, Newman M E J. Community Structure in Social and Biological Networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12): 7821-7826.
doi: 10.1073/pnas.122653799
[3]
Newman M E J. Fast Algorithm for Detecting Community Structure in Networks[J]. Physical Review E, 2004, 69(6): 66-73.
doi: 10.1103/PhysRevE.69.066133
pmid: 15244693
[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.
doi: 10.1007/11569596_31
[5]
Shang R, Bai J, Jiao L, et al.Community Detection Based on Modularity and an Improved Genetic Algorithm[J]. Physica A: Statistical Mechanics and Its Applications, 2013, 392(5): 1215-1231.
doi: 10.1016/j.physa.2012.11.003
[6]
Brandes U, Delling D, Gaertler M, et al.On Modularity Clustering[J]. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(2): 172-188.
doi: 10.1109/TKDE.2007.190689
[7]
Bu Z, Zhang C, Xia Z, et al.A Fast Parallel Modularity Optimization Algorithm (FPMQA) for Community Detection in Online Social Network[J]. Knowledge-Based Systems, 2013, 50(3): 246-259.
doi: 10.1016/j.knosys.2013.06.014
[8]
Zhang S, Zhang H.Normalized Modularity Optimization Method for Community Identification with Degree Adjustment[J]. Physical Review E, 2013, 88(5): 447-453.
doi: 10.1103/PhysRevE.88.052802
pmid: 24329313
[9]
Shiga M, Takigawa I, Mamitsuka H.A Spectral Clustering Approach to Optimally Combining Numerical Vectors with a Modular Network[C]// Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, California, USA. New York, NY, USA: ACM, 2007: 647-656.
[10]
Shen H, Cheng X.Spectral Methods for the Detection of Network Community Structure: A Comparative Analysis[J]. Journal of Statistical Mechanics: Theory and Experiment, 2010(10): 100-108
doi: 10.1088/1742-5468/2010/10/P10020
[11]
Huang L, Li R, Chen H, et al.Detecting Network Communities Using Regularized Spectral Clustering Algorithm[J]. Artificial Intelligence Review, 2014,41(4): 579-594.
doi: 10.1007/s10462-012-9325-3
[12]
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.
doi: 10.1103/PhysRevE.76.036106
pmid: 17930305
[13]
Zhu X, Ghahramani Z.Learning from Labeled and Unlabeled Data with Label Propagation [R]. Technical Report CMU-CALD-02-107. Pittsburghers, USA: Carnegie Mellon University, 2002.
[14]
Xie J, Szymanski B K.LabelRank: A Stabilized Label Propagation Algorithm for Community Detection in Networks[C]//Proceedings of 2013 IEEE 2nd Network Science Workshop (NSW). IEEE, 2013: 138-143.
[15]
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(5): 210-223.
doi: 10.1155/2014/627581
pmid: 4066938
[16]
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.
doi: 10.1016/j.physa.2015.05.080
[17]
Chin J H, Ratnavelu K.Detecting Community Structure by Using a Constrained Label Propagation Algorithm[J]. PLoS One, 2016, 11(5): 214-223.
doi: 10.1371/journal.pone.0155320
pmid: 27176470
[18]
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): 165-187.
doi: 10.1142/S0218001416590242
[19]
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.
doi: 10.1016/j.physa.2017.01.030
[20]
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.
doi: 10.1142/S0217984917501627
[21]
Zhang X K, Song C, 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.
[22]
Leskovec J, Kleinberg J, Faloutsos C.Graph Evolution: Densification and Shrinking Diameters[J]. ACM Transactions on Knowledge Discovery from Data (TKDD), 2007, 1(1): 2-9.
doi: 10.1145/1217299
[23]
Zhang X K, 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.
doi: 10.1142/S0217979215500290
[24]
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.
[25]
Shang R, Liu H, Jiao L.Multi-objective Clustering Technique Based on K-nodes Update Policy and Similarity Matrix for Mining Communities in Social Networks[J]. Physica A: Statistical Mechanics and Its Applications, 2017, 486: 1-24.
doi: 10.1016/j.physa.2017.05.026
[26]
Zhou K, Martin A, Pan Q, et al.Evidential Label Propagation Algorithm for Graphs[C] // Proceedings of the 19th International Conference on Information Fusion, Heidelberg, Germany.IEEE, 2016: 1316-1323.
[27]
Lancichinetti A, Fortunato S, Radicchi F.Benchmark Graphs for Testing Community Detection Algorithms[J]. Physical Review E, 2008, 78(4): 46-61.
doi: 10.1103/PhysRevE.78.046110
pmid: 18999496
[28]
Danon L, Diaz-Guilera A, Duch J, et al.Comparing Community Structure Identification[J]. Journal of Statistical Mechanics: Theory and Experiment, 2005, 15(9): 98-108.
[29]
Zhu M, Meng F, Zhou Y.Semisupervised Clustering for Networks Based on Fast Affinity Propagation[J]. Mathematical Problems in Engineering, 2013: 10-23.
doi: 10.1155/2013/385265
