Search Results

Documents authored by Serra Capizzano, Stefano


Document
Google Pageranking Problem: The Model and the Analysis

Authors: Stefano Serra Capizzano

Published in: Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007)


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.

Cite as

Stefano Serra Capizzano. Google Pageranking Problem: The Model and the Analysis. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@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/entities/document/10.4230/DagSemProc.07071.10},
  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.}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail