Mathematical Analysis of Google PageRank

PageRank is one of the principal criteria according to which Google ranks relevant answers to a user query. PageRank can be viewed as a random walk on the Web graph with uniform random jumps after a geometrically distributed number of steps. It can also be viewed as a singular perturbed Markov chain. PageRank is not able to take into account personal preferences of the users. To address this problem, the Personalized PageRank criterion has been proposed. In the Personalized PageRank the random walk on the Web graph restarts with a non- uniform distribution representing user preferences and interests. Since a user is typically interested in some top list of relevant answers, we propose to use Monte Carlo methods which find top lists with very light complexity. We study and compare several Monte Carlo methods analytically as well as numerically.

The talk is based on a joint work with N. Litvak and D. Nemirovsky.