基于链接矩阵分析的PageRank算法研究

发布时间：2024-04-19 22:44

　　随着社会的不断发展,科学技术的不断进步,越来越多的人们已经把获取信息的主要途径从看报纸、电视和直接上指定目标的官方网站转向了搜索引擎工具。为了适应人们日益增长的网上搜索需求,对于网页排序模型的研究越来越活跃。PageRank算法作为一个著名的网页排序算法,其本质上可以视为谷歌矩阵的主特征向量的求解问题。本文以PageRank算法及其快速算法为研究方向,以链接矩阵分析和Krylov子空间法为切入点,研究了PageRank问题的快速计算方法。本文的主要的研究内容分为了两部分。在第一部分中,我们提出了Arnoldi-PET算法。Power-Arnoldi算法是解决PageRank问题的一种非常优秀的算法。Arnoldi-PET算法可以视为Power-Arnoldi算法的一种变形算法,即在该算法中引入基于矩阵的迹的外推策略。幂迭代方法不仅计算成本较低而且易于实现,但是当阻尼因子趋近于1时,其收敛速度非常慢。基于矩阵的迹的幂迭代方法(PET)是幂迭代方法的一种改进。Krylov子空间法对于求解大型稀疏矩阵的特征向量非常有效。相较于幂迭代等方法,其通常在较少的迭代次数下就能收敛。谷歌矩阵作为一个典...

【文章页数】：56 页

【学位级别】：硕士

【部分图文】：

图3-1矩阵web-Stanford的残差图

电子科技大学硕士学位论文22表3-1web-Stanford的数值实验结果-valueAssessmentcriteriaPETPower-ArnoldiArnoldi-PET=0.99IT716223202Mv716303293CPU10.93227.29646.5764=0.....

图3-2矩阵StanfordBerkeley的残差图

第三章用于计算PageRank问题的Arnoldi-PET算法23表3-2Stanford_Berkeley的数值实验结果-valueAssessmentcriteriaPETPower-ArnoldiArnoldi-PET=0.99IT649298255Mv649387337C....

图3-3矩阵wikipedia-20051105的残差图

第三章用于计算PageRank问题的Arnoldi-PET算法25Power-Arnoldi算法在单次迭代过程中需要的存储量与计算成本高于PET算法。原因可能是当Arnoldi类方法的子空间维数较高时，其在计算成本上会增高。即使在Power-Arnoldi算法的迭代次数较少的情况....

图4-1矩阵web-Stanford的残差图

电子科技大学硕士学位论文36迹。本算例的实验参数设定为m5，p3，maxit=6，1m=40。图4-1矩阵web-Stanford的残差图表4-2Stanford_Berkeley的数值实验结果-valueAssessmentcriteriaArnoldi-PEIA-Arnold....

本文编号：3958486