Haveliwala, Taher and Kamvar, Sepandar (2003) *The Second Eigenvalue of the Google Matrix.* Technical Report. Stanford.

BibTeX | DublinCore | EndNote | HTML |

| PDF 72Kb |

## 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.

Item Type: | Techreport (Technical Report) | |
---|---|---|

Uncontrolled Keywords: | PageRank, eigenvalue, markov chain | |

Subjects: | Computer Science Computer Science > Data Mining Computer Science > Databases and the Web Miscellaneous | |

Projects: | Miscellaneous | |

Related URLs: | Project Homepage, Project Homepage, Project Homepage | http://infolab.stanford.edu/, http://infolab.stanford.edu/, http://www-nlp.stanford.edu/ |

ID Code: | 582 | |

Deposited By: | Import Account | |

Deposited On: | 10 Mar 2003 16:00 | |

Last Modified: | 24 Dec 2008 10:03 |

## Download statistics

Repository Staff Only: item control page