%0 Report
%9 Technical Report
%A Kamvar, Sepandar
%A Haveliwala, Taher
%D 2003
%F ilprints:597
%I Stanford InfoLab
%K pagerank
%T The Condition Number of the PageRank Problem
%U http://ilpubs.stanford.edu:8090/597/
%X 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.