Back to papers
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
- 6900
- Venue
- SIGMOD
- Year
- 2024
- Pagerank
- 4.1905499e-05
- Overall Rank
- 10,961 | 23.83%
- DOI
-
10.1145/3654937
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
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,522 |
Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push |
2021 |
SIGMOD |
8.6029608e-05 |
| 4,487 |
On the Embeddability of Random Walk Distances |
2013 |
VLDB |
6.1412716e-05 |
| 4,560 |
Massively Parallel Algorithms for Personalized PageRank |
2021 |
VLDB |
6.0788254e-05 |
| 4,923 |
LightNE: A Lightweight Graph Processing System for Network Embedding |
2021 |
SIGMOD |
5.8218782e-05 |
| 4,975 |
Challenging the Long Tail Recommendation |
2012 |
VLDB |
5.7854712e-05 |
| 5,000 |
Density-based Place Clustering in Geo-Social Networks |
2014 |
SIGMOD |
5.7636502e-05 |
| 5,237 |
Edge-based Local Push for Personalized PageRank |
2022 |
VLDB |
5.6071758e-05 |
| 5,666 |
Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme |
2023 |
SIGMOD |
5.3824583e-05 |
| 5,701 |
Localizing Anomalous Changes in Time-evolving Graphs |
2014 |
SIGMOD |
5.36437e-05 |
| 7,924 |
Distributed Graph Embedding with Information-Oriented Random Walks |
2023 |
VLDB |
4.6109814e-05 |
| 8,509 |
Network Shuffling: Privacy Amplification via Random Walks |
2022 |
SIGMOD |
4.4904878e-05 |
| 9,252 |
Efficient Resistance Distance Computation: the Power of Landmark-based Approaches |
2023 |
SIGMOD |
4.3648789e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 3,622 |
Efficient and Effective Algorithms for Clustering Uncertain Graphs |
2019 |
VLDB |
6.9021704e-05 |
| 11,167 |
Node-Differentially Private Estimation of the Number of Connected Components |
2023 |
PODS |
4.1905499e-05 |
| 2,102 |
Leveraging History for Faster Sampling of Online Social Networks |
2015 |
VLDB |
9.5379264e-05 |
| 5,936 |
Efficient Estimation of Pairwise Effective Resistance |
2023 |
SIGMOD |
5.2611905e-05 |
| 6,493 |
Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs |
2020 |
SIGMOD |
5.0344095e-05 |
| 9,412 |
Efficient k-Clique Count Estimation with Accuracy Guarantee |
2024 |
VLDB |
4.3399748e-05 |
| 9,246 |
Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs |
2024 |
VLDB |
4.3648789e-05 |
| 10,272 |
Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs |
2026 |
VLDB |
4.1905499e-05 |
| 9,330 |
Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches |
2023 |
SIGMOD |
4.351469e-05 |
| 1,724 |
A General Framework for Estimating Graphlet Statistics via Random Walk |
2017 |
VLDB |
0.00010736699 |