一种求解PageRank问题的修正乘幂法

在现代搜索引擎技术中,PageRank算法发挥了非常重要的作用,通常用幂法计算描述Web链接图的Google矩阵的特征向量,然而当最大特征值与次大特征值不能很好地分离时,幂法的表现较差,主要原因是当阻尼系数接近于1时,算法收敛速度会很慢.因此开发较原有幂法更高效的算法是非常有价值的.本文提出了一个针对PageRank问题的改进幂法,数值实验表明了新算法的有效性.

A modified power method for the PageRank problem

The PageRank algorithm plays a very important role in modern search engine technology,and it makes use of the power method to compute the principal eigenvector of the Google matrix representing the weblink graph. However, when the largest eigenvalue cannot be well separated from the second one, the power method may per?form poorly. This happens when the damping factor is sufficiently close to 1. Therefore, it is worth developing new techniques that are more sophisticated than the power method. In this paper, we propose an improved version of the power method for computing PageRank. Numerical experiments illustrate the efficiency and convergence behavior of the new algorithm.