Research Of Pagerank Algorithm Based On Link Matrix Analysis

With the continuous development of society and the continuous advancement of science and technology,more and more people have shifted the main way of obtaining information from reading newspapers,televisions,and official websites to search engine tools.In order to meet the growing online search needs for us,research on webpage ranking models has become increasingly active.PageRank algorithm,as a well-known webpage ranking algorithm,can be regarded as a problem of solving the eigenvector corresponding to the maximum eigenvalue of the Google matrix,essentially.Taking the PageRank algorithm and its improved algorithms as the research purposes,using the link matrix analysis and Krylov subspace method as the starting point,the fast calculation technology of the PageRank problem is researched in this paper.The main research contents of this paper include two parts.In the first part,we proposed the Arnoldi-PET algorithm.This algorithm has improved the excellent Power-Arnoldi algorithm,which is an algorithm to solve the PageRank problem.We can view the Arnoldi-PET algorithm as a variant of Power-Arnoldi algorithm,that is,a matrix-based trace extrapolation strategy is introduced in the algorithm.The power iterative method is cheap and easy to implement,however,the convergence rate is very slow when the damping factor is close to one.The power iteration method based on matrix trace(PET)is an improvement of the power iteration.We know that the Krylov subspace method is very effective for solving the eigenvectors of large sparse matrices.Compared with the direct iterative methods,it only requires a fewer iterations.With the continuous development of network,as a typical large-scale sparse matrix,the magnitude of the Google matrix dimension becomes larger.Obviously,none of the above methods can efficiently meet the needs.Based on this acknowledge,we have proposed the Arnoldi-PET algorithm by combining the thick restarted Arnoldi algorithm with the PET algorithm,which accelerates the convergence rate of the PageRank problem through an effective iteration strategy.In the construction of Arnoldi-PET algorithm,the PET algorithm is deformed according to the convergence rate of the power iteration,that is,we constructe new parameters to control the run of power iteration in the PET algorithm.Then,some restart parameters are used to control the conversion of the PET algorithm and the thick restarted Arnoldi algorithm.In this paper,the implementation and convergence of the Arnoldi-PET algorithm has been analyzed in detail.Numerical experiments on several examples has been used to illustrate the effectiveness.In the second part,we proposed the GArnoldi-PET algorithm.This algorithm is a further research to Arnoldi-PET algorithm based on the weighted inner product.Similar to the construction mechanism of the Arnoldi-PET algorithm,the new algorithm is a periodic combination of the adaptive generalized Arnoldi algorithm(A-Arnoldi)and the PET algorithm.In order to further improve the convergence rate of PageRank computations,we adaptively change the weight vector according to the residual vector in outer iteration.In this paper,through the numerical experiments on several examples,we see its further optimization relative to the Arnoldi-PET algorithm.Besides,the implementation and convergence of the GArnoldi-PET algorithm has been analyzed in detail.