Efficient Approximation of Kemeny’s Constant for Large Graphs

Summary: Scalable approximation of Kemeny’s constant for massive graphs via two Monte Carlo methods. RefinedMC trims redundant truncated random walks; ForestMC leverages a Laplacian-submatrix / forest-based identity for higher-accuracy estimation, avoiding explicit matrix inversion. (summarized by gpt-5.4-mini on May 24 2026)

Paper ID: 6961
Venue: SIGMOD
Year: 2024
Pagerank: 5.093636e-05
Overall Rank: 11,172 | 23.36%
DOI: 10.1145/3654937

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Haisong Xia (Fudan University)
2. Zhongzhi Zhang (Fudan University)

BibTeX Citation

@inproceedings{xia_sigmod24,
        title = {{Efficient Approximation of Kemeny’s Constant for Large Graphs}},
        author = {Xia, Haisong and Zhang, Zhongzhi},
        series = {{SIGMOD} '24},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3654937},
        url = {https://dl.acm.org/doi/10.1145/3654937},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2,173	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD	9.0375634e-05
3,892	Massively Parallel Algorithms for Personalized PageRank	2021	VLDB	7.0430255e-05
4,272	Challenging the Long Tail Recommendation	2012	VLDB	6.7911017e-05
4,572	On the Embeddability of Random Walk Distances	2013	VLDB	6.62325e-05
4,600	LightNE: A Lightweight Graph Processing System for Network Embedding	2021	SIGMOD	6.6122574e-05
4,651	Density-based Place Clustering in Geo-Social Networks	2014	SIGMOD	6.585234e-05
4,714	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	6.5497309e-05
5,139	Edge-based Local Push for Personalized PageRank	2022	VLDB	6.3495351e-05
5,236	Localizing Anomalous Changes in Time-evolving Graphs	2014	SIGMOD	6.3044413e-05
7,861	Efficient Resistance Distance Computation: the Power of Landmark-based Approaches	2023	SIGMOD	5.5302333e-05
7,900	Distributed Graph Embedding with Information-Oriented Random Walks	2023	VLDB	5.5193e-05
8,489	Network Shuffling: Privacy Amplification via Random Walks	2022	SIGMOD	5.4152704e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,559	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB
2	11,370	Node-Differentially Private Estimation of the Number of Connected Components	2023	PODS
3	4,497	Leveraging History for Faster Sampling of Online Social Networks	2015	VLDB
4	5,157	Efficient Estimation of Pairwise Effective Resistance	2023	SIGMOD
5	6,423	Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs	2020	SIGMOD
6	9,558	Efficient k-Clique Count Estimation with Accuracy Guarantee	2024	VLDB
7	9,387	Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs	2024	VLDB
8	10,560	Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs	2026	VLDB
9	8,062	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD
10	1,958	A General Framework for Estimating Graphlet Statistics via Random Walk	2017	VLDB