计算机科学 ›› 2022, Vol. 49 ›› Issue (2): 216-222.doi: 10.11896/jsjkx.210100107

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

基于路径连接强度的有向网络链路预测方法

赵学磊, 季新生, 刘树新, 李英乐, 李海涛   

  1. 中国人民解放军战略支援部队信息工程大学 郑州450002
  • 收稿日期:2021-01-14 修回日期:2021-04-07 出版日期:2022-02-15 发布日期:2022-02-23
  • 通讯作者: 刘树新(liushuxin11@126.com)
  • 作者简介:zxl96@alu.uestc.edu.cn
  • 基金资助:
    国家自然科学基金(61803384)

Link Prediction Method for Directed Networks Based on Path Connection Strength

ZHAO Xue-lei, JI Xin-sheng, LIU Shu-xin, LI Ying-le, LI Hai-tao   

  1. PLA Strategic Support Force Information Engineering University,Zhengzhou 450002,China
  • Received:2021-01-14 Revised:2021-04-07 Online:2022-02-15 Published:2022-02-23
  • About author:ZHAO Xue-lei,born in 1996,postgra-duate.His main research interests include complex network and link prediction.
    LIU Shu-xin,born in 1987,Ph.D.His main research interests include network evolution and network behavior analysis.
  • Supported by:
    National Natural Science Foundation of China(61803384).

摘要: 链路预测旨在利用可获得的网络拓扑信息预测未知的连接关系。基于路径联系的预测方法在无向网络中取得了较好的效果。然而,在有向网络下,相同长度的路径因路径中连边方向不同会造成节点连接强度不同,传统预测方法难以区分路径异构造成的差异。鉴于此,首先以边权矩阵量化各类有向边连接强度的差异,进而为节点间不同异构的多类路径计算其连接强度,然后区分同一长度路径下各类路径的作用大小,最后综合多阶不同长度路径贡献,提出了一种基于路径连接强度的有向网络链路预测方法。在9个真实网络数据集上进行了实验,结果表明,考虑路径连接强度差异有效提高了在AUC及Precision衡量标准下的预测性能。

关键词: 复杂网络, 连接强度, 链路预测, 有向路径

Abstract: Link prediction aims to predict unknown links using available network topology information.Prediction methods based on paths perform well in undirected networks.However,paths of the same length have different node connection strength due to different type of links through the path in directed network.Traditional methods is difficult to distinguish the path heterogeneity.Given this,the difference in the strength of three types of directed links is first quantified in terms of the link weight matrix,then the connection strength of different heterogeneous classpaths between nodes is calculated and the effect of different paths under the same length path is distinguished.Finally,a directed network link prediction method based on the path connection strength is proposed by integrating the contribution of multi-order paths of different lengths.Validation of 9 real networks shows that accounting for differences in path connection strength effectively improves prediction performance under the AUC and Precision metrics.

Key words: Complex network, Connection strength, Directed paths, Link prediction

中图分类号: 

  • TP301.6
