计算机科学 ›› 2021, Vol. 48 ›› Issue (3): 158-162.doi: 10.11896/jsjkx.200600075

• 数据库&大数据&数据科学 • 上一篇    下一篇

基于改进AdaBoost算法的复杂网络链路预测

龚追飞, 魏传佳   

  1. 浙江工业大学计算机科学与技术学院 杭州310023
  • 收稿日期:2020-06-12 修回日期:2020-08-10 出版日期:2021-03-15 发布日期:2021-03-05
  • 通讯作者: 龚追飞(793688937@qq.com)
  • 基金资助:
    国家自然科学基金(61773348);浙江省自然科学基金(LY17F030016)

Link Prediction of Complex Network Based on Improved AdaBoost Algorithm

GONG Zhui-fei, WEI Chuan-jia   

  1. College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China
  • Received:2020-06-12 Revised:2020-08-10 Online:2021-03-15 Published:2021-03-05
  • About author:GONG Zhui-fei,born in 1977,Ph.D candidate,lecturer,senior engineer.Her main research interests include complex network and link prediction.
  • Supported by:
    National Natural Science Foundation of China (61773348) and Natural Science Foundation of Zhejiang Province,China(LY17F030016).

摘要: 链路预测是复杂网络的重要研究方向,当前的链路预测算法因可利用的网络信息有限,导致预测算法的精确度受限。为了提高预测算法的性能,采用改进的AdaBoost算法进行链路预测。首先根据复杂网络样本建立邻接矩阵,完成样本的矩阵化处理;然后采用AdaBoost算法进行分类训练,通过权重投票获取预测结果;最后,考虑到复杂网络弱分类器预测正负误差分布的不均衡问题,设置权重调整因子η及其调整范围[η12],并根据η值动态调整AdaBoost算法的多个弱分类器分类结果的权重,从而获得准确的链路预测结果。实验结果证明,相比其他常用网络链路预测算法及传统AdaBoost算法,改进的AdaBoost算法的预测准确率优势明显,且在节点数量较多时,其预测时间性能和其他算法的差距较小。

关键词: AdaBoost, 复杂网络, 链路预测, 邻接矩阵, 权重调整

Abstract: Link prediction is an important research direction of complex networks.The accuracy of current link prediction algorithm is limited due to limited network information available.In order to improve the link prediction performance of complex network,the improved AdaBoost algorithm is used to predict the link.Firstly,according to the complex network samples,the adjacency matrix is established,and the connection relationship between network nodes is constructed.Then the AdaBoost algorithm is used for classification training,and the prediction results are obtained by weight voting.Finally,considering the imbalance of the distribution of positive and negative errors in the prediction of complex network structure,the weight readjustment factor η and its adjustment range are set [η12].The weight of multiple weak classifiers in AdaBoost algorithm is dynamically adjusted according to the value to obtain accurate link prediction results.Experiments show that,compared with other common network link prediction algorithms and traditional AdaBoost algorithm,the improved AdaBoost algorithm has obvious advantages in prediction accuracy,and when there are a large number of nodes,the difference of prediction time performance between the improved AdaBoost and other algorithms is small.

Key words: AdaBoost, Adjacency matrix, Complex network, Link prediction, Weight adjustment

中图分类号: 

  • TP391
