 when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-10693
URL:

### Google Pageranking Problem: The Model and the Analysis

 pdf-format:

### Abstract

Let \$A\$ be a given \$n\$-by-\$n\$ complex matrix with eigenvalues \$lambda
,lambda _{2},ldots ,lambda _{n}\$. Suppose there are nonzero vectors \$%
x,yin mathbb{C}^{n}\$ such that \$Ax=lambda x\$, \$y^{ast }A=lambda y^{ast
}\$, and \$y^{ast }x=1\$. Let \$vin mathbb{C}^{n}\$ be such that \$v^{ast }x=1\$%
, let \$cin mathbb{C}\$, and assume that \$lambda
eq clambda _{j}\$ for
each \$j=2,ldots ,n\$. Define \$A(c):=cA+(1-c)lambda xv^{ast }\$. The eigenvalues of \$%
A(c)\$ are \$lambda ,clambda _{2},ldots ,clambda _{n}\$. Every
left eigenvector of \$A(c)\$ corresponding to \$lambda \$ is a scalar multiple of \$%
y-z(c)\$, in which the vector \$z(c)\$ is an explicit rational
function of \$c\$. If a standard form such as the Jordan canonical
form or the Schur triangular form is known for \$A\$, we show how to
obtain the corresponding standard form of \$A(c)\$.

The web hyper-link matrix \$G(c)\$ used by Google for computing the
PageRank is a special case in which \$A\$ is real, nonnegative, and
row stochastic (taking into consideration the dangling nodes),
\$cin (0,1)\$, \$x\$ is the vector of all ones, and \$v\$ is a positive
probability vector. The PageRank vector (the normalized dominant
left eigenvector of \$G(c)\$) is therefore an explicit rational
function of \$c\$. Extrapolation procedures on the complex field may
give a practical and efficient way to compute the PageRank vector
when \$c\$ is close to \$1\$.

A discussion on the model, on its adherence to reality, and on
possible variations is also considered.

### BibTeX - Entry

```@InProceedings{serracapizzano:DagSemProc.07071.10,
author =	{Serra Capizzano, Stefano},
title =	{{Google Pageranking Problem: The Model and the Analysis}},
booktitle =	{Web Information Retrieval and Linear Algebra Algorithms},
pages =	{1--34},
series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN =	{1862-4405},
year =	{2007},
volume =	{7071},
editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address =	{Dagstuhl, Germany},
URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/1069},
URN =		{urn:nbn:de:0030-drops-10693},
doi =		{10.4230/DagSemProc.07071.10},
annote =	{Keywords: Google matrix, rank-one perturbation, Jordan canonical form, extrapolation formulae.}
}```

 Keywords: Google matrix, rank-one perturbation, Jordan canonical form, extrapolation formulae. Seminar: 07071 - Web Information Retrieval and Linear Algebra Algorithms Issue date: 2007 Date of publication: 28.06.2007

DROPS-Home | Fulltext Search | Imprint | Privacy 