title: The Condition Number of the PageRank Problem
creator: Kamvar, Sepandar
creator: Haveliwala, Taher
subject: Miscellaneous
description: 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.
publisher: Stanford InfoLab
date: 2003-06-20
type: Techreport
type: NonPeerReviewed
format: application/pdf
identifier: http://ilpubs.stanford.edu:8090/597/1/2003-36.pdf
identifier: Kamvar, Sepandar and Haveliwala, Taher (2003) The Condition Number of the PageRank Problem. Technical Report. Stanford InfoLab.
relation: http://ilpubs.stanford.edu:8090/597/