{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T08:50:53Z","timestamp":1765356653240,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":41,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,1,20]],"date-time":"2020-01-20T00:00:00Z","timestamp":1579478400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"the National Natural Science Foundation of China","award":["61872093"],"award-info":[{"award-number":["61872093"]}]},{"name":"the National Key R & D Program of China","award":["2018YFB1305104"],"award-info":[{"award-number":["2018YFB1305104"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,1,20]]},"DOI":"10.1145\/3336191.3371777","type":"proceedings-article","created":{"date-parts":[[2020,1,22]],"date-time":"2020-01-22T19:08:16Z","timestamp":1579720096000},"page":"726-734","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Nearly Linear Time Algorithm for Mean Hitting Times of Random Walks on a Graph"],"prefix":"10.1145","author":[{"given":"Zuobai","family":"Zhang","sequence":"first","affiliation":[{"name":"Fudan University, Shanghai, China"}]},{"given":"Wanyue","family":"Xu","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}]},{"given":"Zhongzhi","family":"Zhang","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}]}],"member":"320","published-online":{"date-parts":[[2020,1,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375608"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0400087101"},{"key":"e_1_3_2_1_3_1","volume-title":"E Greville","author":"Ben-Israel Adi","year":"1974","unstructured":"Adi Ben-Israel and Thomas N . E Greville . 1974 . Generalized inverses: theory and applications .J. Wiley . 406--413 pages. Adi Ben-Israel and Thomas N. E Greville. 1974. Generalized inverses: theory and applications .J. Wiley. 406--413 pages."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/070687402"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000152"},{"volume-title":"Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence. AAAI, 616--621","author":"Chen M.","key":"e_1_3_2_1_6_1","unstructured":"M. Chen , J. Z. Liu , and X. Tang . 2008. Clustering via Random Walk Hitting Time on Directed Graphs . In Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence. AAAI, 616--621 . M. Chen, J. Z. Liu, and X. Tang. 2008. Clustering via Random Walk Hitting Time on Directed Graphs. In Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence. AAAI, 616--621."},{"volume-title":"Spectral Graph Theory","author":"Chung Fan RK","key":"e_1_3_2_1_7_1","unstructured":"Fan RK Chung . 1997. Spectral Graph Theory . American Mathematical Society , Providence, RI . Fan RK Chung. 1997. Spectral Graph Theory .American Mathematical Society, Providence, RI."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591833"},{"key":"e_1_3_2_1_9_1","volume-title":"Nature","volume":"450","author":"Condamin S","year":"2007","unstructured":"S Condamin , O B\u00e9nichou , V Tejedor , R Voituriez , and J Klafter . 2007 . First-passage times in complex scale-invariant media . Nature , Vol. 450 , 7166 (2007), 77--80. S Condamin, O B\u00e9nichou, V Tejedor, R Voituriez, and J Klafter. 2007. First-passage times in complex scale-invariant media. Nature , Vol. 450, 7166 (2007), 77--80."},{"volume-title":"Random Walks and Electric Networks","author":"Doyle Peter G","key":"e_1_3_2_1_10_1","unstructured":"Peter G Doyle and J Laurie Snell . 1984. Random Walks and Electric Networks . Mathematical Association of America . Peter G Doyle and J Laurie Snell. 1984. Random Walks and Electric Networks .Mathematical Association of America."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.46"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/050645452"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.233"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2006.02.008"},{"key":"e_1_3_2_1_15_1","volume-title":"The role of Kemeny's constant in properties of Markov chains . Communications in Statistics -- Theory and Methods","author":"Hunter Jeffrey J","year":"2014","unstructured":"Jeffrey J Hunter . 2014. The role of Kemeny's constant in properties of Markov chains . Communications in Statistics -- Theory and Methods , Vol. 43 , 7 ( 2014 ), 1309--1321. Jeffrey J Hunter. 2014. The role of Kemeny's constant in properties of Markov chains . Communications in Statistics -- Theory and Methods , Vol. 43, 7 (2014), 1309--1321."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2018.2863203"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01164627"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.68"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2015.2391998"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.2002.11919905"},{"volume-title":"Markov Chains and Mixing Times","author":"Levin David Asher","key":"e_1_3_2_1_23_1","unstructured":"David Asher Levin , Yuval Peres , and Elizabeth Lee Wilmer . 2009. Markov Chains and Mixing Times . American Mathematical Society , Providence, RI . David Asher Levin, Yuval Peres, and Elizabeth Lee Wilmer. 2009. Markov Chains and Mixing Times. American Mathematical Society, Providence, RI."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00044"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.87.062140"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/110843563"},{"key":"e_1_3_2_1_27_1","volume-title":"Paul Erd\u00f6s is eighty","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1993","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz . 1993. Random walks on graphs: A survey . Combinatorics , Paul Erd\u00f6s is eighty , Vol. 2 , 1 ( 1993 ), 1--46. L\u00e1szl\u00f3 Lov\u00e1sz. 1993. Random walks on graphs: A survey . Combinatorics, Paul Erd\u00f6s is eighty , Vol. 2, 1 (1993), 1--46."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.103"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1458082.1458145"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2004.11.009"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2015.2426317"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2177753"},{"key":"e_1_3_2_1_34_1","volume-title":"Proceedings of the International Congress of Mathematicians. World Scientific, 2698--2722","author":"Spielman Daniel A","year":"2010","unstructured":"Daniel A Spielman . 2010 . Algorithms, graph theory, and linear equations in Laplacian matrices . In Proceedings of the International Congress of Mathematicians. World Scientific, 2698--2722 . Daniel A Spielman. 2010. Algorithms, graph theory, and linear equations in Laplacian matrices. In Proceedings of the International Congress of Mathematicians. World Scientific, 2698--2722."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.065104"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01046996"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956782"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2011-20338-0"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.4922265"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2015.09.057"}],"event":{"name":"WSDM '20: The Thirteenth ACM International Conference on Web Search and Data Mining","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data","SIGIR ACM Special Interest Group on Information Retrieval"],"location":"Houston TX USA","acronym":"WSDM '20"},"container-title":["Proceedings of the 13th International Conference on Web Search and Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3336191.3371777","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3336191.3371777","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:26:10Z","timestamp":1750206370000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3336191.3371777"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,20]]},"references-count":41,"alternative-id":["10.1145\/3336191.3371777","10.1145\/3336191"],"URL":"https:\/\/doi.org\/10.1145\/3336191.3371777","relation":{},"subject":[],"published":{"date-parts":[[2020,1,20]]},"assertion":[{"value":"2020-01-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}