Showing 2025Show all
3 papers · 1 filter
cs.DS2025
Instance-Optimality of Bidirectional PageRank Estimation
Mikkel Thorup, Hanzhi Wang
We study the problem of estimating a vertex's PageRank within a constant relative error, with constant probability. We prove that an adaptive variant of the simple classic bidirect…
cs.DS2025
Approximate Graph Propagation Revisited: Dynamic Parameterized Queries, Tighter Bounds and Dynamic Updates
Zhuowei Zhao, Zhuo Zhang, Hanzhi Wang +3
We revisit Approximate Graph Propagation (AGP), a unified framework which captures various graph propagation tasks, such as PageRank, feature propagation in Graph Neural Networks (…
cs.DS2025
Estimating Random-Walk Probabilities in Directed Graphs
Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup +2
We study discounted random walks in directed graphs. In each step, the walk either terminates with a constant probability , or proceeds to a random out-neighbor. Our goal is to…