Serra Capizzano, Stefano
Google Pageranking Problem: The Model and the Analysis
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+(1c)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 $%
yz(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 hyperlink 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:DSP:2007:1069,
author = {Stefano Serra Capizzano},
title = {Google Pageranking Problem: The Model and the Analysis},
booktitle = {Web Information Retrieval and Linear Algebra Algorithms},
year = {2007},
editor = {Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
number = {07071},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Internationales Begegnungs und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2007/1069},
annote = {Keywords: Google matrix, rankone perturbation, Jordan canonical form, extrapolation formulae.}
}
Keywords: 

Google matrix, rankone perturbation, Jordan canonical form, extrapolation formulae. 
Seminar: 

07071  Web Information Retrieval and Linear Algebra Algorithms

Issue date: 

2007 
Date of publication: 

28.06.2007 