  How large a fraction of a graph must one explore to rank a small set of nodes
according to their PageRank scores? We show that the answer is quite nuanced,
and depends crucially on the interplay between the correctness guarantees one
requires and the way one can access the graph. On the one hand, assuming the
graph can be accessed only via "natural" exploration queries that reveal small
pieces of its topology, we prove that deterministic and Las Vegas algorithms
must in the worst case perform $n - o(n)$ queries and explore essentially the
entire graph, independently of the specific types of query employed. On the
other hand we show that, depending on the types of query available, Monte Carlo
algorithms can perform asymptotically better: if allowed to both explore the
local topology around single nodes and access nodes at random in the graph they
need $\Omega(n^{2/3})$ queries in the worst case, otherwise they still need
$\Omega(n)$ queries similarly to Las Vegas algorithms. All our bounds
generalize and tighten those already known, cover the different types of graph
exploration queries appearing in the literature, and immediately apply also to
the problem of approximating the PageRank score of single nodes.
