{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T08:56:20Z","timestamp":1765356980265,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":30,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,8,14]],"date-time":"2021-08-14T00:00:00Z","timestamp":1628899200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,8,14]]},"DOI":"10.1145\/3447548.3467431","type":"proceedings-article","created":{"date-parts":[[2021,8,13]],"date-time":"2021-08-13T18:21:39Z","timestamp":1628878899000},"page":"964-974","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["An Efficient and Scalable Algorithm for Estimating Kemeny's Constant of a Markov Chain on Large Graphs"],"prefix":"10.1145","author":[{"given":"Shiju","family":"Li","sequence":"first","affiliation":[{"name":"Florida Institute of Technology, Melbourne, FL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xin","family":"Huang","sequence":"additional","affiliation":[{"name":"Florida Institute of Technology, Melbourne, FL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chul-Ho","family":"Lee","sequence":"additional","affiliation":[{"name":"Florida Institute of Technology, Melbourne, FL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,8,14]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"D. Aldous and J. Fill. 2002. Reversible Markov chains and random walks on graphs.  D. Aldous and J. Fill. 2002. Reversible Markov chains and random walks on graphs."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/050643799"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1944345.1944349"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144503423264"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"crossref","unstructured":"C.-K. Chau and P. Basu. 2009. Exact analysis of latency of stateless opportunistic forwarding. In IEEE INFOCOM. 828--836.  C.-K. Chau and P. Basu. 2009. Exact analysis of latency of stateless opportunistic forwarding. In IEEE INFOCOM. 828--836.","DOI":"10.1109\/INFCOM.2009.5061992"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"crossref","unstructured":"F. Chiericetti A. Dasgupta R. Kumar S. Lattanzi and T. Sarl\u00f3s. 2016. On sampling nodes in a network. In WWW. 471--481.  F. Chiericetti A. Dasgupta R. Kumar S. Lattanzi and T. Sarl\u00f3s. 2016. On sampling nodes in a network. In WWW. 471--481.","DOI":"10.1145\/2872427.2883045"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/ett.1017"},{"key":"e_1_3_2_2_8_1","unstructured":"F. R. Chung and F. C. Graham. 1997. Spectral graph theory. Number 92. American Mathematical Soc.  F. R. Chung and F. C. Graham. 1997. Spectral graph theory. Number 92. American Mathematical Soc."},{"key":"e_1_3_2_2_9_1","volume-title":"The Kemeny constant of a Markov chain. arXiv preprint arXiv:0909.2636","author":"Doyle P. G.","year":"2009","unstructured":"P. G. Doyle . 2009. The Kemeny constant of a Markov chain. arXiv preprint arXiv:0909.2636 ( 2009 ). P. G. Doyle. 2009. The Kemeny constant of a Markov chain. arXiv preprint arXiv:0909.2636 (2009)."},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442696"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2011.111011"},{"key":"e_1_3_2_2_12_1","unstructured":"C. Gkantsidis M. Mihail and A. Saberi. 2004. Random walks in peer-to-peer networks. In IEEE INFOCOM. 130.  C. Gkantsidis M. Mihail and A. Saberi. 2004. Random walks in peer-to-peer networks. In IEEE INFOCOM. 130."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1080\/03610926.2012.741742"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1080\/03610918908812806"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/130904867"},{"key":"e_1_3_2_2_16_1","unstructured":"J. G. Kemeny and J. L. Snell. 1976. Markov chains. Springer-Verlag.  J. G. Kemeny and J. L. Snell. 1976. Markov chains. Springer-Verlag."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2020.05.033"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"crossref","unstructured":"R. Kyng and S. Sachdeva. 2016. Approximate gaussian elimination for laplacians-fast sparse and simple. In IEEE FOCS. 573--582.  R. Kyng and S. Sachdeva. 2016. Approximate gaussian elimination for laplacians-fast sparse and simple. In IEEE FOCS. 573--582.","DOI":"10.1109\/FOCS.2016.68"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"crossref","unstructured":"C.-H. Lee and D. Y. Eun. 2015. On the efficiency-optimal Markov chains for distributed networking applications. In IEEE INFOCOM. 1840--1848.  C.-H. Lee and D. Y. Eun. 2015. On the efficiency-optimal Markov chains for distributed networking applications. In IEEE INFOCOM. 1840--1848.","DOI":"10.1109\/INFOCOM.2015.7218566"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.2002.11919905"},{"key":"e_1_3_2_2_21_1","volume-title":"Paul Erdos is Eighty","author":"Lov\u00e1sz L.","year":"1993","unstructured":"L. Lov\u00e1sz . 1993. Random walks on graphs: A survey. Combinatorics , Paul Erdos is Eighty , Vol. 2 , 1 ( 1993 ), 1--46. L. Lov\u00e1sz. 1993. Random walks on graphs: A survey. Combinatorics, Paul Erdos is Eighty, Vol. 2, 1 (1993), 1--46."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1699114"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735703.2735707"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/qua.22323"},{"key":"e_1_3_2_2_25_1","first-page":"3156","article-title":"Robotic surveillance and Markov chains with minimal weighted Kemeny constant","volume":"60","author":"Patel R.","year":"2015","unstructured":"R. Patel , P. Agharkar , and F. Bullo . 2015 . Robotic surveillance and Markov chains with minimal weighted Kemeny constant . IEEE TAC , Vol. 60 , 12 (2015), 3156 -- 3167 . R. Patel, P. Agharkar, and F. Bullo. 2015. Robotic surveillance and Markov chains with minimal weighted Kemeny constant. IEEE TAC, Vol. 60, 12 (2015), 3156--3167.","journal-title":"IEEE TAC"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2006.02.001"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2017.09.003"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"crossref","unstructured":"W. Xu Y. Sheng Z. Zhang H. Kan and Z. Zhang. 2020. Power-Law Graphs Have Minimal Scaling of Kemeny Constant for Random Walks. In WWW. 46--56.  W. Xu Y. Sheng Z. Zhang H. Kan and Z. Zhang. 2020. Power-Law Graphs Have Minimal Scaling of Kemeny Constant for Random Walks. In WWW. 46--56.","DOI":"10.1145\/3366423.3380093"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"crossref","unstructured":"Z. Zhang W. Xu and Z. Zhang. 2020. Nearly Linear Time Algorithm for Mean Hitting Times of Random Walks on a Graph. In WSDM. 726--734.  Z. Zhang W. Xu and Z. Zhang. 2020. Nearly Linear Time Algorithm for Mean Hitting Times of Random Walks on a Graph. In WSDM. 726--734.","DOI":"10.1145\/3336191.3371777"},{"key":"e_1_3_2_2_30_1","unstructured":"M. Zhong and K. Shen. 2006. Popularity-Biased Random Walks for Peer-to-Peer Search under the Square-Root Principle. In IPTPS.  M. Zhong and K. Shen. 2006. Popularity-Biased Random Walks for Peer-to-Peer Search under the Square-Root Principle. In IPTPS."}],"event":{"name":"KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data"],"location":"Virtual Event Singapore","acronym":"KDD '21"},"container-title":["Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447548.3467431","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447548.3467431","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:37Z","timestamp":1750191517000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447548.3467431"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,14]]},"references-count":30,"alternative-id":["10.1145\/3447548.3467431","10.1145\/3447548"],"URL":"https:\/\/doi.org\/10.1145\/3447548.3467431","relation":{},"subject":[],"published":{"date-parts":[[2021,8,14]]},"assertion":[{"value":"2021-08-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}