A preconditioning approach to the Pagerank computation

Abstract

Some spectral properties of the transition matrix of an oriented graph indicate the preconditioning of Euler-Richardson (ER) iterative scheme as a good way to compute efficiently the vertexrank vector associated with such graph. We choose the preconditioner from an algebra $\mathcal U$ of matrices, thereby obtaining an ER-$\mathcal U$ method, and we observe that ER-$\mathcal U$ can outperform ER in terms of rate of convergence. The proposed preconditioner can be updated at a very low cost whenever the graph changes, as is the case when it represents a generic set of information. The particular $\mathcal U$ utilized requires a surplus of operations per step and memory allocations, which make ER-$\mathcal U$ superior to ER for not too wide graphs. However, the observed high improvement in convergence rate obtained by preconditioning and the general theory developed, are a reason for investigating different choices of $\mathcal U$, more efficient for huge graphs.

Please cite this work as:

@article{tudisco2011preconditioning,
  title={A preconditioning approach to the pagerank computation problem},
  author={Tudisco, Francesco and Di Fiore, Carmine},
  journal={Linear Algebra and its Applications},
  volume={435},
  number={9},
  pages={2222--2246},
  year={2011},
  publisher={Elsevier}
}

Keywords: Pagerank Iterative methods Preconditioning Eigenvalues Fast discrete transforms matrix algebras