Randomized incremental algorithms for the PageRank computation

This paper proposes a new class of randomized algorithms to incrementally compute the Google PageRank of a large-scale number of webpages. First, we reformulate the PageRank computation as a least squares (LS) problem. Motivated by a random surfer model, the LS problem is solved in a randomized incremental way. Specifically, when visiting a page, the surfer incrementally updates an estimate of the PageRank by using the information from those pages connected by hyperlinks. Then, the surfer either randomly selects an outgoing link of the current page and moves to the page pointed by this link, or interrupts its search and jumps to an arbitrary page. Subsequently, the PageRank estimate is updated again. The transition between pages is naturally modeled as a Markov process. Under an ergodicity property, we prove the convergence of the proposed algorithm to the PageRank in both the almost sure and Lp sense. A comparison with a classical PageRank algorithm is discussed as well.