{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T21:15:35Z","timestamp":1791407735153,"version":"4.3.3"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>\n            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,\n            <jats:italic>K-dash<\/jats:italic>\n            , 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.\n          <\/jats:p>","DOI":"10.14778\/2140436.2140441","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"442-453","source":"Crossref","is-referenced-by-count":76,"title":["Fast and exact top-k search for random walk with restart"],"prefix":"10.14778","volume":"5","author":[{"given":"Yasuhiro","family":"Fujiwara","sequence":"first","affiliation":[{"name":"NTT Cyber Space Labs, and The University of Tokyo"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Makoto","family":"Nakatsuji","sequence":"additional","affiliation":[{"name":"NTT Cyber Space Labs"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Makoto","family":"Onizuka","sequence":"additional","affiliation":[{"name":"NTT Cyber Space Labs"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Masaru","family":"Kitsuregawa","sequence":"additional","affiliation":[{"name":"The University of Tokyo"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453903"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2022148.2022153"},{"issue":"10","key":"e_1_2_1_3_1","volume":"2008","author":"Blondel V. D.","year":"2008","unstructured":"V. D. Blondel , J.-L. Guillaume , R. Lambiotte , and E. Lefebvre . Fast Unfolding of Communities in Large Networks. J. Statistical Mechanics: Theory and Experiment , 2008 ( 10 ), 2008 . V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre. Fast Unfolding of Communities in Large Networks. J. Statistical Mechanics: Theory and Experiment, 2008(10), 2008.","journal-title":"Fast Unfolding of Communities in Large Networks. J. Statistical Mechanics: Theory and Experiment"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0177-1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497500"},{"key":"e_1_2_1_6_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2009","unstructured":"T. H. Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein . Introduction to Algorithms . The MIT Press , 2009 . T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 2009."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367738"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1027527.1027531"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1997.1404"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989418"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1571941.1571977"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956972"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453904"},{"key":"e_1_2_1_14_1","volume-title":"The Structure And Dynamics of Networks","author":"Newman M.","year":"2006","unstructured":"M. Newman , A.-L. Barabasi , and D. J. Watts . The Structure And Dynamics of Networks . Princeton University Press , 2006 . M. Newman, A.-L. Barabasi, and D. J. Watts. The Structure And Dynamics of Networks. Princeton University Press, 2006."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014135"},{"key":"e_1_2_1_16_1","volume-title":"Numerical Recipes","author":"Press W. H.","year":"2007","unstructured":"W. H. Press , S. A. Teukolsky , W. T. Vetterling , and B. P. Flannery . Numerical Recipes 3 rd Edition. Cambridge University Press , 2007 . W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery. Numerical Recipes 3rd Edition. Cambridge University Press, 2007.","edition":"3"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1718487.1718521"},{"key":"e_1_2_1_18_1","volume-title":"Introduction to Linear Algebra","author":"Strang G.","year":"2009","unstructured":"G. Strang . Introduction to Linear Algebra . Wellesley Cambridge Press , 2009 . G. Strang. Introduction to Linear Algebra. Wellesley Cambridge Press, 2009."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2005.103"},{"key":"e_1_2_1_20_1","volume-title":"PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks. PVLDB, 4(1)","author":"Sun Y.","year":"2011","unstructured":"Y. Sun , J. Han , X. Yan , P. Yu , and T. Wu . PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks. PVLDB, 4(1) , 2011 . Y. Sun, J. Han, X. Yan, P. Yu, and T. Wu. PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks. PVLDB, 4(1), 2011."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150448"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.70"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0602010"},{"key":"e_1_2_1_24_1","first-page":"938","volume-title":"VLDB","author":"Zhao P.","year":"2007","unstructured":"P. Zhao , J. X. Yu , and P. S. Yu . Graph Indexing: Tree + Delta &gt;= Graph . In VLDB , pages 938 -- 949 , 2007 . P. Zhao, J. X. Yu, and P. S. Yu. Graph Indexing: Tree + Delta &gt;= Graph. In VLDB, pages 938--949, 2007."},{"issue":"1","key":"e_1_2_1_25_1","first-page":"718","article-title":"Graph Clustering Based on Structural\/Attribute Similarities","volume":"2","author":"Zhou Y.","year":"2009","unstructured":"Y. Zhou , H. Cheng , and J. X. Yu . Graph Clustering Based on Structural\/Attribute Similarities . PVLDB , 2 ( 1 ): 718 -- 729 , 2009 . Y. Zhou, H. Cheng, and J. X. Yu. Graph Clustering Based on Structural\/Attribute Similarities. PVLDB, 2(1):718--729, 2009.","journal-title":"PVLDB"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2140436.2140441","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:40:33Z","timestamp":1672220433000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2140436.2140441"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.14778\/2140436.2140441"],"URL":"https:\/\/doi.org\/10.14778\/2140436.2140441","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}