Premium
A Power–Arnoldi algorithm for computing PageRank
Author(s) -
Wu Gang,
Wei Yimin
Publication year - 2007
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.531
Subject(s) - pagerank , power iteration , arnoldi iteration , convergence (economics) , eigenvalues and eigenvectors , power (physics) , graph , mathematics , algorithm , matrix (chemical analysis) , computer science , mathematical optimization , iterative method , theoretical computer science , physics , materials science , quantum mechanics , economics , composite material , economic growth
The PageRank algorithm plays an important role in modern search engine technology. It involves using the classical power method to compute the principle eigenvector of the Google matrix representing the web link graph. However, when the largest eigenvalue is not well separated from the second one, the power method may perform poorly. This happens when the damping factor is sufficiently close to 1. Therefore, it is worth developing new techniques that are more sophisticated than the power method. The approach presented here, called Power–Arnoldi, is based on a periodic combination of the power method with the thick restarted Arnoldi algorithm. The justification for this new approach is presented. Numerical tests illustrate the efficiency and convergence behaviour of the new algorithm. Copyright © 2007 John Wiley & Sons, Ltd.