PageRank算法的优化和改进  

PageRank algorithm optimization and improvement

作　　者：吴家麒[1] 谭永基[1] 

机构地区：[1]复旦大学数学科学学院,上海200433

出　　处：《计算机工程与应用》2009年第16期56-59,共4页Computer Engineering and Applications

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]