Computation of the PageRank vector for web search
Prof. Claude Brezinski
- Lille (France)
martedì 19 settembre 2006
caffè, tè & C. ore 17.00
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.
CSS e script comuni siti DOL - frase 9957