Please wait a minute...
Data Analysis and Knowledge Discovery  2018, Vol. 2 Issue (3): 60-69    DOI: 10.11925/infotech.2096-3467.2017.0964
Current Issue | Archive | Adv Search |
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)
Download: PDF (0 KB)   HTML ( 0
Export: BibTeX | EndNote (RIS)      
Abstract  

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

Key wordsLabel Propagation Algorithm      Node Information List      Node Preference to Community     
Received: 22 September 2017      Published: 31 August 2020
ZTFLH:  TP391  

Cite this article:

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.

URL:

http://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/10.11925/infotech.2096-3467.2017.0964     OR     http://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/Y2018/V2/I3/60

网络名称 节点数 边数 描述
email 1 133 5 451 美国大学生email社交网络[21]
CA-GrQc 4 158 13 422 广义相对论研究团体网络[22]
CA-Hepth 8 638 24 807 高能物理学理论研究团体网络[22]
PGP 10 680 24 316 Pretty-Good-Privacy算法研究网络[23]
网络名称 5次迭代后正确划分节点
所占百分比
算法收敛所需的
迭代次数
email 96.64% 17.89
CA-GrQc 99.37% 15.7
CA-Hepth 98.97% 59.75
PGP 99.37% 21.9
网络名称 节点数 边数 描述
karate 34 78 美国空手道俱乐部网络[24]
dolphins 62 159 海豚数据网络[18]
polbooks 105 441 亚马逊美国政治书销售网络[25]
football 115 613 美国秋季大学生足球队网络[26]
参数 意义
N 网络中的节点个数
k 网络的平均度数
maxk 网络的最大度数
minc 社区内的最少节点个数
maxc 社区内的最多节点个数
mu 节点与社区外部连接的概率
网络名称 N k maxk minc maxc mu
1000S 1 000 10 50 10 50 0.1~0.8
1000B 1 000 10 50 20 100 0.1~0.8
5000S 5 000 10 50 10 50 0.1~0.8
5000B 5 000 10 50 20 100 0.1~0.8
网络名称 SOCP_LPA LPA Cen_LP NIBLPA
karate 0.371 0.345 0.416 0.423
dolphins 0.523 0.483 0.523 0.521
polbooks 0.518 0.493 0.518 0.497
football 0.573 0.588 0.589 0.582
email 0.497 0.234 0.427 0.427
CA-GrQc 0.788 0.775 0.740 0.710
CA-Hepth 0.671 0.628 0.621 0.610
PGP 0.819 0.802 0.750 0.783
网络名称 SOCP_LPA LPA Cen_LP NIBLPA
karate 0.371 0.416 0.416 0.423
dolphins 0.526 0.527 0.526 0.521
polbooks 0.523 0.526 0.523 0.497
football 0.603 0.605 0.601 0.582
email 0.545 0.443 0.536 0.427
CA-GrQc 0.796 0.783 0.743 0.710
CA-Hepth 0.685 0.647 0.633 0.610
PGP 0.827 0.816 0.756 0.783
[1] 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
[1] Wang Sili, Zhu Zhongming, Yang Heng, Liu Wei. Research on Automatic Identification of Hypernym-Hyponym Relations of Domain Concepts Based on Pattern and Projection Learning [J]. 数据分析与知识发现, 0, (): 1-.
[2] Weng Mengjuan,Yao Changqing,Han Hongqi,Wang Lijun,Ran Yaxin. Classification and Indexing Method with CNN for Imbalanced Datasets[J]. 数据分析与知识发现, 2020, 4(7): 87-95.
[3] Tang Xiaobo,Gao Hexuan. Classification of Health Questions Based on Vector Extension of Keywords[J]. 数据分析与知识发现, 2020, 4(7): 66-75.
[4] Qiu Erli,He Hongwei,Yi Chengqi,Li Huiying. Research on Public Policy Support Based on Character-level CNN Technology[J]. 数据分析与知识发现, 2020, 4(7): 28-37.
[5] Wang Jiandong,Yu Shiyang. Principles on Constructing National Economic Brain[J]. 数据分析与知识发现, 2020, 4(7): 2-17.
[6] Xu Hongxia,Yu Qianqian,Qian Li. Studying Content Interaction Data with Topic Model and Sentiment Analysis[J]. 数据分析与知识发现, 2020, 4(7): 110-117.
[7] Li Keyu,Wang Hao,Gong Lijuan,Tang Huihui. Measurement and Distribution of Index Quality in Research Topics from Academic Databases[J]. 数据分析与知识发现, 2020, 4(6): 91-108.
[8] Wei Tingxin,Bai Wenlei,Qu Weiguang. Sense Prediction for Chinese OOV Based on Word Embedding and Semantic Knowledge[J]. 数据分析与知识发现, 2020, 4(6): 109-117.
[9] Yang Heng,Wang Sili,Zhu Zhongming,Liu Wei,Wang Nan. Recommending Domain Knowledge Based on Parallel Collaborative Filtering Algorithm[J]. 数据分析与知识发现, 2020, 4(6): 15-21.
[10] Jiao Qihang,Le Xiaoqiu. Generating Sentences of Contrast Relationship[J]. 数据分析与知识发现, 2020, 4(6): 43-50.
[11] Cai Yongming,Liu Lu,Wang Kewei. Identifying Key Users and Topics from Online Learning Community[J]. 数据分析与知识发现, 2020, 4(6): 69-79.
[12] Wang Mo,Cui Yunpeng,Chen Li,Li Huan. A Deep Learning-based Method of Argumentative Zoning for Research Articles[J]. 数据分析与知识发现, 2020, 4(6): 60-68.
[13] Ye Guanghui, Xu Tong. Research on Dynamic City Profile Based on Evolutionary Analysis [J]. 数据分析与知识发现, 0, (): 1-.
[14] Li Junlian,Wu Yingjie,Deng Panpan,Leng Fuhai. Automatic Data Processing Strategy of Citation Anomie Based on Feature Fusion[J]. 数据分析与知识发现, 2020, 4(5): 38-45.
[15] Liu Ping,Peng Xiaofang. Calculating Word Similarities Based on Formal Concept Analysis[J]. 数据分析与知识发现, 2020, 4(5): 66-74.
  Copyright © 2016 Data Analysis and Knowledge Discovery   Tel/Fax:(010)82626611-6626,82624938   E-mail:jishu@mail.las.ac.cn