A new extrapolation method for PageRank computations

详细信息    查看全文

• 作者：Xueyuan Tan ^{tanxueyuan@njnu.edu.cn" class="auth_mail" title="E-mail the corresponding author}
• 关键词：PageRank ; Power method ; Extrapolation method ; Arnoldi-type algorithm ; Trace
• 刊名：Journal of Computational and Applied Mathematics
• 出版年：2017
• 出版时间：15 March 2017
• 年：2017
• 卷：313
• 期：Complete
• 页码：383-392
• 全文大小：895 K

文摘

The PageRank algorithm is widely considered these years because of its great significance in search engine technology and other scientific domains. Though the power method is the initial measure to settle the PageRank problem, it gives poor convergence when the damping factor is sufficiently close to g" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0377042716304034&_mathId=si23.gif&_user=111111111&_pii=S0377042716304034&_rdoc=1&_issn=03770427&md5=f996610d3db5d90f6c627114a1630b38" title="Click to view the MathML source">1gif" overflow="scroll">1. This difficulty encourages researchers to present improved iterative methods for accelerating PageRank computations. In this paper, a cheap and practical extrapolation approach which is determined by the trace of the Google matrix is proposed, and it is more attractive when combined with the well-known Arnoldi-type algorithm. Convergence analysis of our algorithms is given. Numerical examples illustrate the efficiency of these accelerated schemes.