Efficient randomized algorithms for PageRank problem
This work addresses the PageRank problem for web ranking and related applications, presenting incremental improvements with new methods and estimations.
The paper tackles the PageRank problem by proposing a Markov Chain Monte Carlo method with a new estimation and a novel method based on reducing the problem to a matrix game solved via randomized mirror descent with non-standard randomization. The results include new estimations and a method for solving sparse matrix games, but no concrete performance numbers are provided.
In the paper we compare well known numerical methods of finding PageRank vector. We propose Markov Chain Monte Carlo method and obtain a new estimation for this method. We also propose a new method for PageRank problem based on the reduction of this problem to the matrix game. We solve this (sparse) matrix game with randomized mirror descent. It should be mentioned that we used non-standard randomization (in KL-projection) goes back to Grigoriadis-Khachiayn (1995).