论文部分内容阅读
互联网包含有海量网页,越来越多的用户通过搜索引擎寻找特定信息。Web信息检索的目的是在网页集合中找到与用户查询相关的所有网页,而网页评估算法将对这些网页进行评估后显示给用户。Google的PageRank算法通过对超链接结构的分析,有效地提高了搜索结果的排序质量。外推法(Extrapolation)是减少PageRank算法迭代次数的有效方法,而Aitken Extrapolation算法和基于特征值直接求解的算法是其典型代表。 Aitken Extrapolation算法使用Aitken变换以减少迭代次数,但Aitken变换在多数情况下无法确保算法收敛。为了弥补该算法的缺陷,本文在分析了该算法不稳定性的根源后提出了改进算法FNN-Aitken Extrapolation。与原算法相比,改进算法不频繁调用Aitken变换,而执行选择适当时机对Aitken变换调用一次的策略。理论分析和实验结果表明改进算法不仅能够弥补原算法的不稳定性而且通常比Power Method算法具有更少的迭代次数。 与Aitken Extrapolation算法相比,基于特征值求解的算法不借助Aitken变换,而通过特征值直接求解马尔可夫超链接矩阵的主特征向量,从理论上比Aitken Extrapolation算法更高效。然而基于特征值直接求解算法的迭代次数与参数d的选择密切相关,而参数d的确定目前无明显规律可寻。另一方面,Adaptive方法通过将马尔可夫超链接矩阵稀疏化以达到节省迭代时间的目的。本文将Adaptive方法分别与基于特征值直接求解算法和Aitken Extrapolation算法相结合,实验结果初步证明了这两个新算法能够缩短迭代时间。