Séminaire MOCOSY :                       Mathematical Analysis of Google Page Rank
Intervenant:    
Konstantin Avrachenkov
INRIA Sophia Antipolis, MAESTRO team
email: k.avrachenkov@sophia.inria.fr
web: http://www-sop.inria.fr/maestro/personnel/K.Avrachenkov/me.html
Date : 12 November 2007
Heure : 11 h 00
Lieu :
 Salle Europe
LAAS, 7 Av. de Colonel Roche
[how to get to LAAS]
Résumé : PageRank is one of the principle criteria according to which Google ranks Web pages.  PageRank can be interpreted as a frequency of visiting a Web page by a random surfer and thus it reflects the popularity of a Web page. In this talk we present several interesting mathematical problems around PageRank. First, we suggest the Monte Carlo approach for PageRank computation. Then, we study the effect of newly created links on Google PageRank. We discuss to what extend a page can control its PageRank. We show that there exists an optimal linking strategy.  Finally, we apply singular perturbation approach to study the choice of the damping factor in Google's PageRank. The PageRank damping factor is a crucial parameter which determines what proportion of local information in respect to the global information is taken into account.  The Google's choice for the damping factor value is 0.85. In this work we propose new criteria for choosing the damping factor, based on the ergodic structure of the Web Graph and probability flows. These new criteria suggest that the damping factor should be chosen around one half.