Google PageRanking problem: The model and the analysis |
| |
Authors: | Antonio Cicone |
| |
Institution: | a Dipartimento di Matematica, Università degli Studi di L’Aquila, Via Vetoio, Loc. Coppito, 67100 L’Aquila, Italy b Dipartimento di Fisica e Matematica, Università dell’Insubria - Sede di Como, Via Valleggio 11, 22100 Como, Italy |
| |
Abstract: | 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<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)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. |
| |
Keywords: | 65F10 65F15 65Y20 15A18 15A21 15A51 |
本文献已被 ScienceDirect 等数据库收录! |
|