文档介绍：武汉纺织大学
毕业设计[ 论文]
题目: 对Google搜索引擎中网页排序算法的研究
摘要
搜索引擎技术的发展是随着电子技术不断进步的信息数字化和数据网络化的必然产物,网页排序算法一直是搜索引擎的核心技术之一。Google 搜索引擎依靠其PageRank机制及收敛算法一直处于该领域的领先地位。本文深入研究PageRank排名算法,从数学的角度来看,发现它能够通过计算一个基于网络连接图的转移概率矩阵的主特征向量(PageRank 向量)实现。同时针对网络的复杂情形,对转移概率矩阵作出了修正并分析了修正矩阵的特性。给出了计算主特征向量的数值解法-幂法。利用修正矩阵中链接矩阵的稀疏性,,给出了一种较新的加速收敛的外推法-The Vector -algorithm,最后结合一个现实中的复杂网络的数据测试,验证了该外推法的良好的实际运用效果。
关键词:搜索引擎;PageRank;转移概率矩阵;主特征向量;加速收敛;外推法;幂法;The Vector -algorithm
ABSTRACT
With the development of electronic technology, the search engine technology is ing more and more important. Google search engine keeps on the top by its PageRank and convergence algorithm. We will see that, from the mathematical point of view, it could be solved puting the principal eigenvector (the PageRank vector) of a Transition Probability Matrix of the Web. According to the Web’plexity, we will give the modified matrix , and also analyze its characteristics. We will study the mathematical properties of the power method puting the PageRank vector. We use the sparse of the Web matrix in the iterative matrix , optimize putation of each iteration and reduce its storage space. The Vector -algorithm, an extrapolation algorithm for vector sequences, is proposed based on the power method. It will achieve the higher rate convergence in puting performance of power method. Finally, some simulation work of the theoretical proof will be verified by the satisfied practical results.
Keywords:Search Engine; PageRank; Transition Probability Matrix; principal eigenvector; convergence and acceleration; extrapolation; power method; The Vector -algorithm
目录
1. 绪论 1
1
PageRank简介 2
本文的主要内容和结构安排 3
2. 基本的PAGERANK模型 4
PageRank的基本概念 4
PageRank的基本模型 5
存在的问题 8
(Dangling Nodes) 8
8
对上述问题的修正 9
对出现悬点的修正 9
对的修正 10
3. 对PAGERANK问题的求解方法 10
幂法 11
在PageRank上的幂法 12
12
幂法的伪代码 13
4. 幂法加速 14
外推法 14