Google PageRanking problem: the model and the analysis

The spectral and Jordan structures of the Web hyperlink matrix $G(c) = cG + (1-c)ev^T$ have been analyzed when $G$ is the basic (stochastic) Google matrix, $c$ is a real parameter such that $0<c<1$, $v$ is a nonnegative probability vector, and $e$ is the all-ones vector. Typical studies have relied heavily on special properties of nonnegative, positive, and stochastic matrices. There is a unique nonnegative vector $y(c)$ such that $y^TG(c)=y^T$ and $y(c)^T e=1$. This \emph{PageRank} vector $y(c)$ can be computed effectively by the power method. We consider a square complex matrix $A$ and nonzero complex vectors $x$ and $v$ such that $Ax=\lambda x$ and $v^*x=1$. We use standard matrix analytic tools to determine the eigenvalues, the Jordan blocks, and a distinguished left $\lambda$-eigenvector of $A(c)=cA + (1-c)\lambda xv^*$ as a function of a complex variable $c$. If $\lambda$ is a semisimple eigenvalue of $A$, there is a uniquely determined projection $N$ such that $\displaystyle\lim_{c\rightarrow 1}y(c)=Nv$ for all $v$; this limit may fail to exist for some $v$ if $\lambda$ is not semisimple. As a special case of our results, we obtain a complex analog of PageRank for the Web hyperlink matrix $G(c)$ with a complex parameter $c$. We study regularity, limits, expansions, and conditioning of $y(c)$ and we propose algorithms (e.g., complex extrapolation, power method on a modified matrix etc.) that may provide an efficient way to compute PageRank also with $c$ close or equal to $1$. An interpretation of the limit vector $Nv$ and a related critical discussion on the model, on its adherence to reality, and possible ways for its improvement, represent the contribution on modeling issues of the paper.