Google PageRanking problem: The model and the analysis

[摘要] 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 = lambda x and v*x = 1. We use standard matrix analytic tools to determine the eigenvalues, the Jordan blocks, and a distinguished left lambda-eigenvector of A(c) = cA + (1 - c)lambda xv* as a function of a complex variable c. If lambda 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 lambda 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. (C) 2010 Elsevier B.V. All rights reserved.

[发布日期] 2010-10-01

[效力级别]  Proceedings Paper

[关键词] Google matrix;PageRanking;Surfing model;Rank-one perturbation;Brauer's Theorem;Jordan canonical form;Principle of biorthogonality;Extrapolation formulae