[1]ZHANG M,CHEN Y.Link prediction based on graph neural networks [J].arXiv,2018,9(691):1802-1807.
[2]CHIU C,ZHAN J.Deep learning for link prediction in dynamic networks using weak estimators[J].IEEE Access,2018,6(1):35937-35945.
[3]LI T,ZHANG J,PHILIP S Y,et al.Deep dynamic network embedding for link prediction[J].IEEE Access,2018,6(1):29219-29230.
[4]HOU Y,HOLDER L B.Deep learning approach to link weight prediction[C]//2017 International Joint Conference on Neural Networks.IEEE,2017:1855-1862.
[5]CAI L,WANG J,HE T,et al.A novel link prediction algorithm based on deepwalk and clustering method[J].Joumal of Phy-sics:Conference Series,2018,1069(1):012131.
[6]JIN D,LIU Z Y,HE R F,et al.Robust and strong explanatory community discovery method for complex networks with attri-butes[J].Journal of Computer Science,2018,41(7):1476-1489.
[7]PAN Y H,YU H T,WU Y.Link prediction method based on complex network dynamics model [J].Journal of Network and Information Security,2019(6):67-74.
[8]WANG P,XU B W,WU Y R.Link prediction in social net-works:the state-of-the-art[J].Science China Information,2014,58(1):1-38.
[9]HU W B,PENG C,LIANG H L,et al.Event detection method based on link prediction for social network evolution[J].Journal of Software,2015,26(9):2339-2355.
[10]ZHOU T,LUY L Y,ZHANG Y C.Predicting missing links via local information[J].European Physical Journal B,2009,71(4):623-630.
[11]ZHANG Z G,LI S B,MA W L,et al.A node traversal link prediction algorithm for improving common neighborhood [J].Minicomputer System,2018,39(2):207-213.
[12]PAN Y H,YU H T,LIU S X.Link prediction algorithm based on neural network [J].Journal of Network and Information Security,2018,32(7):34-42.
[13]SCABINI L F S,CONDORI R H M,GONALVES W N,et al.Multilayer complex network descriptors for color-texture cha-racterization[J].Information Science,2018,5(1):3-10.
[14]ALONSO L,MENDEZ-BERMUDEZ J A,CONZALEZ-ME-LENDREZ A,et al.Weighted random-geometric and random-rectangular graphs:spectral and eigenfunction properties of the adjacency matrix[J].Journal of Complex Networks,2018,6(5):753-766.
[15]CORBELLINI A,GODOY D,MATEOS C,et al.DPM:A novel distributed large-scale social graph processing framework for link prediction algorithms[J].Future Generation Computer Systems,2018,78(1):474-480.
[16]WU J.A generalized tree augmented naive Bayes link prediction model[J].Journal of Computational Science,2018,27(1):206-217.
[17]WAND L D,XU H.Diversity analysis and improvement of AdaBoost [J].Computer Application,2018,38(3):650-654.
[18]ALSHEMARRY M S,LI Y,ABDULLA S.Ensemble of adaboost cascades of 3L-LBPs classifiers for license plates detection with low quality images[J].Expert Systems with Application,2018,92(2):216-235.
[19]YANG Y M,CHEN X.Gait recognition method using inertial sensor and AdaBoost algorithm [J].Computer Application Research,2019,36(4):258-262.
[20]JIN L M.Infinite dimension adaBoost algorithm based on support vector machine and its application [J].China New Communication,2018,20(8):208-213.
[21]GU Y P,CHENG L S.Classification of unbalanced data based on MTS AdaBoost [J].Computer Application Research,2018,3(8):346-348.
[22]FENG X J,MA M D,WANG D Y.Face detection system based on improved adaBoost algorithm [J].Computer Technology and Development,2019,29(3):89-92.
[23]SHEN X,ZHU J H.Face detection based on skin color and improved AdaBoost algorithm [J].Sensors and Microsystems,2019,38(4):149-151.
[1] 郑文萍, 刘美麟, 杨贵.
一种基于节点稳定性和邻域相似性的社区发现算法
Community Detection Algorithm Based on Node Stability and Neighbor Similarity
计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146
[2] 杨波, 李远彪.
数据科学与大数据技术课程体系的复杂网络分析
Complex Network Analysis on Curriculum System of Data Science and Big Data Technology
计算机科学, 2022, 49(6A): 680-685. https://doi.org/10.11896/jsjkx.210800123
[3] 何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超.
比特币实体交易模式分析
Analysis of Bitcoin Entity Transaction Patterns
计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178
[4] 王本钰, 顾益军, 彭舒凡, 郑棣文.
融合动态距离和随机竞争学习的社区发现算法
Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning
计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206
[5] 高越, 傅湘玲, 欧阳天雄, 陈松龄, 闫晨巍.
基于时空自适应图卷积神经网络的脑电信号情绪识别
EEG Emotion Recognition Based on Spatiotemporal Self-Adaptive Graph ConvolutionalNeural Network
计算机科学, 2022, 49(4): 30-36. https://doi.org/10.11896/jsjkx.210900200
[6] 李勇, 吴京鹏, 张钟颖, 张强.
融合快速注意力机制的节点无特征网络链路预测算法
Link Prediction for Node Featureless Networks Based on Faster Attention Mechanism
计算机科学, 2022, 49(4): 43-48. https://doi.org/10.11896/jsjkx.210800276
[7] 陈世聪, 袁得嵛, 黄淑华, 杨明.
基于结构深度网络嵌入模型的节点标签分类算法
Node Label Classification Algorithm Based on Structural Depth Network Embedding Model
计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177
[8] 赵学磊, 季新生, 刘树新, 李英乐, 李海涛.
基于路径连接强度的有向网络链路预测方法
Link Prediction Method for Directed Networks Based on Path Connection Strength
计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107
[9] 李家文, 郭炳晖, 杨小博, 郑志明.
基于信息传播的致病基因识别研究
Disease Genes Recognition Based on Information Propagation
计算机科学, 2022, 49(1): 264-270. https://doi.org/10.11896/jsjkx.201100129
[10] 穆俊芳, 郑文萍, 王杰, 梁吉业.
基于重连机制的复杂网络鲁棒性分析
Robustness Analysis of Complex Network Based on Rewiring Mechanism
计算机科学, 2021, 48(7): 130-136. https://doi.org/10.11896/jsjkx.201000108
[11] 胡军, 王雨桐, 何欣蔚, 武晖栋, 李慧嘉.
基于复杂网络的全球航空网络结构分析与应用
Analysis and Application of Global Aviation Network Structure Based on Complex Network
计算机科学, 2021, 48(6A): 321-325. https://doi.org/10.11896/jsjkx.200900112
[12] 王学光, 张爱新, 窦炳琳.
复杂网络上的非线性负载容量模型
Non-linear Load Capacity Model of Complex Networks
计算机科学, 2021, 48(6): 282-287. https://doi.org/10.11896/jsjkx.200700040
[13] 马媛媛, 韩华, 瞿倩倩.
基于节点亲密度的重要性评估算法
Importance Evaluation Algorithm Based on Node Intimate Degree
计算机科学, 2021, 48(5): 140-146. https://doi.org/10.11896/jsjkx.200300184
[14] 殷子樵, 郭炳晖, 马双鸽, 米志龙, 孙怡帆, 郑志明.
群智体系网络结构的自治调节:从生物调控网络结构谈起
Autonomous Structural Adjustment of Crowd Intelligence Network: Begin from Structure of Biological Regulatory Network
计算机科学, 2021, 48(5): 184-189. https://doi.org/10.11896/jsjkx.210200161
[15] 刘胜久, 李天瑞, 谢鹏, 刘佳.
带权图的多重分形度量
Measure for Multi-fractals of Weighted Graphs
计算机科学, 2021, 48(3): 136-143. https://doi.org/10.11896/jsjkx.200700159
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!