Google PageRanking problem: The model and the analysis
Google PageRanking problem: The model and the analysis
复制标题
DOI：
10.1016/j.cam.2010.02.005
复制
发表时间：
2010-10
期刊：
影响因子：
--
通讯作者：
A. Cicone;S. Capizzano
中科院分区：
文献类型：
--
作者：
A. Cicone;S. Capizzano
当G是基本（随机）Google矩阵，c是真实的参数，使得0<c<1，v是非负概率向量，e是全1向量时，分析了Web超链接矩阵G（c）=cG+（1−c）evT的谱结构和Jordan结构.典型的研究在很大程度上依赖于非负矩阵、正矩阵和随机矩阵的特殊性质。存在唯一的非负向量y（c）使得y（c）TG（c）=y（c）T且y（c）Te=1。这个PageRank向量y（c）可以通过幂方法有效地计算。我们考虑一个正方形复矩阵A和非零复向量x和v，使得Ax=λx和v <$x=1。我们使用标准的矩阵分析工具来确定A（c）=cA+（1−c）λxv <$作为复变量c的函数的特征值、Jordan块和一个特殊的左λ-特征向量。如果λ是A的半单特征值，则存在唯一确定的投影N使得对于所有v，limc→ 1 y（c）=Nv;如果λ不是半单的，则对于某些v，这个极限可能不存在。作为我们的结果的一个特殊情况，我们得到了一个复杂的模拟网页超链接矩阵G（c）与一个复杂的参数c。我们研究了y（c）的正则性、极限、扩展和条件，并提出了算法（例如， 复外推法、修正矩阵上的幂方法等）这也可以提供计算PageRank有效方式，其中c接近或等于1。解释的极限向量NV和相关的关键讨论的模型，其坚持现实，并可能的方式，其改进，代表的贡献，该文件的建模问题。
The spectral and Jordan structures of the Web hyperlink matrix G(c)=cG+(1−c)evThave 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)Tand 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.