An adaptive bidirectional algorithm for constant-relative-error PageRank estimation is instance-optimal up to polylog factors on bounded-degree directed graphs and on sparse graphs with polylog high-degree vertices.
Estimating random-walk probabilities in directed graphs
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
fields
cs.DS 2years
2025 2representative citing papers
Establishes near-optimal time bounds for SSPPR-A and SSPPR-R queries, with matching upper and lower bounds for SSPPR-R on graphs where m is Omega(n log squared n).
citing papers explorer
-
Instance-Optimality in PageRank Computation
An adaptive bidirectional algorithm for constant-relative-error PageRank estimation is instance-optimal up to polylog factors on bounded-degree directed graphs and on sparse graphs with polylog high-degree vertices.
-
Near-Optimality for Single-Source Personalized PageRank
Establishes near-optimal time bounds for SSPPR-A and SSPPR-R queries, with matching upper and lower bounds for SSPPR-R on graphs where m is Omega(n log squared n).