Computation of the PageRank vector for web search

Relatore
Prof. Claude Brezinski - Lille (France)

Data e ora
martedì 19 settembre 2006 alle ore 17.30 - caffè, tè & C. ore 17.00

Luogo
Ca' Vignal 3 - Piramide, Piano 0, Sala Verde

Referente
Stefano De Marchi

Referente esterno

Data pubblicazione
18 agosto 2006

Dipartimento
 

Riassunto

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.
ornamento
Inizio pagina