Google PageRanking problem: The model and the analysis

The spectral and Jordan structures of the Web hyperlink matrix G(c)=cG+(1-c)evT have been analyzed when G is the basic (stochastic) Google matrix, c is a real parameter such that 0<1, v is a nonnegative probability vector, and e is the all-ones vector. Typical studies have relied heavily on special properties of nonnegative, positive, and stochastic matrices. There is a unique nonnegative vector y(c) such that y(c)TG(c)=y(c) T and y(c)Te=1. This PageRank vector y(c) can be computed effectively by the power method. We consider a square complex matrix A and nonzero complex vectors x and v such that Ax=λx and v*x=1. We use standard matrix analytic tools to determine the eigenvalues, the Jordan blocks, and a distinguished left λ-eigenvector of A(c)=cA+(1-c)λxv* as a function of a complex variable c. If λ is a semisimple eigenvalue of A, there is a uniquely determined projection N such that limc→1y(c)=Nv for all v; this limit may fail to exist for some v if λ is not semisimple. As a special case of our results, we obtain a complex analog of PageRank for the Web hyperlink matrix G(c) with a complex parameter c. We study regularity, limits, expansions, and conditioning of y(c) and we propose algorithms (e.g., complex extrapolation, power method on a modified matrix etc.) that may provide an efficient way to compute PageRank also with c close or equal to 1. An interpretation of the limit vector Nv and a related critical discussion on the model, on its adherence to reality, and possible ways for its improvement, represent the contribution of the paper on modeling issues. © 2010 Elsevier B.V. All rights reserved.