{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T17:39:11Z","timestamp":1781890751129,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":36,"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"}],"funder":[{"name":"JSPS KAKENHI","award":["17H04676, 18H05291, 20H05965"],"award-info":[{"award-number":["17H04676, 18H05291, 20H05965"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,8,14]]},"DOI":"10.1145\/3447548.3467361","type":"proceedings-article","created":{"date-parts":[[2021,8,12]],"date-time":"2021-08-12T06:12:08Z","timestamp":1628748728000},"page":"1329-1338","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Local Algorithms for Estimating Effective Resistance"],"prefix":"10.1145","author":[{"given":"Pan","family":"Peng","sequence":"first","affiliation":[{"name":"University of Sheffield, Sheffield, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Lopatta","sequence":"additional","affiliation":[{"name":"University of Sheffield, Sheffield, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuichi","family":"Yoshida","sequence":"additional","affiliation":[{"name":"National Institute of Informatics, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gramoz","family":"Goranci","sequence":"additional","affiliation":[{"name":"University of Glasgow, Glasgow, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,8,14]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2020.10.096"},{"key":"e_1_3_2_2_2_1","volume-title":"9th Innovations in Theoretical Computer Science Conference (ITCS)","volume":"94","author":"Alev Vedat Levi","year":"2018","unstructured":"Vedat Levi Alev , Nima Anari , Lap Chi Lau , and Shayan Oveis Gharan . 2018 . Graph Clustering using Effective Resistance . In 9th Innovations in Theoretical Computer Science Conference (ITCS) , Vol. 94 . 41:1--41:16. Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. 2018. Graph Clustering using Effective Resistance. In 9th Innovations in Theoretical Computer Science Conference (ITCS), Vol. 94. 41:1--41:16."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.11"},{"key":"e_1_3_2_2_4_1","volume-title":"On Solving Linear Systems in Sublinear Time. In 10th Innovations in Theoretical Computer Science Conference (ITCS).","author":"Andoni Alexandr","year":"2018","unstructured":"Alexandr Andoni , Robert Krauthgamer , and Yosef Pogrow . 2018 . On Solving Linear Systems in Sublinear Time. In 10th Innovations in Theoretical Computer Science Conference (ITCS). Alexandr Andoni, Robert Krauthgamer, and Yosef Pogrow. 2018. On Solving Linear Systems in Sublinear Time. In 10th Innovations in Theoretical Computer Science Conference (ITCS)."},{"key":"e_1_3_2_2_5_1","unstructured":"Siddhartha Banerjee and Peter Lofgren. 2015. Fast Bidirectional Probability Estimation in Markov Models. In Advances in Neural Information Processing Systems (NIPS). 1423--1431.  Siddhartha Banerjee and Peter Lofgren. 2015. Fast Bidirectional Probability Estimation in Markov Models. In Advances in Neural Information Processing Systems (NIPS). 1423--1431."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30541-2_4"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00073"},{"key":"e_1_3_2_2_8_1","volume-title":"On approximating the stationary distribution of time-reversible Markov chains. Theory of Computing Systems","author":"Bressan Marco","year":"2019","unstructured":"Marco Bressan , Enoch Peserico , and Luca Pretto . 2019. On approximating the stationary distribution of time-reversible Markov chains. Theory of Computing Systems ( 2019 ), 1--23. Marco Bressan, Enoch Peserico, and Luca Pretto. 2019. On approximating the stationary distribution of time-reversible Markov chains. Theory of Computing Systems (2019), 1--23."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01270385"},{"key":"e_1_3_2_2_10_1","volume-title":"Testing Graph Clusterability: Algorithms and Lower Bounds. (2018). arxiv","author":"Chiplunkar Ashish","year":"1808","unstructured":"Ashish Chiplunkar , Michael Kapralov , Sanjeev Khanna , Aida Mousavifar , and Yuval Peres . 2018. Testing Graph Clusterability: Algorithms and Lower Bounds. (2018). arxiv : 1808 .04807 Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, and Yuval Peres. 2018. Testing Graph Clusterability: Algorithms and Lower Bounds. (2018). arxiv: 1808.04807"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993674"},{"key":"e_1_3_2_2_12_1","volume-title":"Spectral Graph Theory","author":"Chung Fan R. K","unstructured":"Fan R. K Chung . 1997. Spectral Graph Theory . American Mathematical Society . Fan R. K Chung. 1997. Spectral Graph Theory .American Mathematical Society."},{"key":"e_1_3_2_2_13_1","volume-title":"Proceedings of the 46th annual ACM Symposium on Theory of Computing (STOC). 343--352","author":"Cohen Michael B.","year":"2014","unstructured":"Michael B. Cohen , Rasmus Kyng , Gary L. Miller , Jakub W. Pachocki , Richard Peng , Anup B. Rao , and Shen Chen Xu . 2014 . Solving SDD linear systems in nearly mlog(1\/2 )n time . In Proceedings of the 46th annual ACM Symposium on Theory of Computing (STOC). 343--352 . Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu. 2014. Solving SDD linear systems in nearly mlog(1\/2 )n time. In Proceedings of the 46th annual ACM Symposium on Theory of Computing (STOC). 343--352."},{"key":"e_1_3_2_2_14_1","volume-title":"Concentration of measure for the analysis of randomized algorithms","author":"Dubhashi Devdatt P","unstructured":"Devdatt P Dubhashi and Alessandro Panconesi . 2009. Concentration of measure for the analysis of randomized algorithms . Cambridge University Press . Devdatt P Dubhashi and Alessandro Panconesi. 2009. Concentration of measure for the analysis of randomized algorithms .Cambridge University Press."},{"key":"e_1_3_2_2_15_1","volume-title":"Effective graph resistance. Linear algebra and its applications","author":"Ellens Wendy","year":"2011","unstructured":"Wendy Ellens , FM Spieksma , P Van Mieghem , A Jamakovic , and RE Kooij . 2011. Effective graph resistance. Linear algebra and its applications , Vol. 435 , 10 ( 2011 ), 2491--2506. Wendy Ellens, FM Spieksma, P Van Mieghem, A Jamakovic, and RE Kooij. 2011. Effective graph resistance. Linear algebra and its applications, Vol. 435, 10 (2011), 2491--2506."},{"key":"e_1_3_2_2_16_1","volume-title":"Community detection in graphs. Physics reports","author":"Fortunato Santo","year":"2010","unstructured":"Santo Fortunato . 2010. Community detection in graphs. Physics reports , Vol. 486 , 3--5 ( 2010 ), 75--174. Santo Fortunato. 2010. Community detection in graphs. Physics reports, Vol. 486, 3--5 (2010), 75--174."},{"key":"e_1_3_2_2_17_1","volume-title":"Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI). 3733--3739","author":"Hayashi Takanori","year":"2016","unstructured":"Takanori Hayashi , Takuya Akiba , and Yuichi Yoshida . 2016 . Efficient algorithms for spanning tree centrality . In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI). 3733--3739 . Takanori Hayashi, Takuya Akiba, and Yuichi Yoshida. 2016. Efficient algorithms for spanning tree centrality. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI). 3733--3739."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.159"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775126"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289026"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043932.2043945"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73435-2_21"},{"key":"e_1_3_2_2_23_1","unstructured":"Christina E Lee Asuman Ozdaglar and Devavrat Shah. 2013. Computing the stationary distribution locally. In Advances in Neural Information Processing Systems. 1376--1384.  Christina E Lee Asuman Ozdaglar and Devavrat Shah. 2013. Computing the stationary distribution locally. In Advances in Neural Information Processing Systems. 1376--1384."},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2835776.2835823"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623745"},{"key":"e_1_3_2_2_26_1","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz et al. 1993. Random walks on graphs: A survey. Combinatorics Paul erdos is eighty Vol. 2 1 (1993) 1--46.  L\u00e1szl\u00f3 Lov\u00e1sz et al. 1993. Random walks on graphs: A survey. Combinatorics Paul erdos is eighty Vol. 2 1 (1993) 1--46."},{"key":"e_1_3_2_2_27_1","volume-title":"Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications","author":"L\u00fc Linyuan","year":"2011","unstructured":"Linyuan L\u00fc and Tao Zhou . 2011. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications , Vol. 390 , 6 ( 2011 ), 1150--1170. Linyuan L\u00fc and Tao Zhou. 2011. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications, Vol. 390, 6 (2011), 1150--1170."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnx082"},{"key":"e_1_3_2_2_29_1","volume-title":"Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Madry Aleksander","year":"2014","unstructured":"Aleksander Madry , Damian Straszak , and Jakub Tarnawski . 2014 . Fast Generation of Random Spanning Trees and the Effective Resistance Metric . In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Aleksander Madry, Damian Straszak, and Jakub Tarnawski. 2014. Fast Generation of Random Spanning Trees and the Effective Resistance Metric. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100033879"},{"key":"e_1_3_2_2_31_1","volume-title":"Lecture 4-5: Effective Resistance and Simple Random Walks. https:\/\/homes.cs.washington.edu\/ shayan\/courses\/approx\/adv-approx-4.pdf","author":"Gharan Shayan Oveis","year":"2015","unstructured":"Shayan Oveis Gharan . 2015. Lecture 4-5: Effective Resistance and Simple Random Walks. https:\/\/homes.cs.washington.edu\/ shayan\/courses\/approx\/adv-approx-4.pdf ( 2015 ). Shayan Oveis Gharan. 2015. Lecture 4-5: Effective Resistance and Simple Random Walks. https:\/\/homes.cs.washington.edu\/ shayan\/courses\/approx\/adv-approx-4.pdf (2015)."},{"key":"e_1_3_2_2_33_1","volume-title":"Computing and Software Science","author":"Ron Dana","unstructured":"Dana Ron . 2019. Sublinear-time algorithms for approximating graph parameters . In Computing and Software Science . Springer , 105--122. Dana Ron. 2019. Sublinear-time algorithms for approximating graph parameters. In Computing and Software Science. Springer, 105--122."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0023849"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644893.1644932"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"e_1_3_2_2_37_1","volume-title":"Analyzing Location-Based Advertising for Vehicle Service Providers Using Effective Resistances. Proceedings of the ACM on Measurement and Analysis of Computing Systems","volume":"3","author":"Yu Haoran","year":"2019","unstructured":"Haoran Yu , Ermin Wei , and Randall A. Berry . 2019 . Analyzing Location-Based Advertising for Vehicle Service Providers Using Effective Resistances. Proceedings of the ACM on Measurement and Analysis of Computing Systems , Vol. 3 , 1, Article 6 ( 2019 ), 35 pages. Haoran Yu, Ermin Wei, and Randall A. Berry. 2019. Analyzing Location-Based Advertising for Vehicle Service Providers Using Effective Resistances. Proceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 3, 1, Article 6 (2019), 35 pages."}],"event":{"name":"KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","location":"Virtual Event Singapore","acronym":"KDD '21","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data"]},"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.3467361","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447548.3467361","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:23Z","timestamp":1750191503000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447548.3467361"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,14]]},"references-count":36,"alternative-id":["10.1145\/3447548.3467361","10.1145\/3447548"],"URL":"https:\/\/doi.org\/10.1145\/3447548.3467361","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"}}]}}