导　　师： 范金燕

学科专业： G0102

授予学位： 硕士

作　　者： ;

机构地区： 上海交通大学

摘　　要： 本文介绍了google搜索引擎技术的组成模块，分析了排序模块所使用的pagerank模型并进行了模型在有向有权网络中稳定性的数值仿真试验，得到了网页排序结果对网络中权值变化敏感的结论。通过分析和比较计算pagerank向量不同思路的算法：power算法、gmres算法、块结构算法、非悬虚节点算法、自适应算法、power-arnoldi算法和层结构等算法的优缺点、适用条件以及各算法的时间和空间消耗，提出了以排名波动率作为衡量算法排名准确性的参数。在非悬虚节点算法的基础上，通过改用由入度信息构成的迭代初始向量、将排名波动率加入停机准则给出了计算pagerank向量的新算法。数值试验表明新算法在保证“重要网页”排名准确的前提下，较大幅度的减少了计算时间和存储空间需求。新算法在时间、空间和结果准确性三个方面取得了平衡，实现了优化算法的目的。 This paper briefly introduced the structure of Google search engine technology and analyzed the stability of the ranking module for directed and weighted network, finding out the rank of the page was sensitive to the weight disturbance of the network. Particularly, several popular algorithms were theoretically analyzed and compared, including Power algorithm, GMRES algorithm, Block algorithm, Non-dangling algorithm, Adaptive algorithm, Power-Arnoldi algorithm and hierarchical algorithm. Not only time-space consumption parameters, but also a new rank accuracy parameter were proposed to evaluate the above algorithms. Based on Non-dangling algorithm, our algorithm adopted in-degree information of each web page as a new initial iteration vector and added rank accuracy parameter as a new stop criterion. Numerical tests indicated that our algorithm could reduce the time-space consumption and keep those important pages’rank accuracy at the same time. Our algorithm could balance the time-space consumption and rank accuracy, which optimized the existing algorithms.

关 键 词： 搜索引擎 向量 网页排序

分 类 号： [TP393.09]

领　　域： [自动化与计算机技术] [自动化与计算机技术]