  Graphs are fundamental data structures and have been employed for centuries
to model real-world systems and phenomena. Random walk with restart (RWR)
provides a good proximity score between two nodes in a graph, and it has been
successfully used in many applications such as automatic image captioning,
recommender systems, and link prediction. The goal of this work is to find
nodes that have top-k highest proximities for a given node. Previous approaches
to this problem find nodes efficiently at the expense of exactness. The main
motivation of this paper is to answer, in the affirmative, the question, `Is it
possible to improve the search time without sacrificing the exactness?'. Our
solution, {it K-dash}, is based on two ideas: (1) It computes the proximity of
a selected node efficiently by sparse matrices, and (2) It skips unnecessary
proximity computations when searching for the top-k nodes. Theoretical analyses
show that K-dash guarantees result exactness. We perform comprehensive
experiments to verify the efficiency of K-dash. The results show that K-dash
can find top-k nodes significantly faster than the previous approaches while it
guarantees exactness.
