Stanford InfoLab Publication Server

The Condition Number of the PageRank Problem

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




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:Techreport (Technical Report)
Uncontrolled Keywords:pagerank
Related URLs:Project Homepage, Project Homepage, Project Homepage,,
ID Code:597
Deposited By:Import Account
Deposited On:19 Jun 2003 17:00
Last Modified:24 Dec 2008 10:14

Download statistics

Repository Staff Only: item control page