Cargando…

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

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

Descripción completa

Detalles Bibliográficos
Autores principales: Jin, Woojeong, Jung, Jinhong, Kang, U.
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Public Library of Science 2019
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6426185/
https://www.ncbi.nlm.nih.gov/pubmed/30893375
http://dx.doi.org/10.1371/journal.pone.0213857
_version_ 1783404963096952832
author Jin, Woojeong
Jung, Jinhong
Kang, U.
author_facet Jin, Woojeong
Jung, Jinhong
Kang, U.
author_sort Jin, Woojeong
collection PubMed
description 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.
format Online
Article
Text
id pubmed-6426185
institution National Center for Biotechnology Information
language English
publishDate 2019
publisher Public Library of Science
record_format MEDLINE/PubMed
spelling pubmed-64261852019-04-02 Supervised and extended restart in random walks for ranking and link prediction in networks Jin, Woojeong Jung, Jinhong Kang, U. PLoS One Research Article 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. Public Library of Science 2019-03-20 /pmc/articles/PMC6426185/ /pubmed/30893375 http://dx.doi.org/10.1371/journal.pone.0213857 Text en © 2019 Jin et al http://creativecommons.org/licenses/by/4.0/ This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) , which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
spellingShingle Research Article
Jin, Woojeong
Jung, Jinhong
Kang, U.
Supervised and extended restart in random walks for ranking and link prediction in networks
title Supervised and extended restart in random walks for ranking and link prediction in networks
title_full Supervised and extended restart in random walks for ranking and link prediction in networks
title_fullStr Supervised and extended restart in random walks for ranking and link prediction in networks
title_full_unstemmed Supervised and extended restart in random walks for ranking and link prediction in networks
title_short Supervised and extended restart in random walks for ranking and link prediction in networks
title_sort supervised and extended restart in random walks for ranking and link prediction in networks
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6426185/
https://www.ncbi.nlm.nih.gov/pubmed/30893375
http://dx.doi.org/10.1371/journal.pone.0213857
work_keys_str_mv AT jinwoojeong supervisedandextendedrestartinrandomwalksforrankingandlinkpredictioninnetworks
AT jungjinhong supervisedandextendedrestartinrandomwalksforrankingandlinkpredictioninnetworks
AT kangu supervisedandextendedrestartinrandomwalksforrankingandlinkpredictioninnetworks