[ Pagewise preview ]
| Category | Value | ||
| Available via | http://dbpubs.stanford.edu/pub/2003-20 | ||
| Submitted on | 11th of March 2003 | ||
| Author | Haveliwala, Taher; Kamvar, Sepandar | ||
| Title | The Second Eigenvalue of the Google Matrix | ||
| Date of publication | 2003 | ||
| Published in | Stanford University Technical Report | ||
| Citation | Haveliwala, Taher; Kamvar, Sepandar. The Second Eigenvalue of the Google Matrix, Stanford University Technical Report | ||
| Number of pages | 8 | ||
| Language | English | ||
| Project | Stanford InfoLab; Database Group; Natural Language Processing Group | ||
| Type | Technical Report | ||
| Subject group | Computer Science; Data Mining; Databases and the Web; Miscellaneous | ||
| Abstract | 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. | ||
| Keywords | PageRank, eigenvalue, markov chain | ||
| Contact address |
taherh@cs.stanford.edu sdkamvar@stanford.edu | ||
| Fulltext source |
| Management of the document by | siroker@db.stanford.edu
| |
[ Pagewise preview ]