Estimating PageRank on graph streams

<jats:p> 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 <jats:italic>n</jats:italic> ) and a smaller number of passes. </jats:p> <jats:p> In the streaming model, we show how to perform several graph computations including estimating the probability distribution after a random walk of length <jats:italic>l</jats:italic> , the mixing time <jats:italic>M</jats:italic> , 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 <jats:italic>PageRank</jats:italic> <jats:italic>p</jats:italic> of any node up to an additive error of √ε <jats:italic>p</jats:italic> +ε in <jats:italic>Õ</jats:italic> (√ <jats:italic>M</jats:italic> /α) passes and <jats:italic>Õ</jats:italic> (min( <jats:italic>n</jats:italic> α+1/ε√ <jats:italic>M</jats:italic> /α+(1/ε) <jats:italic>M</jats:italic> α, α <jats:italic>n</jats:italic> √ <jats:italic>M</jats:italic> α + (1/ε)√ <jats:italic>M</jats:italic> /α)) space, for any α ∈ (0,1]. Specifically, for ε = <jats:italic>M</jats:italic> / <jats:italic>n</jats:italic> , α = <jats:italic>M</jats:italic> <jats:sup>−1/2</jats:sup> , we can compute the approximate PageRank values in Õ( <jats:italic>nM</jats:italic> <jats:sup>−1/4</jats:sup> ) space and Õ( <jats:italic>M</jats:italic> <jats:sup>3/4</jats:sup> ) passes. In comparison, a standard implementation of the PageRank algorithm will take <jats:italic>O(n)</jats:italic> space and <jats:italic>O(M)</jats:italic> passes. We also give an approach to approximate the PageRank values in just Õ(1) passes although this requires Õ( <jats:italic>nM</jats:italic> ) space. </jats:p>