# The Condition Number of the PageRank Problem

Kamvar, Sepandar and Haveliwala, Taher (2003) The Condition Number of the PageRank Problem. Technical Report. Stanford InfoLab.

 BibTeX DublinCore EndNote HTML

 Preview
PDF
41Kb

## Abstract

We determine analytically the condition number of the PageRank problem. Specifically, we prove the following statement: "Let $P$ be an $n \times n$ row-stochastic matrix whose diagonal elements $P_{ii}=0$. Let $c$ be a real number such that $0 \leq c < 1$. Let $E$ be the $n \times n$ rank-one row-stochastic matrix $E=\vec{e}\vec{v}^T$, where $\vec{e}$ is the n-vector whose elements are all $e_i=1$, and $\vec{v}$ is an n-vector that represents a probability distribution. Define the matrix $A=[cP + (1-c)E]^T$. The problem $A\vec{x}=\vec{x}$ has condition number $\kappa=(1+c)/(1-c)$." This statement has implications for the accuracy to which PageRank can be computed, currently and as the web scales. Furthermore, it provides a simple proof that, for values of $c$ that are used by Google, small changes in the link structure of the web do not cause large changes in the PageRanks of pages of the web.

Item Type: Uncontrolled Keywords: Techreport (Technical Report) pagerank Miscellaneous Miscellaneous Project Homepage, Project Homepage, Project Homepage http://infolab.stanford.edu/, http://infolab.stanford.edu/, http://www-nlp.stanford.edu/ 597 Import Account 19 Jun 2003 17:00 24 Dec 2008 10:14