Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (16): 56-59.DOI: 10.3778/j.issn.1002-8331.2009.16.015

• 研究、探讨 • Previous Articles     Next Articles

PageRank algorithm optimization and improvement

WU Jia-qi,TAN Yong-ji   

  1. School of Mathematical Science,Fudan University,Shanghai 200433,China
  • Received:2008-04-08 Revised:2008-07-30 Online:2009-06-01 Published:2009-06-01
  • Contact: WU Jia-qi



  1. 复旦大学 数学科学学院,上海 200433
  • 通讯作者: 吴家麒

Abstract: The original PageRank algorithm uses the Power Method to compute successive iterations that converge to the principal eigenvector of the Markov matrix representing the Web link graph.Authors use the sparse of the Google matrix P in the iterative matrix A=[CP+(1-cE]T,optimize the computation of each iteration and reduce storage space.Linear Extrapolation Method is an adjusted extrapolation method,which is proposed based on the Power Method.It utilizes the property of the second eigenvalue of the Google matrix to acheive the high rate convergence in the computing performance of Power Method.Therefore,the computing time is shortened without extra space storage.After some simulation work,the theoretical proof can be verified by the satisfactory practical result.

摘要: 在PageRank算法中是使用乘幂法对网络链接图的Markov矩阵进行迭代计算,利用迭代矩阵A=[CP+(1-cE]T中Google矩阵P的稀疏性,优化每次迭代的计算量并且减少空间存储量。在乘幂法证明理论基础上,提出了一种修正的外推方法称为线性外推法,并且利用Google矩阵的第二特征值的性质,使得在乘幂法的计算过程中达到快速收敛。从而在不增加空间存储的基础上缩短计算时间。最后结合实际数据测试,说明理论推导的结果达到了良好的实际使用效果。