IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v510y2018icp52-67.html
   My bibliography  Save this article

Link prediction in complex networks based on the interactions among paths

Author

Listed:
  • Yao, Yabing
  • Zhang, Ruisheng
  • Yang, Fan
  • Tang, Jianxin
  • Yuan, Yongna
  • Hu, Rongjing

Abstract

Link prediction in incomplete complex networks is an important issue in network science. Recently, various structure-based similarity methods have been proposed. However, most path-dependent methods merely pay attention to the contributions of paths with specific length, which neglects the interactions of paths with different length for performance improvement. Motivated by the resource-traffic flow mechanism on networks, we measure the interaction relationship of paths with a resource receiving process. In this process, each node takes certain initial resources quantified by its H-index, and then the intermediate nodes on paths can receive resources from their neighbours. Based on this process, a local path-based link predictor which emphasizes the effect of the Resources from Short Paths (RSP) is proposed. Experiments on twelve real-world networks demonstrate that the RSP index has better performance than other nine structure-based similarity methods.

Suggested Citation

  • Yao, Yabing & Zhang, Ruisheng & Yang, Fan & Tang, Jianxin & Yuan, Yongna & Hu, Rongjing, 2018. "Link prediction in complex networks based on the interactions among paths," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 510(C), pages 52-67.
  • Handle: RePEc:eee:phsmap:v:510:y:2018:i:c:p:52-67
    DOI: 10.1016/j.physa.2018.06.051
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437118307751
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

    File URL: https://libkey.io/10.1016/j.physa.2018.06.051?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Xu, Zhongqi & Pu, Cunlai & Yang, Jian, 2016. "Link prediction based on path entropy," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 456(C), pages 294-301.
    2. Zhu, Xuzhen & Tian, Hui & Cai, Shimin, 2014. "Predicting missing links via effective paths," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 413(C), pages 515-522.
    3. Wu, Zhihao & Lin, Youfang & Zhao, Yiji & Yan, Hongyan, 2018. "Improving local clustering based top-L link prediction methods via asymmetric link clustering information," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 492(C), pages 1859-1874.
    4. Zhou, Wen & Jia, Yifan, 2017. "Predicting links based on knowledge dissemination in complex network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 471(C), pages 561-568.
    5. Aaron Clauset & Cristopher Moore & M. E. J. Newman, 2008. "Hierarchical structure and the prediction of missing links in networks," Nature, Nature, vol. 453(7191), pages 98-101, May.
    6. Lü, Linyuan & Zhou, Tao, 2011. "Link prediction in complex networks: A survey," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(6), pages 1150-1170.
    7. Fei Tan & Yongxiang Xia & Boyao Zhu, 2014. "Link Prediction in Complex Networks: A Mutual Information Perspective," PLOS ONE, Public Library of Science, vol. 9(9), pages 1-8, September.
    8. Aghabozorgi, Farshad & Khayyambashi, Mohammad Reza, 2018. "A new similarity measure for link prediction based on local structures in social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 501(C), pages 12-23.
    9. Zhen Liu & Jia-Lin He & Komal Kapoor & Jaideep Srivastava, 2013. "Correlations between Community Structure and Link Formation in Complex Networks," PLOS ONE, Public Library of Science, vol. 8(9), pages 1-10, September.
    10. Ding, Jingyi & Jiao, Licheng & Wu, Jianshe & Hou, Yunting & Qi, Yutao, 2015. "Prediction of missing links based on multi-resolution community division," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 417(C), pages 76-85.
    11. Pei, Panpan & Liu, Bo & Jiao, Licheng, 2017. "Link prediction in complex networks based on an information allocation index," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 470(C), pages 1-11.
    12. Ma, Xiaoke & Sun, Penggang & Wang, Yu, 2018. "Graph regularized nonnegative matrix factorization for temporal link prediction in dynamic networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 496(C), pages 121-136.
    13. Wang, Zuxi & Li, Qingguang & Jin, Fengdong & Xiong, Wei & Wu, Yao, 2016. "Hyperbolic mapping of complex networks based on community information," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 455(C), pages 104-119.
    14. Leo Katz, 1953. "A new status index derived from sociometric analysis," Psychometrika, Springer;The Psychometric Society, vol. 18(1), pages 39-43, March.
    15. Tao Zhou & Linyuan Lü & Yi-Cheng Zhang, 2009. "Predicting missing links via local information," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 71(4), pages 623-630, October.
    16. Wu, Zhihao & Lin, Youfang & Wang, Jing & Gregory, Steve, 2016. "Link prediction with node clustering coefficient," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 452(C), pages 1-8.
    17. Wang, Zuxi & Wu, Yao & Li, Qingguang & Jin, Fengdong & Xiong, Wei, 2016. "Link prediction based on hyperbolic mapping with community structure for complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 450(C), pages 609-623.
    18. Liu, Shuxin & Ji, Xinsheng & Liu, Caixia & Bai, Yi, 2017. "Extended resource allocation index for link prediction of complex network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 479(C), pages 174-183.
    19. Linyuan Lü & Tao Zhou & Qian-Ming Zhang & H. Eugene Stanley, 2016. "The H-index of a network node and its relation to degree and coreness," Nature Communications, Nature, vol. 7(1), pages 1-7, April.
    20. Yang, Yujie & Zhang, Jianhua & Zhu, Xuzhen & Tian, Lei, 2018. "Link prediction via significant influence," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 492(C), pages 1523-1530.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Assouli, Nora & Benahmed, Khelifa & Gasbaoui, Brahim, 2021. "How to predict crime — informatics-inspired approach from link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 570(C).
    2. Shugang Li & Ziming Wang & Beiyan Zhang & Boyi Zhu & Zhifang Wen & Zhaoxu Yu, 2022. "The Research of “Products Rapidly Attracting Users” Based on the Fully Integrated Link Prediction Algorithm," Mathematics, MDPI, vol. 10(14), pages 1-19, July.
    3. Kart, Ozge & Ulucay, Oguzhan & Bingol, Berkay & Isik, Zerrin, 2020. "A machine learning-based recommendation model for bipartite networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 553(C).
    4. Chen Yang & Tingting Liu & Xiaohong Chen & Yiyang Bian & Yuewen Liu, 2020. "HNRWalker: recommending academic collaborators with dynamic transition probabilities in heterogeneous networks," Scientometrics, Springer;Akadémiai Kiadó, vol. 123(1), pages 429-449, April.
    5. Chi, Kuo & Qu, Hui & Yin, Guisheng, 2022. "Link prediction for existing links in dynamic networks based on the attraction force," Chaos, Solitons & Fractals, Elsevier, vol. 159(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Chi, Kuo & Qu, Hui & Yin, Guisheng, 2022. "Link prediction for existing links in dynamic networks based on the attraction force," Chaos, Solitons & Fractals, Elsevier, vol. 159(C).
    2. Kumar, Ajay & Singh, Shashank Sheshar & Singh, Kuldeep & Biswas, Bhaskar, 2020. "Link prediction techniques, applications, and performance: A survey," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 553(C).
    3. Yin, Likang & Zheng, Haoyang & Bian, Tian & Deng, Yong, 2017. "An evidential link prediction method and link predictability based on Shannon entropy," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 482(C), pages 699-712.
    4. Wu, Jiehua & Shen, Jing & Zhou, Bei & Zhang, Xiayan & Huang, Bohuai, 2019. "General link prediction with influential node identification," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 523(C), pages 996-1007.
    5. Wang, Jun & Zhang, Qian-Ming & Zhou, Tao, 2019. "Tag-aware link prediction algorithm in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 523(C), pages 105-111.
    6. Wang, Zuxi & Wu, Yao & Li, Qingguang & Jin, Fengdong & Xiong, Wei, 2016. "Link prediction based on hyperbolic mapping with community structure for complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 450(C), pages 609-623.
    7. Liu, Shuxin & Ji, Xinsheng & Liu, Caixia & Bai, Yi, 2017. "Extended resource allocation index for link prediction of complex network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 479(C), pages 174-183.
    8. Pei, Panpan & Liu, Bo & Jiao, Licheng, 2017. "Link prediction in complex networks based on an information allocation index," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 470(C), pages 1-11.
    9. Park, Ji Hwan & Chang, Woojin & Song, Jae Wook, 2020. "Link prediction in the Granger causality network of the global currency market," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 553(C).
    10. Mishra, Shivansh & Singh, Shashank Sheshar & Kumar, Ajay & Biswas, Bhaskar, 2022. "ELP: Link prediction in social networks based on ego network perspective," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 605(C).
    11. Assouli, Nora & Benahmed, Khelifa & Gasbaoui, Brahim, 2021. "How to predict crime — informatics-inspired approach from link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 570(C).
    12. Liu, Yangyang & Zhao, Chengli & Wang, Xiaojie & Huang, Qiangjuan & Zhang, Xue & Yi, Dongyun, 2016. "The degree-related clustering coefficient and its application to link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 454(C), pages 24-33.
    13. Zhang, Xuejun & Pang, Wenbo & Xia, Yongxiang, 2018. "An intermediary probability model for link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 512(C), pages 902-912.
    14. Lee, Yan-Li & Zhou, Tao, 2021. "Collaborative filtering approach to link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 578(C).
    15. Charikhi, Mourad, 2024. "Association of the PageRank algorithm with similarity-based methods for link prediction in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 637(C).
    16. Bütün, Ertan & Kaya, Mehmet, 2019. "A pattern based supervised link prediction in directed complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 525(C), pages 1136-1145.
    17. Sherkat, Ehsan & Rahgozar, Maseud & Asadpour, Masoud, 2015. "Structural link prediction based on ant colony approach in social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 419(C), pages 80-94.
    18. Aziz, Furqan & Gul, Haji & Muhammad, Ishtiaq & Uddin, Irfan, 2020. "Link prediction using node information on local paths," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 557(C).
    19. Chunning Wang & Fengqin Tang & Xuejing Zhao, 2023. "LPGRI: A Global Relevance-Based Link Prediction Approach for Multiplex Networks," Mathematics, MDPI, vol. 11(14), pages 1-15, July.
    20. Chen, Guangfu & Xu, Chen & Wang, Jingyi & Feng, Jianwen & Feng, Jiqiang, 2020. "Robust non-negative matrix factorization for link prediction in complex networks using manifold regularization and sparse learning," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 539(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:phsmap:v:510:y:2018:i:c:p:52-67. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.