Computing PageRank Problems Based On Anderson Extrapolation Method

As the core issue of search engine technology,PageRank problems have received great attention in recent decades.As the damping factor approaches 1,the computing speed of the classical power method gradually decreases.Moreover,the effectiveness of the newly proposed algorithm in recent years is not ideal compared with the power method for solving the PageRank problems with small damping factor such as α=0.85.In order to improve the speed of solving the PageRank problem,this paper proposes three new algorithms based on the Anderson extrapolation method which is used for accelerating the solution of fixed-point iterative problems.The principle of Anderson extrapolation is:first find the constraint vector of the least square problem formed by the following two conditions:(1)the sum of the elements of the constraint vector is 1;(2)the 2-norm of the matrix-vector product formed by the m0+1(m0∈N)residual vectors and the constraint vector is the smallest.Then the elements in the constraint vector are used as coefficients and combined with previous m0+1 iterative solutions linearly to obtain a new approximate solution.Anderson extrapolation is also called Anderson(m0)extrapolation.As the parameter m0 increases,the time and storage cost to solve the least squares problem in the Anderson(m0)extrapolation method are also greater.Therefore,the parameter m0 should be small.In this paper,we take m0=1.For the PageRank problems with a small damping factor,we combine the Ander-son(1)extrapolation with the classical power method to develop the AP algorithm.Specif-ically,first we run the power method for a few times,next treat the power iteration as a fixed-point iteration problem and then apply the Anderson(1)extrapolation method.After that,we give a rigorous convergence analysis of the AP algorithm.Numerical experiments have studied the influence of the parameter maxit on the AP algorithm.Moreover,the ex-perimental results show that the AP algorithm has a better performance than the power method when damping factor is small.Then in order to optimize the AP algorithm,we take the advantage of the Krylov subspace method that can quickly improve the solution speed,and periodically combine the thick restarted Arnoldi algorithm with the AP algo-rithm to propose the Arnoldi-AP algorithm.After the convergence analysis,the numerical simulation experiment results prove the effectiveness of the new algorithm for solving the PageRank problems with a large damping factor.Finally,based on the design idea of Arnoldi-AP algorithm,this paper uses Anderson(1)extrapolation method to accelerate Arnoldi-Inout algorithm and propose the AIOA algorithm.After the convergence anal-ysis of the new algorithm,we conduct a two-part numerical experiment.The first part discusses the selection of the parameter maxit,and the second part verifies the effective-ness of the new algorithm for solving PageRank problem with a large damping factor.