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

Multiple Order Local Information model for link prediction in complex networks

Author

Listed:
  • Yu, Jiating
  • Wu, Ling-Yun

Abstract

As a classical problem in the field of complex networks, link prediction has attracted much attention from researchers, which is of great significance to help us understand the evolution and dynamic development mechanisms of networks. Although various network type-specific algorithms have been proposed to tackle the link prediction problem, most of them suppose that the network structure is dominated by the Triadic Closure Principle. We still lack an adaptive and comprehensive understanding of network formation patterns for predicting potential links. In addition, it is valuable to investigate how network local information can be better utilized. To this end, we proposed a novel method named Link prediction using Multiple Order Local Information (MOLI) that exploits the local information from the neighbors of different distances, with parameter that can be a prior-driven based on prior knowledge, or data-driven by solving an optimization problem on observed networks. MOLI defined a local network diffusion process via random walks on the graph, resulting in better use of network information. We show that MOLI outperforms the other 12 widely used link prediction methods on 15 different types of simulated and real-world networks. We also conclude that there are different patterns of local information utilization for different networks, including social networks, communication networks, biological networks, etc. In particular, the classical common neighbor-based methods are not as adaptable to all social networks as it is perceived to be; instead, some of the social networks obey the Quadrilateral Closure Principle which preferentially connects paths of length three.

Suggested Citation

  • Yu, Jiating & Wu, Ling-Yun, 2022. "Multiple Order Local Information model for link prediction in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 600(C).
  • Handle: RePEc:eee:phsmap:v:600:y:2022:i:c:s0378437122003697
    DOI: 10.1016/j.physa.2022.127522
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437122003697
    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.2022.127522?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. Zhou, Tao & Lee, Yan-Li & Wang, Guannan, 2021. "Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 564(C).
    2. David Liben‐Nowell & Jon Kleinberg, 2007. "The link‐prediction problem for social networks," Journal of the American Society for Information Science and Technology, Association for Information Science & Technology, vol. 58(7), pages 1019-1031, May.
    3. Mengfei Cao & Hao Zhang & Jisoo Park & Noah M Daniels & Mark E Crovella & Lenore J Cowen & Benjamin Hescott, 2013. "Going the Distance for Protein Function Prediction: A New Distance Metric for Protein Interaction Networks," PLOS ONE, Public Library of Science, vol. 8(10), pages 1-12, October.
    4. 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.
    5. István A. Kovács & Katja Luck & Kerstin Spirohn & Yang Wang & Carl Pollis & Sadie Schlabach & Wenting Bian & Dae-Kyum Kim & Nishka Kishore & Tong Hao & Michael A. Calderwood & Marc Vidal & Albert-Lász, 2019. "Network-based prediction of protein interactions," Nature Communications, Nature, vol. 10(1), pages 1-8, December.
    6. Leo Katz, 1953. "A new status index derived from sociometric analysis," Psychometrika, Springer;The Psychometric Society, vol. 18(1), pages 39-43, March.
    7. 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.
    8. Pech, Ratha & Hao, Dong & Lee, Yan-Li & Yuan, Ye & Zhou, Tao, 2019. "Link prediction via linear optimization," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 528(C).
    9. 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).
    10. Pietro Panzarasa & Tore Opsahl & Kathleen M. Carley, 2009. "Patterns and dynamics of users' behavior and interaction: Network analysis of an online community," Journal of the American Society for Information Science and Technology, Association for Information Science & Technology, vol. 60(5), pages 911-932, May.
    11. Barabási, A.L & Jeong, H & Néda, Z & Ravasz, E & Schubert, A & Vicsek, T, 2002. "Evolution of the social network of scientific collaborations," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 311(3), pages 590-614.
    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. Yuliansyah, Herman & Othman, Zulaiha Ali & Bakar, Azuraliza Abu, 2023. "A new link prediction method to alleviate the cold-start problem based on extending common neighbor and degree centrality," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 616(C).
    2. Liu, Qian & Wang, Jian & Zhao, Zhidan & Zhao, Na, 2022. "Relatively important nodes mining algorithm based on community detection and biased random walk with restart," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 607(C).
    3. Yuping Jin & Yanbin Yang & Wei Liu, 2022. "Finding Global Liquefied Natural Gas Potential Trade Relations Based on Improved Link Prediction," Sustainability, MDPI, vol. 14(19), pages 1-22, September.

    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. Lee, Yan-Li & Zhou, Tao, 2021. "Collaborative filtering approach to link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 578(C).
    2. Zhou, Tao, 2023. "Discriminating abilities of threshold-free evaluation metrics in link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 615(C).
    3. Wahid-Ul-Ashraf, Akanda & Budka, Marcin & Musial, Katarzyna, 2019. "How to predict social relationships — Physics-inspired approach to link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 523(C), pages 1110-1129.
    4. Zhou, Tao & Lee, Yan-Li & Wang, Guannan, 2021. "Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 564(C).
    5. Lee, Yan-Li & Dong, Qiang & Zhou, Tao, 2021. "Link prediction via controlling the leading eigenvector," Applied Mathematics and Computation, Elsevier, vol. 411(C).
    6. 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.
    7. 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).
    8. Kai Yang & Yuan Liu & Zijuan Zhao & Xingxing Zhou & Peijin Ding, 2023. "Graph attention network via node similarity for link prediction," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 96(3), pages 1-10, March.
    9. Mungo, Luca & Lafond, François & Astudillo-Estévez, Pablo & Farmer, J. Doyne, 2023. "Reconstructing production networks using machine learning," Journal of Economic Dynamics and Control, Elsevier, vol. 148(C).
    10. 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).
    11. Najari, Shaghayegh & Salehi, Mostafa & Ranjbar, Vahid & Jalili, Mahdi, 2019. "Link prediction in multiplex networks based on interlayer similarity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 536(C).
    12. 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.
    13. 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).
    14. Seo, Wonchul & Afifuddin, Mokh, 2024. "Developing a supervised learning model for anticipating potential technology convergence between technology topics," Technological Forecasting and Social Change, Elsevier, vol. 203(C).
    15. 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).
    16. 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).
    17. Tofighy, Sajjad & Charkari, Nasrollah Moghadam & Ghaderi, Foad, 2022. "Link prediction in multiplex networks using intralayer probabilistic distance and interlayer co-evolving factors," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 606(C).
    18. Xu-Wen Wang & Lorenzo Madeddu & Kerstin Spirohn & Leonardo Martini & Adriano Fazzone & Luca Becchetti & Thomas P. Wytock & István A. Kovács & Olivér M. Balogh & Bettina Benczik & Mátyás Pétervári & Be, 2023. "Assessment of community efforts to advance network-based prediction of protein–protein interactions," Nature Communications, Nature, vol. 14(1), pages 1-14, December.
    19. Mueller, Falko, 2023. "Link and edge weight prediction in air transport networks — An RNN approach," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 613(C).
    20. Karimi, Fatemeh & Lotfi, Shahriar & Izadkhah, Habib, 2021. "Community-guided link prediction in multiplex networks," Journal of Informetrics, Elsevier, vol. 15(4).

    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:600:y:2022:i:c:s0378437122003697. 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.