{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T18:38:19Z","timestamp":1791916699319,"version":"4.3.4"},"reference-count":71,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62372112, U20B2051, and 61872093"],"award-info":[{"award-number":["62372112, U20B2051, and 61872093"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>For an undirected graph, its Kemeny's constant is defined as the mean hitting time of random walks from one vertex to another chosen randomly according to the stationary distribution. Kemeny's constant exhibits numerous explanations from different perspectives and has found various applications in the field of complex networks. Due to the requirement of computing the inverse of the normalized Laplacian matrix, it is infeasible to get the accurate Kemeny's constant of large networks with millions of vertices. Existing methods either consume excessive memory space that are impractical for large-scale networks, or involve redundant simulation, leaving room for further optimization. In this paper, we propose two scalable Monte Carlo algorithms RefinedMC and ForestMC to approximate Kemeny's constant. RefinedMC makes several refinements based on the simulation of truncated random walks, significantly reducing the amount of required random walks, while ForestMC utilizes the newly discovered paradigm connecting Kemeny's constant with the inverse of corresponding Laplacian submatrix, which is considerably accurate. Extensive numerical experiments on model and realistic networks demonstrate that our approximation algorithms evidently outperform the baseline methods in terms of efficiency and accuracy.<\/jats:p>","DOI":"10.1145\/3654937","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-26","source":"Crossref","is-referenced-by-count":6,"title":["Efficient Approximation of Kemeny's Constant for Large Graphs"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-3339-0054","authenticated-orcid":false,"given":"Haisong","family":"Xia","sequence":"first","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1260-2079","authenticated-orcid":false,"given":"Zhongzhi","family":"Zhang","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"David Aldous and Jim Fill. 2002. Reversible Markov Chains and Random Walks on Graphs. (2002)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75225-7_15"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1944345.1944349"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0400087101"},{"key":"e_1_2_1_5_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."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/070687402"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000152"},{"key":"e_1_2_1_8_1","first-page":"1","article-title":"On stationary-point hitting time and ergodicity of stochastic gradient Langevin dynamics","volume":"21","author":"Chen Xi","year":"2020","unstructured":"Xi Chen, Simon S. Du, and Xin T. Tong. 2020. On stationary-point hitting time and ergodicity of stochastic gradient Langevin dynamics. Journal of Machine Learning Research, Vol. 21, 68 (2020), 1--41.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3580305.3599251"},{"key":"e_1_2_1_10_1","volume-title":"Spectral Graph Theory","author":"Chung Fan RK","unstructured":"Fan RK Chung. 1997. Spectral Graph Theory. American Mathematical Society."},{"key":"e_1_2_1_11_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."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.71.016128"},{"key":"e_1_2_1_13_1","volume-title":"Random Walks and Electric Networks","author":"Doyle Peter G","unstructured":"Peter G Doyle and J Laurie Snell. 1984. Random Walks and Electric Networks. Mathematical Association of America."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3587136.3587140"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.46"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/050645452"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 25th International Joint Conference on Artificial Intelligence","volume":"16","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, Vol. 16. 3733--3739."},{"key":"e_1_2_1_18_1","volume-title":"Probability Inequalities for Sums of Bounded Random Variables","author":"Hoeffding Wassily","unstructured":"Wassily Hoeffding. 1994. Probability Inequalities for Sums of Bounded Random Variables. Springer New York, 409--426."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461554"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588705"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1080\/03610926.2012.741742"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1080\/03610918908812806"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.4807589"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.5143504"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01164627"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjp\/s13360-023-03997-0"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1063\/5.0105099"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.68"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","unstructured":"R. B. Lehoucq D. C. Sorensen and C. Yang. 1998. ARPACK Users' Guide. Society for Industrial and Applied Mathematics. https:\/\/doi.org\/10.1137\/1.9780898719628","DOI":"10.1137\/1.9780898719628"},{"key":"e_1_2_1_31_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_32_1","volume-title":"Measuring the network vulnerability based on Markov criticality. ACM Transactions on Knowledge Discovery from Data","author":"Li Hui-Jia","year":"2021","unstructured":"Hui-Jia Li, Lin Wang, Zhan Bu, Jie Cao, and Yong Shi. 2021b. Measuring the network vulnerability based on Markov criticality. ACM Transactions on Knowledge Discovery from Data, Vol. 16, 2 (2021), 28:1--28:24."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467431"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588922"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526162"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3167062"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.87.062140"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems. 1124--1132","author":"Liu Brandon K.","year":"2016","unstructured":"Brandon K. Liu, David C. Parkes, and Sven Seuken. 2016. Personalized hitting time for informative trust mechanisms despite sybils. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems. 1124--1132."},{"key":"e_1_2_1_39_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."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.103"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2004.11.009"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1002\/qua.22323"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2015.2426317"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3449970"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467361"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxz080"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxx094"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2018.2797483"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457329"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.03.009"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2925610"},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. 99--110","author":"Shi Jieming","unstructured":"Jieming Shi, Nikos Mamoulis, Dingming Wu, and David W. Cheung. 2014. Density-based place clustering in geo-social networks. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. 99--110."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612184"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.065104"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01046996"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/3523210.3523216"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2017.09.003"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956782"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237880"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457298"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2011-20338-0"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.4922265"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2015.09.057"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380093"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311916"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3580305.3599323"},{"key":"e_1_2_1_68_1","volume-title":"Proceedings of the 38th International Conference on Machine Learning","volume":"139","author":"Zhang Yiming","unstructured":"Yiming Zhang and Keith W. Ross. 2021. On-policy deep reinforcement learning for the average-reward criterion. In Proceedings of the 38th International Conference on Machine Learning, Vol. 139. 12535--12545."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3336191.3371777"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.85.011106"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556554"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654937","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654937","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:37:13Z","timestamp":1755787033000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654937"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":71,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654937"],"URL":"https:\/\/doi.org\/10.1145\/3654937","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}