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

BibTeX | DublinCore | EndNote | HTML |

| 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: | Techreport (Technical Report) | |
---|---|---|

Uncontrolled Keywords: | pagerank | |

Subjects: | Miscellaneous | |

Projects: | Miscellaneous | |

Related URLs: | Project Homepage, Project Homepage, Project Homepage | http://infolab.stanford.edu/, http://infolab.stanford.edu/, http://www-nlp.stanford.edu/ |

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