Estimating PageRank on Graph Streams

This article focuses on computations on large graphs (e.g., the web-graph) where the edges of the graph are presented as a stream. The objective in the streaming model is to use small amount of memory (preferably sub-linear in the number of nodes n) and a smaller number of passes. In the streaming model, we show how to perform several graph computations including estimating the probability distribution after a random walk of length l, the mixing time M, and other related quantities such as the conductance of the graph. By applying our algorithm for computing probability distribution on the web-graph, we can estimate the PageRank p of any node up to an additive error of root epsilon p+ epsilon in (O) over tilde(root M/alpha) passes and (O) over tilde (min(n alpha + 1/epsilon root M/alpha + (1/epsilon)M alpha, alpha n root M alpha + (1/epsilon)root M/alpha)) space, for any alpha is an element of (0, 1]. Specifically, for epsilon = M/n, alpha = M-1/2, we can compute the approximate PageRank values in (O) over tilde (nM(-1/4)) space and (O) over tilde (M-3/4) passes. In comparison, a standard implementation of the PageRank algorithm will take O(n) space and O(M) passes. We also give an approach to approximate the PageRank values in just (O) over tilde (1) passes although this requires (O) over tilde (nM) space.