| Available via | http://dbpubs.stanford.edu/pub/2003-36 |
|
Submitted on |
20th of June 2003 |
|
Author |
Kamvar, Sepandar; Haveliwala, Taher |
|
Title |
The Condition Number of the PageRank Problem |
|
Date of publication |
20th of June 2003 |
|
Citation |
Kamvar, Sepandar; Haveliwala, Taher. The Condition Number of the PageRank Problem, |
|
Number of pages |
4 |
|
Language |
English |
|
Project |
Stanford InfoLab; Database Group; Natural Language Processing Group |
|
Type |
Other |
|
Subject group |
Miscellaneous |
|
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. |
|
Keywords |
pagerank |
| Fulltext source |
Postscript (ps, ps.gz, ps.zip)
PDF (pdf, pdf.gz, pdf.zip)
| Management of the document by | siroker@db.stanford.edu
| |