The Condition Number of the PageRank Problem

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.