[1]TAN Y,WU J,ZHONG Q.Complex network[J].Journal ofPhysics:Conference Series,2020,1601:032011.
[2]FAN T,XIONG S,ZHAO W,et al.Information spread link prediction through multi-layer of social network based on trusted central nodes[J].Peer-to-Peer Networking and Applications,2019,12(5):1028-1040.
[3]DZAFERAGIC M,KAMINSKI N,MCBRIDE N,et al.A Functional Complexity Framework for the Analysis of Telecommunication Networks[J].Journal of Complex Networks,2018,6(6):971-988.
[4]CANNISTRACI C V,ALANIS-LOBATO G,RAVASI T.Erratum:From Link-Prediction in Brain Connectomes and Protein Interactomes to the Local-Community-Paradigm in Complex Networks:1[J].Scientific Reports,2015,5(1):9794.
[5]WANG H,LE Z C,GONG X,et al.Review of Link Prediction Methods Based on Feature Classification[J].Computer Science,2020,47(8):302-312.
[6]LÜ L,ZHOU T.Link Prediction in Complex Networks:A Survey[J].Physica A:Statistical Mechanics and Its Applications,2011,390(6):1150-1170.
[7]MARTÍNEZ V,BERZAL F,CUBERO J C.A survey of linkprediction in complex networks[J].ACM Computing Surveys (CSUR),2016,49(4):1-33.
[8]ZARE H,NIKOOIE M A,MORADI P.Enhanced recommender system using predictive network approach[J].Physica A Statistical Mechanics & Its Applications,2019,520:332-337.
[9]LESKOVEC J,HORVITZ E.Planetary-scale views on a large instant-messaging network[C]//Proceedings of the 17th International Conference on World Wide Web.2008:915-924.
[10]ZHANG X,ZHAO C,WANG X,et al.Identifying missing and spurious interactions in directed networks[C]//Proceedings of the 9th International Conference on Wireless Algorithms,Systems,and Applications.2014:470-481.
[11]SHANG K,SMALL M,YAN W.Link direction for link prediction[J].Physica A:Statistical Mechanics and its Applications,2017,469:767-776.
[12]ZHANG Q M,LÜ L,WANG W Q,et al.Potential theory for di-rected networks[J].PloS One,2013,8(2):e55437.
[13]LI J,PENG J,LIU S,et al.Link Prediction in Directed Networks Utilizing the Role of Reciprocal Links[J].IEEE Access,2020,8:28668-28680.
[14]BÜTÜN E,KAYA M,ALHAJJ R.Extension of Neighbor-Based Link Prediction Methods for Directed,Weighted and Temporal Social Networks[J].Information Sciences,2018,463/464:152-165.
[15]PECH R,HAO D,LEE Y L,et al.Link Prediction via Linear Optimization[J].Physica A:Statistical Mechanics and Its Applications,2019,528:121319.
[16]LI X,LI P,ZHU Q.Directed Network Representation Method Based on Hierarchical Structure Information[J].Computer Science,2021,48(2):100-104.
[17]LÜ L,JIN C H,ZHOU T.Similarity index based on local paths for link prediction of complex networks[J].Physical Review E,2009,80(2):046122.
[18]WANG K,LIU S X,CHEN H C,et al.A New Link Prediction Method for Complex Networks Based on Resources Carrying Capacity Between Nodes[J].Journal of Electronics and Information Technology,2019,41(5):1225-1234.
[19]WANG K,LI X,LAN J L,et al.A New Link Prediction Methodfor Complex Networks Based on Topological Effectiveness of Resource Transmission Paths[J].Journal of Electronics and Information Technology,2020,42(3):653-660.
[20]LIU S,JI X,LIU C,et al.Extended Resource Allocation Index for Link Prediction of Complex Network[J].Physica A:Statistical Mechanics and Its Applications,2017,479:174-183.
[21]LIU S X,LI X,CHEN H C,et al.Link prediction method based on matching degree of resource transmission for complex network[J].Journal on Communications,2020,41(6):70-79.
[22]HANLEY J A,MCNEIL B J.The meaning and use of the area under a receiver operating characteristic (ROC) curve[J].Ra-diology,1982,143(1):29-36.
[23]LAWERA M.Predictive Inference:An Introduction[J].Technometrics,1995,37(1):121.
[24]KUNEGIS J.KONECT:the Koblenz network collection[C]//International Conference on World Wide Web Companion.ACM,2013:1343-1350.
[1] 郑文萍, 刘美麟, 杨贵.
一种基于节点稳定性和邻域相似性的社区发现算法
Community Detection Algorithm Based on Node Stability and Neighbor Similarity
计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146
[2] 何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超.
比特币实体交易模式分析
Analysis of Bitcoin Entity Transaction Patterns
计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178
[3] 杨波, 李远彪.
数据科学与大数据技术课程体系的复杂网络分析
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
[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] 李勇, 吴京鹏, 张钟颖, 张强.
融合快速注意力机制的节点无特征网络链路预测算法
Link Prediction for Node Featureless Networks Based on Faster Attention Mechanism
计算机科学, 2022, 49(4): 43-48. https://doi.org/10.11896/jsjkx.210800276
[6] 陈世聪, 袁得嵛, 黄淑华, 杨明.
基于结构深度网络嵌入模型的节点标签分类算法
Node Label Classification Algorithm Based on Structural Depth Network Embedding Model
计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177
[7] 李家文, 郭炳晖, 杨小博, 郑志明.
基于信息传播的致病基因识别研究
Disease Genes Recognition Based on Information Propagation
计算机科学, 2022, 49(1): 264-270. https://doi.org/10.11896/jsjkx.201100129
[8] 穆俊芳, 郑文萍, 王杰, 梁吉业.
基于重连机制的复杂网络鲁棒性分析
Robustness Analysis of Complex Network Based on Rewiring Mechanism
计算机科学, 2021, 48(7): 130-136. https://doi.org/10.11896/jsjkx.201000108
[9] 胡军, 王雨桐, 何欣蔚, 武晖栋, 李慧嘉.
基于复杂网络的全球航空网络结构分析与应用
Analysis and Application of Global Aviation Network Structure Based on Complex Network
计算机科学, 2021, 48(6A): 321-325. https://doi.org/10.11896/jsjkx.200900112
[10] 王学光, 张爱新, 窦炳琳.
复杂网络上的非线性负载容量模型
Non-linear Load Capacity Model of Complex Networks
计算机科学, 2021, 48(6): 282-287. https://doi.org/10.11896/jsjkx.200700040
[11] 马媛媛, 韩华, 瞿倩倩.
基于节点亲密度的重要性评估算法
Importance Evaluation Algorithm Based on Node Intimate Degree
计算机科学, 2021, 48(5): 140-146. https://doi.org/10.11896/jsjkx.200300184
[12] 殷子樵, 郭炳晖, 马双鸽, 米志龙, 孙怡帆, 郑志明.
群智体系网络结构的自治调节:从生物调控网络结构谈起
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
[13] 刘胜久, 李天瑞, 谢鹏, 刘佳.
带权图的多重分形度量
Measure for Multi-fractals of Weighted Graphs
计算机科学, 2021, 48(3): 136-143. https://doi.org/10.11896/jsjkx.200700159
[14] 龚追飞, 魏传佳.
基于改进AdaBoost算法的复杂网络链路预测
Link Prediction of Complex Network Based on Improved AdaBoost Algorithm
计算机科学, 2021, 48(3): 158-162. https://doi.org/10.11896/jsjkx.200600075
[15] 李鑫超, 李培峰, 朱巧明.
一种基于层级信息优化的有向网络表示学习方法
Directed Network Representation Method Based on Hierarchical Structure Information
计算机科学, 2021, 48(2): 100-104. https://doi.org/10.11896/jsjkx.191200033
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!