A preconditioning approach to the pagerankudcomputation problem

摘要

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 U of matrices, thereby obtaining an ERU method, and we observe that ERU can outperform ER in terms of rate of convergence. The proposed preconditioner can be updated at a very low cost whenever the graph changs, as is the case when it represents a generic set of information. The particular U utilized requires a surplus of operations per step and memory allocations, which make ERU superior to ER for not too wide graphs. However , the observed high improvement in convergence rate obtained by preconditining and the general theory developed, are a reason for investigating different choices of U, more efficient for huge graphs.