IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0312863.html

Comparing random walks in graph embedding and link prediction

Author

Listed:
  • Adilson Vital Jr.
  • Filipi Nascimento Silva
  • Diego Raphael Amancio

Abstract

Random walks find extensive applications across various complex network domains, including embedding generation and link prediction. Despite the widespread utilization of random walks, the precise impact of distinct biases on embedding generation from sequence data and their subsequent effects on link prediction remain elusive. We conduct a comparative analysis of several random walk strategies, including the true self-avoiding random walk and the traditional random walk. We also analyze walks biased towards node degree and those with inverse node degree bias. Diverse adaptations of the node2vec algorithm to induce distinct exploratory behaviors were also investigated. Our empirical findings demonstrate that despite the varied behaviors inherent in these embeddings, only slight performance differences manifest in the context of link prediction. This implies the resilient recovery of network structure, regardless of the specific walk heuristic employed to traverse the network. Consequently, the results suggest that data generated from sequences governed by unknown mechanisms can be successfully reconstructed.

Suggested Citation

  • Adilson Vital Jr. & Filipi Nascimento Silva & Diego Raphael Amancio, 2024. "Comparing random walks in graph embedding and link prediction," PLOS ONE, Public Library of Science, vol. 19(11), pages 1-22, November.
    • Handle: RePEc:plo:pone00:0312863
    DOI: 10.1371/journal.pone.0312863
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0312863
    Download Restriction: no
    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0312863&type=printable
    Download Restriction: no
    File URL: https://libkey.io/10.1371/journal.pone.0312863?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
    ---><---

    References listed on IDEAS

    as
    1. Kibae Kim & Jörn Altmann, 2015. "Effect of Homophily on Network Formation," TEMEP Discussion Papers 2015121, Seoul National University; Technology Management, Economics, and Policy Program (TEMEP), revised Mar 2017.
    2. 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.
    3. Kabir, KM Ariful & Kuga, Kazuki & Tanimoto, Jun, 2020. "The impact of information spreading on epidemic vaccination game dynamics in a heterogeneous complex network- A theoretical approach," Chaos, Solitons & Fractals, Elsevier, vol. 132(C).
    4. Pierre Barthelemy & Jacopo Bertolotti & Diederik S. Wiersma, 2008. "A Lévy flight for light," Nature, Nature, vol. 453(7194), pages 495-498, May.
    Full references (including those not matched with items on IDEAS)

    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. Chen, Ling-Jiao & Zhang, Zi-Ke & Liu, Jin-Hu & Gao, Jian & Zhou, Tao, 2017. "A vertex similarity index for better personalized recommendation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 466(C), pages 607-615.
    2. Dong-Rui Chen & Chuang Liu & Yi-Cheng Zhang & Zi-Ke Zhang, 2019. "Predicting Financial Extremes Based on Weighted Visual Graph of Major Stock Indices," Complexity, Hindawi, vol. 2019, pages 1-17, October.
    3. Wei, Daijun & Deng, Xinyang & Zhang, Xiaoge & Deng, Yong & Mahadevan, Sankaran, 2013. "Identifying influential nodes in weighted networks based on evidence theory," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(10), pages 2564-2575.
    4. Li, Xiang, 2025. "Higher-order dependencies for multi-step link prediction," Chaos, Solitons & Fractals, Elsevier, vol. 200(P1).
    5. Sakthivel, Rathinasamy & Suveetha, V.T. & Nithya, Venkatesh & Sakthivel, Ramalingam, 2020. "Finite-time fault detection filter design for complex systems with multiple stochastic communication and distributed delays," Chaos, Solitons & Fractals, Elsevier, vol. 136(C).
    6. Weihua Lei & Luiz G. A. Alves & Luís A. Nunes Amaral, 2022. "Forecasting the evolution of fast-changing transportation networks using machine learning," Nature Communications, Nature, vol. 13(1), pages 1-12, December.
    7. Leto Peel & Tiago P. Peixoto & Manlio De Domenico, 2022. "Statistical inference links data and theory in network science," Nature Communications, Nature, vol. 13(1), pages 1-15, December.
    8. Rafiee, Samira & Salavati, Chiman & Abdollahpouri, Alireza, 2020. "CNDP: Link prediction based on common neighbors degree penalization," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 539(C).
    9. Linyuan Lü & Yi-Cheng Zhang & Chi Ho Yeung & Tao Zhou, 2011. "Leaders in Social Networks, the Delicious Case," PLOS ONE, Public Library of Science, vol. 6(6), pages 1-9, June.
    10. Yin, Liang & Shi, Li-Chen & Zhao, Jun-Yan & Du, Song-Yang & Xie, Wen-Bo & Yuan, Fei & Chen, Duan-Bing, 2018. "Heterogeneous information network model for equipment-standard system," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 490(C), pages 935-943.
    11. 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.
    12. 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).
    13. Alireza Abbasi & Mahdi Jalili & Abolghasem Sadeghi-Niaraki, 2018. "Influence of network-based structural and power diversity on research performance," Scientometrics, Springer;Akadémiai Kiadó, vol. 117(1), pages 579-590, October.
    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. Moradabadi, Behnaz & Meybodi, Mohammad Reza, 2016. "Link prediction based on temporal similarity metrics using continuous action set learning automata," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 460(C), pages 361-373.
    16. Jiang, Yawen & Jia, Caiyan & Yu, Jian, 2013. "An efficient community detection method based on rank centrality," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(9), pages 2182-2194.
    17. Park, Mingyu & Geum, Youngjung, 2022. "Two-stage technology opportunity discovery for firm-level decision making: GCN-based link-prediction approach," Technological Forecasting and Social Change, Elsevier, vol. 183(C).
    18. Yichi Zhang & Zhiliang Dong & Sen Liu & Peixiang Jiang & Cuizhi Zhang & Chao Ding, 2021. "Forecast of International Trade of Lithium Carbonate Products in Importing Countries and Small-Scale Exporting Countries," Sustainability, MDPI, vol. 13(3), pages 1-23, January.
    19. Yao, Can-Zhong & Lin, Ji-Nan & Zheng, Xu-Zhou & Liu, Xiao-Feng, 2015. "The study of RMB exchange rate complex networks based on fluctuation mode," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 436(C), pages 359-376.
    20. Wang, Luyao & Chen, Libin & Yang, Zhiwei & Yang, Kewei, 2026. "Research on network robustness analysis method of combat system-of-systems considering collaborative reconfiguration," Reliability Engineering and System Safety, Elsevier, vol. 265(PB).

    More about this item

    Statistics

    Access and download statistics

    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:plo:pone00:0312863. 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: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    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.