Back to papers
Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach
Summary: Index-based effective-resistance computation via multiple landmarks: precompute compact Schur-complement matrices over a landmark set, then answer single-pair/source queries with Vl-absorbed random-walk push/sampling. Provable accuracy/performance guarantees; up to 10^4× speedup on large graphs.
(summarized by gpt-5.4-mini on May 24 2026)
- Paper ID
- 6899
- Venue
- SIGMOD
- Year
- 2024
- Pagerank
- 4.1905499e-05
- Overall Rank
- 10,960 | 23.83%
- DOI
-
10.1145/3654936
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
Outgoing Citations (Sorted by Pagerank)
Showing 18 of 18 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank |
Cited Paper |
Year |
Venue |
Pagerank |
| 260 |
Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling |
2013 |
SIGMOD |
0.00030020929 |
| 707 |
Near Neighbor Search in Large Metric Spaces |
1995 |
VLDB |
0.00017770532 |
| 1,809 |
Computing Personalized PageRank Quickly by Exploiting Graph Structures |
2014 |
VLDB |
0.00010472588 |
| 2,110 |
HubPPR: Effective Indexing for Approximate Personalized PageRank |
2017 |
VLDB |
9.5280826e-05 |
| 2,189 |
BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs |
2015 |
SIGMOD |
9.3358152e-05 |
| 2,206 |
When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks |
2018 |
SIGMOD |
9.2958349e-05 |
| 2,522 |
Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push |
2021 |
SIGMOD |
8.6029608e-05 |
| 4,688 |
TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs |
2018 |
SIGMOD |
5.9900111e-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,701 |
Localizing Anomalous Changes in Time-evolving Graphs |
2014 |
SIGMOD |
5.36437e-05 |
| 5,713 |
Efficient Estimation of Heat Kernel PageRank for Local Clustering |
2019 |
SIGMOD |
5.3595796e-05 |
| 5,936 |
Efficient Estimation of Pairwise Effective Resistance |
2023 |
SIGMOD |
5.2611905e-05 |
| 6,203 |
k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation |
2016 |
VLDB |
5.1552752e-05 |
| 6,310 |
Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks |
2018 |
SIGMOD |
5.111823e-05 |
| 8,252 |
Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement |
2022 |
VLDB |
4.544713e-05 |
| 9,252 |
Efficient Resistance Distance Computation: the Power of Landmark-based Approaches |
2023 |
SIGMOD |
4.3648789e-05 |
| 9,330 |
Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches |
2023 |
SIGMOD |
4.351469e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 2,118 |
Efficient SimRank-based Similarity Join Over Large Graphs |
2013 |
VLDB |
9.5036922e-05 |
| 10,159 |
Efficient Influential Community Search over Dynamic Graphs |
2026 |
SIGMOD |
4.1905499e-05 |
| 5,936 |
Efficient Estimation of Pairwise Effective Resistance |
2023 |
SIGMOD |
5.2611905e-05 |
| 2,440 |
Efficient Structural Graph Clustering: An Index-Based Approach |
2018 |
VLDB |
8.8166939e-05 |
| 7,430 |
DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs |
2022 |
VLDB |
4.7275494e-05 |
| 9,485 |
I/O Efficient Label-Constrained Reachability Queries in Large Graphs |
2024 |
VLDB |
4.3300131e-05 |
| 10,272 |
Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs |
2026 |
VLDB |
4.1905499e-05 |
| 10,075 |
Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach |
2026 |
SIGMOD |
4.1905499e-05 |
| 9,641 |
Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs |
2025 |
SIGMOD |
4.3067693e-05 |
| 9,252 |
Efficient Resistance Distance Computation: the Power of Landmark-based Approaches |
2023 |
SIGMOD |
4.3648789e-05 |