Computation of the PageRank vector for web search

Supervisor
Prof. Claude Brezinski - Lille (France)
Date and time
Tuesday, September 19, 2006 at 5:30 PM - caffè, tè & C. ore 17.00
Place
Ca' Vignal - Piramide, Floor 0, Hall Verde
Programme Director
Stefano De Marchi
External reference
Publication date
August 18, 2006
Department
 

Summary

An important problem in Web search is determining the importance of each page. After introducing the main characteristics of this problem, we will see that, from the mathematical point of view, it could be solved by computing the left principal eigenvector (the PageRank vector) of a matrix related to the structure of the Web by using the power method. We will give expressions of the PageRank vector and study the mathematical properties of the power method. Various Padé-style approximations of the PageRank vector will be given. Since the convergence of the power method is slow, it has to be accelerated. This problem will be discussed. Recently, several acceleration methods were proposed. We will give a theoretical justification for these methods. In particular, we will generalize the recently proposed Quadratic Extrapolation, and we interpret it on the basis of the method of moments of Vorobyev, and as a Krylov subspace method. Acceleration results are given for the various epsilon-algorithms, and for the E-algorithm. Other algorithms for this problem are also discussed.





© 2002 - 2021  Verona University
Via dell'Artigliere 8, 37129 Verona  |  P. I.V.A. 01541040232  |  C. FISCALE 93009870234