{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T21:15:33Z","timestamp":1791407733184,"version":"4.3.3"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,5,11]],"date-time":"2016-05-11T00:00:00Z","timestamp":1462924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NRF","award":["NRF-2013R1A1A3005259"],"award-info":[{"award-number":["NRF-2013R1A1A3005259"]}]},{"name":"MSIP\/IITP","award":["R0101-15-0176"],"award-info":[{"award-number":["R0101-15-0176"]}]},{"name":"MSIP","award":["R0190-15-2012"],"award-info":[{"award-number":["R0190-15-2012"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2016,6,30]]},"abstract":"<jats:p>Given a large graph, how can we calculate the relevance between nodes fast and accurately? Random walk with restart (RWR) provides a good measure for this purpose and has been applied to diverse data mining applications including ranking, community detection, link prediction, and anomaly detection. Since calculating RWR from scratch takes a long time, various preprocessing methods, most of which are related to inverting adjacency matrices, have been proposed to speed up the calculation. However, these methods do not scale to large graphs because they usually produce large dense matrices that do not fit into memory. In addition, the existing methods are inappropriate when graphs dynamically change because the expensive preprocessing task needs to be computed repeatedly.<\/jats:p>\n          <jats:p>\n            In this article, we propose B\n            <jats:sc>ear<\/jats:sc>\n            , a fast, scalable, and accurate method for computing RWR on large graphs. B\n            <jats:sc>ear<\/jats:sc>\n            has two versions: a preprocessing method B\n            <jats:sc>ear<\/jats:sc>\n            S for static graphs and an incremental update method B\n            <jats:sc>ear<\/jats:sc>\n            D for dynamic graphs. B\n            <jats:sc>ear<\/jats:sc>\n            S consists of the preprocessing step and the query step. In the preprocessing step, B\n            <jats:sc>ear<\/jats:sc>\n            S reorders the adjacency matrix of a given graph so that it contains a large and easy-to-invert submatrix, and precomputes several matrices including the Schur complement of the submatrix. In the query step, B\n            <jats:sc>ear<\/jats:sc>\n            S quickly computes the RWR scores for a given query node using a block elimination approach with the matrices computed in the preprocessing step. For dynamic graphs, B\n            <jats:sc>ear<\/jats:sc>\n            D efficiently updates the changed parts in the preprocessed matrices of B\n            <jats:sc>ear<\/jats:sc>\n            S based on the observation that only small parts of the preprocessed matrices change when few edges are inserted or deleted. Through extensive experiments, we show that B\n            <jats:sc>ear<\/jats:sc>\n            S significantly outperforms other state-of-the-art methods in terms of preprocessing and query speed, space efficiency, and accuracy. We also show that B\n            <jats:sc>ear<\/jats:sc>\n            D quickly updates the preprocessed matrices and immediately computes queries when the graph changes.\n          <\/jats:p>","DOI":"10.1145\/2901736","type":"journal-article","created":{"date-parts":[[2016,5,13]],"date-time":"2016-05-13T14:30:58Z","timestamp":1463149858000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["Random Walk with Restart on Large Graphs Using Block Elimination"],"prefix":"10.1145","volume":"41","author":[{"given":"Jinhong","family":"Jung","sequence":"first","affiliation":[{"name":"Seoul National University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kijung","family":"Shin","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lee","family":"Sael","sequence":"additional","affiliation":[{"name":"State University of New York (SUNY) Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"U","family":"Kang","sequence":"additional","affiliation":[{"name":"Seoul National University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,5,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-8733(03)00009-1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Reka Albert Hawoong Jeong and Albert-Laszlo Barabasi. 2000. Error and attack tolerance of complex networks. Nature 406 6794 378--382.  Reka Albert Hawoong Jeong and Albert-Laszlo Barabasi. 2000. Error and attack tolerance of complex networks. Nature 406 6794 378--382.","DOI":"10.1038\/35019019"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.44"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2124295.2124330"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453903"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1935826.1935914"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/1929861.1929864"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB\u201904)","author":"Balmin Andrey","year":"2004"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","volume-title":"Linear Algebra and Matrix Analysis for Statistics","author":"Banerjee Sudipto","DOI":"10.1201\/b17040"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505522"},{"key":"e_1_2_1_11_1","volume-title":"Convex Optimization","author":"Boyd Stephen"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014064"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-010-0204-8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557049"},{"key":"e_1_2_1_16_1","volume-title":"Random Walks and Electric Networks","author":"Doyle Peter G."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140441"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339538"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129128"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339628"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367738"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0895-7177(97)00050-2"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1027527.1027531"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775126"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.26"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the SIAM International Conference on Data Mining (SDM\u201912)","author":"Kang U."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646196"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2034117.2034134"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972832.18"},{"key":"e_1_2_1_30_1","volume-title":"Meyer","author":"Langville Amy N.","year":"2011"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.v58:7"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2320716"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646185"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623745"},{"key":"e_1_2_1_36_1","first-page":"849","article-title":"On spectral clustering: Analysis and an algorithm","volume":"14","author":"Ng Andrew Y.","year":"2002","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014135"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/1032080"},{"key":"e_1_2_1_40_1","volume-title":"Numerical Recipes","author":"Press William H.","edition":"3"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI\u201907)","author":"Sarkar Purnamrita"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835871"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723716"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2005.103"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150448"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281271"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-007-0094-2"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505535"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610500"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398450"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the International Conference on Machine Learning (ICML\u201913)","author":"Zhu Zeyuan A.","year":"2013"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2901736","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2901736","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:31Z","timestamp":1750273531000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2901736"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,11]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,6,30]]}},"alternative-id":["10.1145\/2901736"],"URL":"https:\/\/doi.org\/10.1145\/2901736","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,11]]},"assertion":[{"value":"2015-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}