{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:53:00Z","timestamp":1773481980739,"version":"3.50.1"},"publisher-location":"New York, New York, USA","reference-count":29,"publisher":"ACM Press","license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Information & commu- nications Technology Promotion(IITP) of the Korea government(MSIT)","award":["No.R0190-15-2012"],"award-info":[{"award-number":["No.R0190-15-2012"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1145\/3178876.3186107","type":"proceedings-article","created":{"date-parts":[[2018,4,13]],"date-time":"2018-04-13T15:53:48Z","timestamp":1523634828000},"page":"409-418","source":"Crossref","is-referenced-by-count":26,"title":["Fast and Accurate Random Walk with Restart on Dynamic Graphs with Guarantees"],"prefix":"10.1145","author":[{"given":"Minji","family":"Yoon","sequence":"first","affiliation":[{"name":"Seoul National University, Seoul, Rebublic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Woojeong","family":"Jin","sequence":"additional","affiliation":[{"name":"Seoul National University, Seoul, Rebublic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"U.","family":"Kang","sequence":"additional","affiliation":[{"name":"Seoul National University, Seoul, Rebublic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","reference":[{"key":"key-10.1145\/3178876.3186107-1","doi-asserted-by":"crossref","unstructured":"Reid Andersen, Fan Chung, and Kevin Lang. 2006. Local graph partitioning using pagerank vectors. In Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium on. IEEE, 475--486.","DOI":"10.1109\/FOCS.2006.44"},{"key":"key-10.1145\/3178876.3186107-2","unstructured":"I Antonellis, H Garcia-Molina, and C-C Simrank"},{"key":"key-10.1145\/3178876.3186107-3","unstructured":"Chang. 2007. Query rewriting through link analysis of the click graph. Proceedings of VLDB (Dec 2008) (2007), 408--421."},{"key":"key-10.1145\/3178876.3186107-4","doi-asserted-by":"crossref","unstructured":"R Artusi, P Verderio, and E Marubini. 2002. Bravais-Pearson and Spearman correlation coefficients: meaning, test of hypothesis and confidence interval. Int J Biol Markers Vol. 17, 2 (2002), 148--151.","DOI":"10.1177\/172460080201700213"},{"key":"key-10.1145\/3178876.3186107-5","doi-asserted-by":"crossref","unstructured":"Bahman Bahmani, Abdur Chowdhury, and Ashish Goel. 2010. Fast incremental and personalized pagerank. Proceedings of the VLDB Endowment Vol. 4, 3 (2010), 173--184.","DOI":"10.14778\/1929861.1929864"},{"key":"key-10.1145\/3178876.3186107-6","doi-asserted-by":"crossref","unstructured":"Soumen Chakrabarti, Amit Pathak, and Manish Gupta. 2011. Index design and query processing for graph conductance search. The VLDB Journal Vol. 20, 3 (2011), 445--470.","DOI":"10.1007\/s00778-010-0204-8"},{"key":"key-10.1145\/3178876.3186107-7","doi-asserted-by":"crossref","unstructured":"Steve Chien, Cynthia Dwork, Ravi Kumar, Daniel R Simon, and D Sivakumar. 2004. Link evolution: Analysis and algorithms. Internet mathematics Vol. 1, 3 (2004), 277--304.","DOI":"10.1080\/15427951.2004.10129090"},{"key":"key-10.1145\/3178876.3186107-8","unstructured":"Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. 1999. On power-law relationships of the internet topology ACM SIGCOMM computer communication review, Vol. Vol. 29. ACM, 251--262."},{"key":"key-10.1145\/3178876.3186107-9","doi-asserted-by":"crossref","unstructured":"Yasuhiro Fujiwara, Makoto Nakatsuji, Makoto Onizuka, and Masaru Kitsuregawa. 2012. Fast and exact top-k search for random walk with restart. Proceedings of the VLDB Endowment Vol. 5, 5 (2012), 442--453.","DOI":"10.14778\/2140436.2140441"},{"key":"key-10.1145\/3178876.3186107-10","doi-asserted-by":"crossref","unstructured":"Glen Jeh and Jennifer Widom. 2002. SimRank: a measure of structural-context similarity Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 538--543.","DOI":"10.1145\/775047.775126"},{"key":"key-10.1145\/3178876.3186107-11","doi-asserted-by":"crossref","unstructured":"Glen Jeh and Jennifer Widom. 2003. Scaling personalized web search. In Proceedings of the 12th international conference on World Wide Web. ACM, 271--279.","DOI":"10.1145\/775152.775191"},{"key":"key-10.1145\/3178876.3186107-12","unstructured":"Woojeong Jin, Jinhong Jung, and U Kang. 2017. Supervised and Extended Restart in Random Walks for Ranking and Link Prediction in Networks. arXiv preprint arXiv:1710.06609."},{"key":"key-10.1145\/3178876.3186107-13","unstructured":"Jinhong Jung, Woojeong Jin, Lee Sael, and U. Kang. 2016 a. Personalized Ranking in Signed Networks Using Signed Random Walk with Restart IEEE 16th International Conference on Data Mining, ICDM 2016, December 12--15, 2016, Barcelona, Spain. 973--978."},{"key":"key-10.1145\/3178876.3186107-14","doi-asserted-by":"crossref","unstructured":"Jinhong Jung, Namyong Park, Lee Sael, and U Kang. 2017. BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart. In SIGMOD.","DOI":"10.1145\/3035918.3035950"},{"key":"key-10.1145\/3178876.3186107-15","unstructured":"Jinhong Jung, Kijung Shin, Lee Sael, and U. Kang. 2016 b. Random Walk with Restart on Large Graphs Using Block Elimination. ACM Trans. Database Syst. Vol. 41, 2 (2016), 12. deftempurl%https:\/\/doi.org\/10.1145\/2901736showDOItempurl"},{"key":"key-10.1145\/3178876.3186107-16","unstructured":"U Kang, Mikhail Bilenko, Dengyong Zhou, and Christos Faloutsos. 2012. Axiomatic Analysis of Co-occurrence Similarity Functions. Carnegie Mellon University-CS-12--102 (2012)."},{"key":"key-10.1145\/3178876.3186107-17","unstructured":"Zhenjiang Lin, Michael R Lyu, and Irwin King. 2009. Matchsim: a novel neighbor-based similarity measure with maximum neighborhood matching Proceedings of the 18th ACM conference on Information and knowledge management. ACM, 1613--1616."},{"key":"key-10.1145\/3178876.3186107-18","doi-asserted-by":"crossref","unstructured":"Naoto Ohsaka, Takanori Maehara, and Ken-ichi Kawarabayashi. 2015. Efficient PageRank tracking in evolving networks. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 875--884.","DOI":"10.1145\/2783258.2783297"},{"key":"key-10.1145\/3178876.3186107-19","unstructured":"Jia-Yu Pan, Hyung-Jeong Yang, Christos Faloutsos, and Pinar Duygulu. 2004. Automatic multimedia cross-modal correlation discovery Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 653--658."},{"key":"key-10.1145\/3178876.3186107-20","doi-asserted-by":"crossref","unstructured":"Haekyu Park, Jinhong Jung, and U. Kang. 2017. A comparative study of matrix factorization and random walk with restart in recommender systems. In 2017 IEEE International Conference on Big Data, BigData 2017, Boston, MA, USA, December 11--14, 2017. 756--765.","DOI":"10.1109\/BigData.2017.8257991"},{"key":"key-10.1145\/3178876.3186107-21","doi-asserted-by":"crossref","unstructured":"Kijung Shin, Jinhong Jung, Sael Lee, and U Kang. 2015. BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. ACM, 1571--1585.","DOI":"10.1145\/2723372.2723716"},{"key":"key-10.1145\/3178876.3186107-22","unstructured":"Jimeng Sun, Huiming Qu, Deepayan Chakrabarti, and Christos Faloutsos. 2005. Neighborhood formation and anomaly detection in bipartite graphs Data Mining, Fifth IEEE International Conference on. IEEE, 8--pp."},{"key":"key-10.1145\/3178876.3186107-23","doi-asserted-by":"crossref","unstructured":"Hanghang Tong and Christos Faloutsos. 2006. Center-piece subgraphs: problem definition and fast solutions Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 404--413.","DOI":"10.1145\/1150402.1150448"},{"key":"key-10.1145\/3178876.3186107-24","doi-asserted-by":"crossref","unstructured":"Hanghang Tong, Christos Faloutsos, and Jia-Yu Pan. 2006. Fast random walk with restart and its applications. (2006).","DOI":"10.1109\/ICDM.2006.70"},{"key":"key-10.1145\/3178876.3186107-25","doi-asserted-by":"crossref","unstructured":"Sibo Wang, Youze Tang, Xiaokui Xiao, Yin Yang, and Zengxiang Li. 2016. HubPPR: effective indexing for approximate personalized pagerank. Proceedings of the VLDB Endowment Vol. 10, 3 (2016), 205--216.","DOI":"10.14778\/3021924.3021936"},{"key":"key-10.1145\/3178876.3186107-26","unstructured":"Joyce Jiyoung Whang, David F Gleich, and Inderjit S Dhillon. 2013. Overlapping community detection using seed set expansion Proceedings of the 22nd ACM international conference on Conference on information & knowledge management. ACM, 2099--2108."},{"key":"key-10.1145\/3178876.3186107-27","doi-asserted-by":"crossref","unstructured":"Minji Yoon, Jinhong Jung, and U Kang. 2018. TPA: Fast, Scalable, and Accurate method for Approximate Random Walk with Restart on Billion Scale Graphs. In IEEE 34th International Conference on Data Engineering, ICDE 2018, April 16--20, 2018, Paris, France.","DOI":"10.1109\/ICDE.2018.00105"},{"key":"key-10.1145\/3178876.3186107-28","doi-asserted-by":"crossref","unstructured":"Hongyang Zhang, Peter Lofgren, and Ashish Goel. 2016. Approximate Personalized PageRank on Dynamic Graphs. arXiv preprint arXiv:1603.07796 (2016).","DOI":"10.1145\/2939672.2939804"},{"key":"key-10.1145\/3178876.3186107-29","unstructured":"Zeyuan Allen Zhu, Silvio Lattanzi, and Vahab S Mirrokni. 2013. A Local Algorithm for Finding Well-Connected Clusters. ICML (3). 396--404."}],"event":{"name":"the 2018 World Wide Web Conference","location":"Lyon, France","acronym":"WWW '18","number":"2018","sponsor":["SIGWEB, ACM Special Interest Group on Hypertext, Hypermedia, and Web","IW3C2, International World Wide Web Conference Committee"],"start":{"date-parts":[[2018,4,23]]},"end":{"date-parts":[[2018,4,27]]}},"container-title":["Proceedings of the 2018 World Wide Web Conference on World Wide Web - WWW '18"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3178876.3186107","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/dl.acm.org\/ft_gateway.cfm?id=3186107&ftid=1957463&dwn=1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:28Z","timestamp":1750212688000},"score":1,"resource":{"primary":{"URL":"http:\/\/dl.acm.org\/citation.cfm?doid=3178876.3186107"}},"subtitle":[],"proceedings-subject":"World Wide Web","short-title":[],"issued":{"date-parts":[[2018]]},"references-count":29,"URL":"https:\/\/doi.org\/10.1145\/3178876.3186107","relation":{},"subject":[],"published":{"date-parts":[[2018]]}}}