Name
Abstract | ||
|---|---|---|
We present a stationary iterative scheme for PageRank computation. The algorithm is based on a linear system formulation of the problem, uses inner/outer iterations, and amounts to a simple preconditioning tech- nique. It is simple, can be easily implemented and parallelized, and requires minimal storage overhead. Convergence analysis shows that the algorithm is effective for a crude in ner tolerance and is not particularly sensitive to the choic e of the parameters involved. Numerical examples featuring matrices of dimensions up to approximately 107 confirm the analytical results and demonstrate the accelerated convergence of the algorithm compared to the power method. 1. Introduction. PageRank (13) is a method for ranking Web pages whereby a page's 'importance' (or ranking) is determined according to the li nk structure of the Web. This model has been used by Google as part of its search engine technology. The exact ranking techniques and calculation methods used by Google today are no longer public information, but the PageRank model has taken on a life of its own and has received considerable attention in the scientific community in the last few years. PageRank is essentially the stationary distribution vector of a Markov chain whose transition matrix is a convex combination of the matrix associated with the Web link graph and a certain rank-1 matrix. A key parameter in the model is the damping factor, a scalar denoted henceforth by α that determines the weight given to the Web link graph in the model. Due to the great size and sparsity of the matrix, methods based on decomposition are considered infeasible; instead, iterative methods are used, where the computation is dominated by matrix-vector products. Detailed descriptions of the problem and available algorithms can be found, for example, in (3, 11). In this paper, we propose and investigate a new algorithm for the PageRank problem. It uses the linear system formulation and involves inner/outer iterations. The proposed tech- nique is based on the observation that in general, the smaller the damping factor is, the easier it is to solve the problem. Hence we apply an iterative scheme in which each iteration re- quires solving another linear system which is similar in its algebraic structure to the original, but with a lower damping factor. In essence, what is proposed here is a simple precondition- ing approach that exploits the spectral properties of the ma trix involved. We use a technique of inexact solves, whereby the inner iteration is solved onl y to a crude tolerance. The algo- rithm is just a few lines long, and can be implemented and parallelized in a straightforward fashion. |
Year | Venue | Keywords |
|---|---|---|
2007 | Web Information Retrieval and Linear Algebra Algorithms | inner/outer iterations,damping factor,pagerank,power method,stationary method,web pages,markov chain,search engine,convex combination,linear system,iteration method,stationary distribution,transition matrix |
Field | DocType | Citations |
PageRank,Linear system,Convex combination,Iterative method,Matrix (mathematics),Computer science,Markov chain,Algorithm,Google matrix,Power iteration | Conference | 0 |
PageRank | References | Authors |
0.34 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrew P. Gray | 1 | 28 | 1.69 |
| CHEN GREIF | 2 | 321 | 43.63 |
| Tracy Lau | 3 | 28 | 1.69 |