The Second Eigenvalue of the Google Matrix
The Second Eigenvalue of the Google Matrix
复制标题
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Taher H. Haveliwala;S. Kamvar
中科院分区：
文献类型：
--
作者：
Taher H. Haveliwala;S. Kamvar
我们解析地确定了Google用于计算PageRank的网页超链接矩阵的第二本征值的模数。具体地，我们证明了下列命题：对任意矩阵$A=[Cp+(1-c)E]^T$，其中$P$是$n\x n$行随机矩阵，$E$是严格正的$n\x n$秩单行随机矩阵，$0\leq c\1$，$A$的第二个特征值有模$|\lambda_2|\leq c$。此外，如果$P$至少有两个不可约闭子集，则第二本征值$\lambda_2=c$。这一陈述对标准PageRank算法随着Web规模的收敛速度、PageRank对Web链接结构扰动的稳定性、Google垃圾邮件发送者的检测以及加快PageRank的算法设计具有一定的影响。
We determine analytically the modulus of the second eigenvalue for the web hyperlink matrix used by Google for computing PageRank. Specifically, we prove the following statement: ``For any matrix $A=[cP + (1-c)E]^T$, where $P$ is an $n \times n$ row-stochastic matrix, $E$ is a strictly positive $n \times n$ rank-one row-stochastic matrix, and $0 \leq c \leq 1$, the second eigenvalue of $A$ has modulus $|\lambda_2| \leq c$. Furthermore, if $P$ has at least two irreducible closed subsets, the second eigenvalue $\lambda_2 = c$.'' This statement has implications for the convergence rate of the standard PageRank algorithm as the web scales, for the stability of PageRank to perturbations to the link structure of the web, for the detection of Google spammers, and for the design of algorithms to speed up PageRank.