Google PageRanking problem: The model and the analysis

✍ Scribed by Antonio Cicone; Stefano Serra-Capizzano

• Book ID: 104007057
• Publisher: Elsevier Science
• Year: 2010
• Tongue: English
• Weight: 731 KB
• Volume: 234
• Category: Article
• ISSN: 0377-0427
• DOI: 10.1016/j.cam.2010.02.005

✦ Synopsis

The spectral and Jordan structures of the Web hyperlink matrix G(c) = cG+(1-c)ev T have been analyzed when G is the basic (stochastic) Google matrix, c is a real parameter such that 0 < c < 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) T G(c) = y(c) T and y(c) T e = 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 lim c→1 y(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.