Computer Science ›› 2022, Vol. 49 ›› Issue (2): 216-222.doi: 10.11896/jsjkx.210100107

• Database & Big Data & Data Science • Previous Articles     Next Articles

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

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

CLC Number: 

  • 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] SONG Jie, LIANG Mei-yu, XUE Zhe, DU Jun-ping, KOU Fei-fei. Scientific Paper Heterogeneous Graph Node Representation Learning Method Based onUnsupervised Clustering Level [J]. Computer Science, 2022, 49(9): 64-69.
[2] HUANG Li, ZHU Yan, LI Chun-ping. Author’s Academic Behavior Prediction Based on Heterogeneous Network Representation Learning [J]. Computer Science, 2022, 49(9): 76-82.
[3] ZHENG Wen-ping, LIU Mei-lin, YANG Gui. Community Detection Algorithm Based on Node Stability and Neighbor Similarity [J]. Computer Science, 2022, 49(9): 83-91.
[4] HE Xi, HE Ke-tai, WANG Jin-shan, LIN Shen-wen, YANG Jing-lin, FENG Yu-chao. Analysis of Bitcoin Entity Transaction Patterns [J]. Computer Science, 2022, 49(6A): 502-507.
[5] YANG Bo, LI Yuan-biao. Complex Network Analysis on Curriculum System of Data Science and Big Data Technology [J]. Computer Science, 2022, 49(6A): 680-685.
[6] WANG Ben-yu, GU Yi-jun, PENG Shu-fan, ZHENG Di-wen. Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning [J]. Computer Science, 2022, 49(5): 170-178.
[7] LI Yong, WU Jing-peng, ZHANG Zhong-ying, ZHANG Qiang. Link Prediction for Node Featureless Networks Based on Faster Attention Mechanism [J]. Computer Science, 2022, 49(4): 43-48.
[8] CHEN Shi-cong, YUAN De-yu, HUANG Shu-hua, YANG Ming. Node Label Classification Algorithm Based on Structural Depth Network Embedding Model [J]. Computer Science, 2022, 49(3): 105-112.
[9] LI Jia-wen, GUO Bing-hui, YANG Xiao-bo, ZHENG Zhi-ming. Disease Genes Recognition Based on Information Propagation [J]. Computer Science, 2022, 49(1): 264-270.
[10] MU Jun-fang, ZHENG Wen-ping, WANG Jie, LIANG Ji-ye. Robustness Analysis of Complex Network Based on Rewiring Mechanism [J]. Computer Science, 2021, 48(7): 130-136.
[11] HU Jun, WANG Yu-tong, HE Xin-wei, WU Hui-dong, LI Hui-jia. Analysis and Application of Global Aviation Network Structure Based on Complex Network [J]. Computer Science, 2021, 48(6A): 321-325.
[12] WANG Xue-guang, ZHANG Ai-xin, DOU Bing-lin. Non-linear Load Capacity Model of Complex Networks [J]. Computer Science, 2021, 48(6): 282-287.
[13] HU Xin-tong, SHA Chao-feng, LIU Yan-jun. Post-processing Network Embedding Algorithm with Random Projection and Principal Component Analysis [J]. Computer Science, 2021, 48(5): 124-129.
[14] MA Yuan-yuan, HAN Hua, QU Qian-qian. Importance Evaluation Algorithm Based on Node Intimate Degree [J]. Computer Science, 2021, 48(5): 140-146.
[15] YIN Zi-qiao, GUO Bing-hui, MA Shuang-ge, MI Zhi-long, SUN Yi-fan, ZHENG Zhi-ming. Autonomous Structural Adjustment of Crowd Intelligence Network: Begin from Structure of Biological Regulatory Network [J]. Computer Science, 2021, 48(5): 184-189.
Full text



No Suggested Reading articles found!