Mathematical Analysis of Google PageRank
Date: Tue, Sep 8 2009
Location: Bizkaia Technology Park, Building 500 E-48160 DERIO - Basque Country- Spain
Speakers: Konstantin Avrachenkov
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.
Non-self-adjoint operators and their spectra
RGAS School on Singularities
Daniel Bath (KU Leuven), Eamon Quinlan-Gallego (U. Utah), Ilya Smirnov (BCAM Bilbao) and Guillem Blanco (KU Leuven)