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: HTML ( 4 ) 
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 words： Label Propagation Algorithm      Node Information List      Node Preference to Community     
Received: 22 September 2017      Published: 31 August 2020
ZTFLH:  TP391  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Suqi Zhang
Xing Gao
Shijie Huo
Jingjin Guo
Junhua Gu

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:

https://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/10.11925/infotech.2096-3467.2017.0964     OR     https://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 Hong, Shu Zhan, Gao Yinquan, Tian Wenhong. Analyzing Implicit Discourse Relation with Single Classifier and Multi-Task Network[J]. 数据分析与知识发现, 2021, 5(11): 80-88.
[2] Wu Yanwen, Cai Qiuting, Liu Zhi, Deng Yunze. Digital Resource Recommendation Based on Multi-Source Data and Scene Similarity Calculation[J]. 数据分析与知识发现, 2021, 5(11): 114-123.
[3] Li Zhenyu, Li Shuqing. Deep Collaborative Filtering Algorithm with Embedding Implicit Similarity Groups[J]. 数据分析与知识发现, 2021, 5(11): 124-134.
[4] Dong Miao, Su Zhongqi, Zhou Xiaobei, Lan Xue, Cui Zhigang, Cui Lei. Improving PubMedBERT for CID-Entity-Relation Classification Using Text-CNN[J]. 数据分析与知识发现, 2021, 5(11): 145-152.
[5] Yu Chuanming, Zhang Zhengang, Kong Lingge. Comparing Knowledge Graph Representation Models for Link Prediction[J]. 数据分析与知识发现, 2021, 5(11): 29-44.
[6] Ding Hao, Ai Wenhua, Hu Guangwei, Li Shuqing, Suo Wei. A Personalized Recommendation Model with Time Series Fluctuation of User Interest[J]. 数据分析与知识发现, 2021, 5(11): 45-58.
[7] Hua Bin, Wu Nuo, He Xin. Integrating Expert Reviews for Government Information Projects with Knowledge Fusion[J]. 数据分析与知识发现, 2021, 5(10): 124-136.
[8] Wang Yuan, Shi Kaize, Niu Zhendong. Position-Aware Stepwise Tagging Method for Triples Extraction of Entity-Relationship[J]. 数据分析与知识发现, 2021, 5(10): 71-80.
[9] Yang Chen, Chen Xiaohong, Wang Chuhan, Liu Tingting. Recommendation Strategy Based on Users’ Preferences for Fine-Grained Attributes[J]. 数据分析与知识发现, 2021, 5(10): 94-102.
[10] Dai Zhihong, Hao Xiaoling. Extracting Hypernym-Hyponym Relationship for Financial Market Applications[J]. 数据分析与知识发现, 2021, 5(10): 60-70.
[11] Wang Xuefeng, Ren Huichao, Liu Yuqin. Research on the Visualization Method of Drawing Technology Theme Map with Clusters [J]. 数据分析与知识发现, 0, (): 1-.
[12] Wang Yifan,Li Bo,Shi Hua,Miao Wei,Jiang Bin. Annotation Method for Extracting Entity Relationship from Ancient Chinese Works[J]. 数据分析与知识发现, 2021, 5(9): 63-74.
[13] Che Hongxin,Wang Tong,Wang Wei. Comparing Prediction Models for Prostate Cancer[J]. 数据分析与知识发现, 2021, 5(9): 107-114.
[14] Zhou Yang,Li Xuejun,Wang Donglei,Chen Fang,Peng Lijuan. Visualizing Knowledge Graph for Explosive Formula Design[J]. 数据分析与知识发现, 2021, 5(9): 42-53.
[15] Ma Jiangwei, Lv Xueqiang, You Xindong, Xiao Gang, Han Junmei. Extracting Relationship Among Military Domains with BERT and Relation Position Features[J]. 数据分析与知识发现, 2021, 5(8): 1-12.
  Copyright © 2016 Data Analysis and Knowledge Discovery   Tel/Fax:(010)82626611-6626，82624938   E-mail:jishu@mail.las.ac.cn