IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0213857.html
   My bibliography  Save this article

Supervised and extended restart in random walks for ranking and link prediction in networks

Author

Listed:
  • Woojeong Jin
  • Jinhong Jung
  • U Kang

Abstract

Given a real-world graph, how can we measure relevance scores for ranking and link prediction? Random walk with restart (RWR) provides an excellent measure for this and has been applied to various applications such as friend recommendation, community detection, anomaly detection, etc. However, RWR suffers from two problems: 1) using the same restart probability for all the nodes limits the expressiveness of random walk, and 2) the restart probability needs to be manually chosen for each application without theoretical justification. We have two main contributions in this paper. First, we propose Random Walk with Extended Restart (RWER), a random walk based measure which improves the expressiveness of random walks by using a distinct restart probability for each node. The improved expressiveness leads to superior accuracy for ranking and link prediction. Second, we propose SuRe (Supervised Restart for RWER), an algorithm for learning the restart probabilities of RWER from a given graph. SuRe eliminates the need to heuristically and manually select the restart parameter for RWER. Extensive experiments show that our proposed method provides the best performance for ranking and link prediction tasks.

Suggested Citation

  • Woojeong Jin & Jinhong Jung & U Kang, 2019. "Supervised and extended restart in random walks for ranking and link prediction in networks," PLOS ONE, Public Library of Science, vol. 14(3), pages 1-23, March.
  • Handle: RePEc:plo:pone00:0213857
    DOI: 10.1371/journal.pone.0213857
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0213857
    Download Restriction: no

    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0213857&type=printable
    Download Restriction: no

    File URL: https://libkey.io/10.1371/journal.pone.0213857?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
    ---><---

    Citations

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


    Cited by:

    1. 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).
    2. Davide Buffelli & Fabio Vandin, 2022. "The Impact of Global Structural Information in Graph Neural Networks Applications," Data, MDPI, vol. 7(1), pages 1-20, January.
    3. Zhou, Yinzuo & Wu, Chencheng & Tan, Lulu, 2021. "Biased random walk with restart for link prediction with graph embedding method," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 570(C).
    4. Liu, Yanyan & Li, Keping & Yan, Dongyang, 2024. "Quantification analysis of potential risk in railway accidents: A new random walk based approach," Reliability Engineering and System Safety, Elsevier, vol. 242(C).
    5. Chao Li & Qiming Yang & Bowen Pang & Tiance Chen & Qian Cheng & Jiaomin Liu, 2021. "A Mixed Strategy of Higher-Order Structure for Link Prediction Problem on Bipartite Graphs," Mathematics, MDPI, vol. 9(24), pages 1-13, December.

    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:0213857. 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.

    We have no bibliographic references for this item. You can help adding them by using 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.