毕业论文 对GOOGLE搜索引擎中网页排序算法的研究

1、武汉纺织大学 2010 届毕业设计论文武汉纺织大学毕毕 业业 设设 计计 论论 文文 题题 目目： 对对 Google 搜索引擎中网页排序算法的研究搜索引擎中网页排序算法的研究 武汉纺织大学 2010 届毕业设计论文摘 要搜索引擎技术的发展是随着电子技术不断进步的信息数字化和数据网络化的必然产物，网页排序算法一直是搜索引擎的核心技术之一。Google 搜索引擎依靠其 PageRank 机制及收敛算法一直处于该领域的领先地位。本文深入研究PageRank 排名算法，从数学的角度来看，发现它能够通过计算一个基于网络连接图的转移概率矩阵的主特征向量 (PageRank 向量)实现。同时针对网络的复v

2、杂情形,对转移概率矩阵作出了修正并分析了修正矩阵的特性。(1)PPE给出了计算主特征向量的数值解法-幂法。利用修正矩阵中链接矩阵的稀疏PP性，优化了幂法在迭代中的计算量并减少了存储空间.在幂法理论基础上，给出了一种较新的加速收敛的外推法-The Vector -algorithm，最后结合一个现实中的复杂网络的数据测试，验证了该外推法的良好的实际运用效果。关键词关键词：搜索引擎；PageRank；转移概率矩阵；主特征向量；加速收敛；外推法；幂法；The Vector -algorithm武汉纺织大学 2010 届毕业设计论文ABSTRACTWith the development of ele

3、ctronic technology, the search engine technology is becoming 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 by computing the principal eigenvector (the PageRank vector

4、) of a Transition Probability Matrix of the Web. According to the Webs complexity, we will give the modified matrix , and also analyze its (1)PPEcharacteristics. We will study the mathematical properties of the power method that computing the PageRank vector. We use the sparse of the Web matrix in t

5、he Piterative matrix , optimize the computation of each iteration and reduce its storage Pspace. The Vector -algorithm, an extrapolation algorithm for vector sequences, is proposed based on the power method. It will achieve the higher rate convergence in the computing performance of power method. Fi

6、nally, 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武汉纺织大学 2010 届毕业设计论文目 录1. 绪论

7、11.1 引言11.2 PAGERANK简介21.3 本文的主要内容和结构安排32. 基本的 PAGERANK 模型42.1 PAGERANK的基本概念42.2 PAGERANK的基本模型52.3 存在的问题82.3.1 悬点(Dangling Nodes)82.3.2 主特征向量空间()TL P不是一维的82.4 对上述问题的修正92.4.1 对出现悬点的修正92.4.2 对dim( ()2TL P的修正103. 对 PAGERANK 问题的求解方法103.1 幂法113.2 在 PAGERANK上的幂法123.2.1 初始优化 PageRank 矩阵123.2.2 幂法的伪代码13武汉纺织

8、大学 2010 届毕业设计论文4. 幂法加速144.1 外推法144.1.1 The vector -algorithm144.1.2 The vector -algorithm 伪代码155. 应用165.1 对简化的网络进行等级分析165.2 对一个现实的复杂网络进行分析186. 结语与展望20参考文献22武汉纺织大学 2010 届毕业设计论文1 绪论1.1 引言当前因特网上有大量站点正在不断地从广大用户当中搜索数据，并利用机器学习和统计方法从中获得需要的信息。Google 搜索引擎作为其中的佼佼者，它不仅可以利用网络链接对网页进行排名，而且当其广告被不同的用户选定时，它会持续搜集信息，这

9、使得 Google 能够更加有效地进行广告定位。它目前被公认为是全球规模最 大的搜索引擎，它提供了简 便人性化的各种免费服务，用户可以在很短的时间内 得到相关的搜索结果。 一个优秀的搜索引擎应该及时向用户提供所需要的最重要最有价值的网页信息并将其排在前面，然而这种及时，高效，高质量的显示结果必然需要一个强大的搜索算法给予支持。大家普遍相信，Google 从一个研究型项目迅速崛起为世界范围内最受欢迎的搜索引擎，这在很大程度上归功于它的 RageRank 网页排名机制及其收敛加速算法的进一步发展。这种基于链的网页排名的巧妙之处在于它把整个互联网当作了一个整体的结构来看待，这无意识的符合了系统论和整

10、体的观点。与以前的相比，以前的信息检索大多把每一个网页当作独立的个体对待，很多人当初只看重页面内容和查询关键词之间的相关性，忽略了页面之间的关系。当前，Google 搜索引擎比最初复杂、完善了许多。从系统的观点上来看，据 Google 最近检测，互联网上独立页面的数量超过了 1 万亿个并且发现互联网上每天新增加数十亿个网页1。Google 互联网搜索基础架构团队的软件工程师杰西阿尔帕特和尼桑哈贾吉在博客中写道， “我们没有索引这 1 万亿个网页中的每个页面因为许多页面都彼此相似，或代表自动生成的内容，这些对用户没多大意义。但令我们骄傲的是，我们拥有最完整的索引数据库。我们的目标是索引全球的数据

11、。”由此可以看出，当前的 Google 搜索引擎在信息采集上处于领先地位，其得到的庞大索引数据库不单纯追求网页链接的数量，同时采取了一些很有力的筛选和过滤措施。这也使得基于链分析的网页排序(PageRank)受人为控制因素大为减少或者说是微不足道的，并且响应速度快同时也不影响网页排名的质量。在武汉纺织大学 2010 届毕业设计论文2学术界, 这个网页排序算法被公认为是文献检索中最大的贡献之一，并且被很多大学引入了信息检索课程的教程。因此，对网页排序算法(PageRank 算法)的分析、探索、研究和应用具有重大的现实意义。1.2 PageRank 简介 PageRank 算法是由 Google

12、的创始人提出的，现在基于这一思路的各种变种已被所有大型搜索引擎采用。该算法为每个页面都赋予了一个指示页面重要程度的评价值。网页的重要性由指向该网页的所有其他网页的重要性和这些网页中所包含的链接数求得。理论上，PageRank（以 Google 创始人之一 Larry Page命名）计算的是某个人在任意次链接点击之后到达某一网页的可能性。如果某网页拥有来自其他比较热门网页的外部回指链接越多，人们无意间访问该网页的可能性也就越大。当然，如果用户始终不停地点击，那么他们终将到达每一个网页，但是大多数人在浏览一段时间之后都会停止点击。为了反映这一情况，PageRank 还使用了一个值为 0.85 的阻

13、尼因子(damping factor)，用以指示用户持续点击每个网页中链接的概率为 85%。在计算网站排名时， Pagerank 会将网站的外部链接数考虑进去。并不 是说一个网页的外部链接数越多其 页面评价值就越高， 若是这样的情形，一个网站 只需要尽可能获得最多的外部链接就可以了，有这种想法是错误的。 Google 看重一个网页上的外部链接数 ，但并不意味着你 能够不求策略地与任何网站建立 链接。这是由于 Google 并不是仅仅由网页的外部链接数来决定其等级 ，也会考虑其质量。 在此基础上也会考虑外部链接的数量。例如，对一个有一定 网页评价值的网页 X，若网页 Y 是它的唯一的外部链接，那

14、么 Google 就认为网页 X 将网页 Y 视做它最好的一个外部链接，从而会给你的网 页 Y 更多的分值。可是，如果网页 X 上已经有 39 个外部链接，那么 Google 就认为网页 X 只是将你的网页视做它第 40 个好的网站。因而你的外部链接站点上的外部链接数越多，你所能够得到的分值反而会越低。 可见 Google 搜索引擎排序是一个复杂问题，比最初复杂、完善 的多，但是网页排名在 Google 所有算法中依然 占有重要位置。当前几乎所有主要的网页搜索引擎都以链分析来改进搜索结果，PageRank武汉纺织大学 2010 届毕业设计论文3机制首当其冲。这对研究线性代数的学者来说的确是一件

15、兴奋的事，因为对于网页超链结构的运用是依据矩阵理论的基础而构建的。链分析及其底层的线性代数使网页搜索产生革命性巨变，一些基于幂法的收敛加速算法研究变得异常活跃，这令 1998 年之前的预链分析搜索在今天如此精准高效搜索面前黯然失色。1.3 本文的主要内容和结构安排当前的搜索引擎不得不做的三件事：1. 利用爬虫程序搜集页面文档，有时可能涉及针对特定网页的抓取2-在互联网上先从一小组网页开始，然后再根据网页内的链接逐步追踪其他的网页。2. 根据步骤 1 进行必要处理，为全文索引建立数据库，以便对相关的关键字或关键词进行高效检索。3. 根据某种评价方法如 PageRank 排名机制，对给定的查询条件

16、为网页进行评价，以便能在返回查询结果中将评价最高者排在最前面。本文将集中考虑第 3 步,即在假定索引数据库已经建立的基础上研究页面的等级排序问题。这也有利于集中于其核心思想的研究。本文所做工作主要分成三个部分：第一部分是在介绍 PageRank 基础知识的前提下，建立 PageRank 的基本模型，同时将针对各种不利情形对 PageRank 矩阵进行修正。第二部分主要针对第一部分提出的修正矩阵使用一定的数值解法解决 PageRank 的排序问题，在此基础上给出加速收敛的方法。第三部分是应用，将针对一现实中的网络验证第二部分提出的修正方法的合理性并给出收敛加速的效果图。本文结构安排如下，第二章介

17、绍 PageRank 的基本概念以及基本的PageRank 模型，包括它涉及到的基本概念、定义、定理和性质。第三章介绍 PageRank 问题的求解方法。给出了解决 PageRank 排序的数值方法幂法及其伪码。第四章在基于幂法的理论基础之上,给出一种加速收敛的外推法-The vector-algorithm 及其伪码。第五章是应用，结合一现实中的复杂网络进行测试。包括对模型的验证以及收敛加速的分析。最后是对本文的总结与展望。武汉纺织大学 2010 届毕业设计论文42 基本的 PageRank 模型21 PageRank 的基本概念 CAB图 2-1 简化网络结构图 网页级别(PageRank

18、):2001 年 9 月被授予美国专利，专利人是 Google 创始人之一拉里佩奇 PageRank 专利人拉里佩奇（Larry Page） 。因此，PageRank里的 page 不是指网页，而是指佩奇，即这个等级方法是以佩奇来命名的。它是Google 排名运算规则（排名公式）的一部分，是 Google 用于用来标识网页的等级/重要性的一种方法，是 Google 用来衡量一个网站的好坏的唯一标准。在揉合了诸如 Title 标识和 Keywords 标识等所有其它因素之后，Google 通过PageRank 来调整结果，使那些更具“等级/重要性”的网页在搜索结果中另网站排名获得提升，从而提高搜

19、索结果的相关性和质量。分数越高说明该网页越受欢迎（越重要） 。网络结构图(Structure Of The Web)：由页面作为图结点，页面之间的链接作为边的有向图。转移概率矩阵：矩阵各元素都是非负的，并且各行元素之和等于 1，各元素用概率表示，在一定条件下是互相转移的，故称为转移概率矩阵。武汉纺织大学 2010 届毕业设计论文5分数(Score)：我们用一个页面所获得分数的高低作为评价一个页面质量好坏的标准，并且这个重要性的分数总是非负的实数。一个页面的得分来源于其他页面对这个页面的链接，如图 2.1 页面 C 的得分来源于 A、B。前链(Forward links): 页面 P 得到另一个

20、页面 Q 的链接，则 Q 是 P 的前链，对于结点 P 而言，前链数为 P 的出度数(Outdegrees)。如图 2.1 有 C、B 为 A 的前链,A 的出度为 2。背链(Backlinks): 页面 P 给予另一个页面 Q 的链接，则 P 是 Q 的背链，对于结点 Q 而言，背链数为 Q 的入度数(Indegrees)。如图 2.1 有 A、B 为 C 的背链。悬点(Dangling Nodes):不含出度的页面结点，如图 2.1 有 C 为悬点。2.2 PageRank 的基本模型如果我们把整个因特网络看作一个大型的拓扑结构图，网页页面看作节点，页面之间的超链接看作有向边，于是就形成的

21、了一个巨大的有向图 G。如何进行网页等级排序，最初 Google 的两个创始人拉里佩奇 (Larry Page )和谢尔盖布林 (Sergey Brin) 把这个问题转化为二维矩阵相乘的问题，并且用迭代的方法解决。他们提出的 PageRank 模型用于具有超链结构的网络的页面排序。设,边表示网页存在 的超链接，考虑在有向图 G 上随机游走的马, u vGuvuv可夫链12，一个用户在时刻访问了页面。在下一时刻该用户通过随机选择ku上的某个超链接，访问到了的某个指向的页面，其中。另uuiv |ivv uv一方面，在时刻，访问者在的机率是。转移概率矩1k |ivv uv1/deg( )u阵由 G

22、的链接情况定义，即当存在超链接从网页链接到的时候，P1/deg( )ijpi其余的，PageRank 即为此马可夫链的平稳分布。设页面 的出度记为0ijp i，则矩阵用于描述有向图 G 中页面 与之间的传输，并且有：deg( )1i ()ijPpij武汉纺织大学 2010 届毕业设计论文61deg( )0ijip, deg(i )0 , deg(i )=0于是构造了一个以转移概率矩阵为特征的马可夫链。由马可夫链遍历定理(ErgodicTheorem)3,只有当转移矩阵是非周期不可约的情况下才有唯一的平稳P分布。此非周期不可约条件保证了稳定向量 存在，其值与初始值的选取无关。v通过计算该马可夫链

23、的稳定向量 得到 PR 值(PageRank 值)，并且收敛速度取v决于 PageRank 矩阵的第二特征值的大小4。2ABCDABCDABCD图 2-2 理想图 图 2-3 存在悬点 图 2-4 存在子图根据转移矩阵的定义，从上图 2-2 可得到, , Pdeg( )1A deg( )2B ,有deg( )2C deg()1D (2-1)00101100221100220010P从上图 2-3 可得到,deg( )1A deg( )3B deg( )2C deg()0D (2-2)001011103331100220000P从上图 2-4 可得到,deg( )1A deg( )1B deg(

24、 )1C deg()1D 武汉纺织大学 2010 届毕业设计论文7 (2-3)0100100000010010P若矩阵为式(2-1)的形式，我们发现有特征值 1,事实上取,则有PP(1,1,1,1)e 。Pee定义定义 2.2 一个稀疏矩阵称为列随机方矩阵(Column-Stochastic matrix)，如果该矩阵中所有的元素均为非负的，且每一列的总和均为 1。不包含悬点的网络结构图得到的转移概率矩阵的转置是列随机()TTijPp矩阵，我们只需要证明下面的命题。命题命题 2.2 每一个列随机方阵都有特征值 1。证明:设是列随机矩阵， 为全 1 的 n 维列向量。则对有,所TnnPeTnnP

25、nnP ee以 1 是的特征值，因此 1 也是的特征值。nnPTnnP下面我们用来表示列随机矩阵的特征值为 1 的特征向量空间。以()TL PTP下均表示由网络结构图得到的转移概率矩阵的转置。同时将会发()TTijPpP现，如果对进行必要的修正(见 2.4 节)后，将满足马可夫链遍历定理和列TPTP随机性，此时必存在对应于主特征值 1 的稳定特征向量 ，此主特征向量即可v作为 PageRank 向量5。定理定理 2.2 (Gerschgorins 定理) 设，则的每一个特征值必属于下*()ijn nAaA述某个圆盘之中： ()1|niiijjj iaa1,2,in证明 设为的任意一个特征值，为

26、对应的特征向量，即Ax (2-4)()0IA x记及，,所以从式(2-4)的第 个方程12( ,)0Tnxx xx| max |ikkxx0ix i武汉纺织大学 2010 届毕业设计论文81()niiiijjjj iaxa x以及 ()，有|/| 1jixx ji , .|iiijj iaa|/|jiijj ixxa这说明属于复平面上以为圆心、为半径的一个圆盘。iia|ijj ia定理的证明，不仅指出了的每一个特征值必属于的一个圆盘中，而且指出，若一个特征向量的第个分量最大，则对应的特征值一定属于第个圆盘中。更重要的一点，可以发现列随机矩阵的特征值均不大于 1，所以列随机矩阵的TPTP特征值可

27、以表示为, 其中231,n 231 | |,n2.3 存在的问题由于网络的复杂性，导致从某些网络结构图中得到的转移矩阵得不到一P个稳定的特征向量(PageRank eigenvector)。下面主要讨论两种情形：1.存在悬点;2.得到的主特征向量不唯一。2.3.1 悬点(Dangling Nodes)如果一个网络中出现悬点，这种情况也是很常见的，如图 2-3 将导致转移矩阵的某一列或某几列全 0。此时矩阵是列子随机的，也就是的各列元TPTPTP素之和小于或等于 1。在这种情形下，必然会有所有的特征值小于或等于 1（由定理 2.2 得） 。可是，在存在悬点的网络结构中，我们仍然可以用同样的方式来

28、处理排名问题。相应的列子随机阵必定有一个非负的特征值满足,其相应的1特征向量 x 是非负的(称为 Perron 特征向量)6，此特征向量符合页面排序的要求。2.3.2 主特征向量空间不是一维的()TL P我们希望矩阵的主特征向量空间是一维的，这样就可以标准化为唯一的TP所需排名得分向量 满足。但并不一定能满足这个要求，如上图 2-4 x1ix 得到的矩阵,是二维的，其中可行的基向量为;TP()TL P11 1( ,0,0)2 2x ;但与的任意线性组合均属于,例如：21 1 1 1( , )4 4 4 4x 1x2x()TL P武汉纺织大学 2010 届毕业设计论文9;，可见不能明确的得到一个

29、稳11121 1 1 1( , , )333 3 6 6xx12215511(,)3312 12 12 12xx定的 PageRank 向量。当然这种情形并非偶然，如果某个网络结构图是非连通图，即由一些子G连通图构成，则有。12,nG GGdim( ( )L Pn不访设图对应于矩阵,子图对应于子矩阵，得到如下转移矩阵GPiGiP (2-5)1200000000nPPPP设总页面数为，对于矩阵中的每个的子矩阵是列随机的，因此mTP*iimmTiP存在一个向量,。很容易得到一组线性无关的特征向量,()TiixL P1ijx iX,如下：1in ，1100 xX2200 xX满足0000TTiiiP

30、 XPXx可知,又线性无关，所以的维数至少为。()TiXL PiX()TL Pn所以不能得到一个确定的 PageRank 向量,。()TxL P1ix 2.4 对上述问题的修正为了避免上述的两个问题，需要对原先定义的矩阵做一些修改，以满足TPPageRank 向量的唯一性。武汉纺织大学 2010 届毕业设计论文102.4.1 对出现悬点的修正如果网络结构图中出现悬点，则的某些列是全 0 的，使得转移矩阵不PP满足列随机。对这个问题有几种修正方法，最常用的是用另一个矩阵代替。PP设概率向量，为总页面数，满足且；向12(,)Tmmww wwRm0w1iw 量,满足，( )miqqR1,0,ijiq

31、为悬点其他有 。TPPqw其中附加的矩阵是可行的，如果某个用户搜索到了为悬点的网页，此时已Tqw经不存在其他页面的超链接，则假定用户以概率向量来跳转到其他页面。一w般可设,即以相同的概率跳转。可知矩阵是列随机的，因此有特征值1iwmTP为 1 的 PageRank 向量。又由定理 2.2可知，的特征值均不大于 1。TP 2.4.2 对的修正dim( ()2TL P如果图又出现多个子图，则矩阵可约(reducible)，即矩阵特征值GiGTPTP为 1 的特征向量不是一维的。4中给出了这种情形的修正，此时被另一矩阵TP代替TP(1),TPPEEew其中阻尼因子，在 Google 中常取 0.85

32、7，为概率向量同上，又称0,1w为个性化向量(Personalization Vector)，又可表示从一子链接图跳到另一子链w接图的概率。此时矩阵非负不可约，列随机且存在 PageRank 向量。因为 TPTv.(1)(1) ()(1)TTPePeew ePee w eeee同时我们发现为完全稠密矩阵。TP定理定理 2.4.1 修正矩阵 的第二特征值.(1) ,TTTPPEEew2|武汉纺织大学 2010 届毕业设计论文11定理定理 2.4.2 若矩阵具有至少 2 个不可约的子集，则修正矩阵的第二特TPTP征值为.以上两个定理的证明可参见 8。3 对 PageRank 问题的求解方法在一些工

33、程、物理问题中，通常只需要求出矩阵的按模最大的特征值（称为的主特征值）和相应的特征向量，对于解这种特征值问题，应用幂法A(Power Methord)是合适的。3.1 幂法幂法是一种计算矩阵主特征值(矩阵按模最大的特征值)及对应特征向量的A数值迭代方法，它最大的优点是方法简单，对于稀疏矩阵较合适，但有时收敛的速度很慢。设实矩阵有一个完全的特征向量组，其特征值为，相应()ijnAa12,n 的特征向量为。已知的主特征值是实根，且满足条件12,nx xx123| | |,n幂法的基本思想是任取一个非零的初始向量，由矩阵构造一向量序列0vA102210110kkkvAvvAvA vvAvAv称为迭代

34、向量。由假设，可表示为0v (设),01 122nnva xa xa x10a 于是0v01 11222kkkknnnA vaxaxax ,11 11111 12(/)()nkkkiikia xaxa x武汉纺织大学 2010 届毕业设计论文12其中。由假设 ，故 ，112(/)nkkiiiax1|/| 1i(2,3, )in0k()k 从而1 11limkkkva x这说明序列越来越接近的对应于的特征向量。1kkvA下面考虑主特征值的计算。用表示的第 个分量，则1()kivkvi (3-1)1111111()()()()()()kiikikiikiva xva x故11()lim()kikk

35、ivv即两相邻迭代向量分量的比值收敛到主特征值。由式(3-1)知，的收敛速度由比值来确定， 越小收敛11() /()kikivv21/rr越快，但当时收敛可能就很慢。21/1r3.2 在 PageRank 上的幂法通过计算该马可夫链的稳定向量 以决定 PR 值(PageRank 值)，根据第 2 章v得到的新的转移矩阵，可知 PageRank 就是在这个所对应的马可夫链的平TPTP稳分布，也即是的特征值 1 所对应的特征向量 。有方程TPv (或).TTv PvTP vv3.2.1 初始优化 PageRank 矩阵尽管幂法不总是很有效，但 Google 选择其作为数值解法。主要出于两点考虑：第

36、一，如果将幂法作用于矩阵，由于它是完全稠密的，必定影响幂法的TP收敛速度。但考虑其展开形式，有 P(1)(1)TPEPew武汉纺织大学 2010 届毕业设计论文13()(1)TTPqwew(1) )TPqe w则有幂法表达式( )k Tv(1)(1)(1) )kTkTTvPvPqe w(1)(1)(1)(1)kTkTkTTvPvqve w(1)(1)(1)(1)()kTkTkTTvPvqve w (3-2)(1)(1)(1)kTkTTvPvqw其中为概率向量,通常取初值。(1)kTv(0)111(,)TTevmm mm写成如上式(3-2)的形式，很容易看出幂法作用于矩阵可以由向量-矩阵乘积TP

37、形式作用于大型稀疏矩阵实现，在此过程中无需构造并存储修正矩阵和，PPP极大的减少了存储空间。尽管目前 Google 索引的页面数量超过 82 亿个页面1，由于矩阵是极为稀疏的，每行中非零元素平均不超过 10 个同时有很多全零列,使P得幂法的收敛速度很快。由定理 2.4.2 知矩阵的次大特征值(1) TTPPE满足（取 0.85） ，使得收敛很快，正因为如此，在222210.851Lawrence Page 和 Sergey Brin 的报告中指出成功迭代的次数在 50 到 100 步16。此外，幂法在每步迭代中只须存储一个向量，也就是当前迭代向量。这有别于像 BiCGStab 等其他方法，减少

38、了空间存储量。虽然说 PageRank 排序的基本思想很简单，但其背后有比较完善的矩阵理论作为支撑，很多微妙的问题潜藏在暗处，如个性化计算，加速收敛，灵敏度分析及运行的时间与空间复杂度估计等等。3.2.2 幂法的伪代码Function =PowerMethod()()mvInitialize(,);(0)vw武汉纺织大学 2010 届毕业设计论文14;1k Repeat;( )(1)(1)(1)k TkTkTTvvPvqw;( )(1)kkvv;1kkUntil ;4 幂法加速研究提高运算效率从来都是一个诱人的话题，特别是对于 Google 搜索引擎面对如此巨大的索引数据，运算效率更是一个不容

39、忽视的问题。好的运算速度很快就能返回结果,使客户满意度大为提高同时也提高了该领域的竞争力。在幂法的理论基础之上，之前有许多人对幂法加速收敛的问题进行了研究，如原点平移法，Rayleigh 商加速法,外推法(Extrapolations Methods)包括著名的 AitKen -过程等。24.1 外推法外推法利用过去和现在已知其构成规律的动态统计数列向未来的延伸的方法。有用的外推规则有如下特性：设一序列收敛到极限 ，通过一外推方程得到一( )()nxv( )()nx( )( ):()()nnTxy个新的序列同样收敛于极限 ，但序列比序列收敛的更快，即( )()nyv( )()ny( )()nx

40、有( )( )lim0nnnyvxv有许多外推方程被提出，下面将介绍一种很好的外推方法被称( )( ):()()nnTxy为 The vector -algorithm71214。武汉纺织大学 2010 届毕业设计论文154.1.1 The vector -algorithm外推算法 The vector -algorithm 由 Wynn12首次提出，由 Graves-Morris13证明。在一定条件下，通过这种外推规则，可以从原始序列得出一新的序列收敛于同一极限值，并且使序列收敛的更快。设为原始向量序列收敛于极限值，The vector algorithm 的外推规则( )()nxmvR如

41、下：； ；( )10n( )( )0nnx( )0,1,;nmnxR ；( )( )(1)112( )nnnkkknk0,1,;1,2,nk其中 .( )(1)( )nnnkkk可以看出,当序列为标量时，取即可得出著名的 AitKen -过程1417( )()nx1k 218。 ， (4-1)( )2n(2)(1)(1)( )(1)(2)(1)( )()()2nnnnnnnnxxxxxxxx考虑两种情形加速方式：标量法：对矩阵运用幂法可得到一收敛于主特征值 1 的标(1) TTPPE量序列，因此可以用上面的 AitKen -过程(式(2-4)将序列映射到( )k2( )k序列，使其更快的收敛于

42、主特征值 1。( )k向量法：对矩阵运用幂法同样可得到一收敛于主特征向量(1) TTPPE的向量序列，运用式（4-2）可以将序列映射到向量序列，使v( )kv( )kv( )kv其更快的收敛于主特征向量 。v设是一向量序列。当时，有如下表示形式( )()nx1k ，( )10n( )( )0nnx，( )( )( )(1)001122( )( )00nnnnnn( )(1)( )(1)( )000nnnnnxx武汉纺织大学 2010 届毕业设计论文16， (4-2)( )( )(1)122( )1nnnnx( )(1)( )111nnn4.1.2 The vector -algorithm 伪

43、代码基于上面的外推规则，下面给出取时向量法的 The vector-algorithm1k 伪代码：Function = Vector_Algorithm_2(,)(*)x(2)kx(1)kx( )kx；(2)(1)kkpxx(1)( )kkqxx ， ( , )ppp p( , )qqq q(*)(1)(,)kpqxxpq pqReturn (*)xFunction =Accel_PowerMethod()vInitialize(,，);(0)vw(0)y;1k ( )(1)(1)(1)k TkTkTTvvPvqw1kkRepeat;( )(1)(1)(1)k TkTkTTvvPvqw=Ve

44、ctor_Algorithm_2(,)( )ky( )kv(1)kv(2)kv;(2)(1)kkvv;(1)( )kkvv武汉纺织大学 2010 届毕业设计论文17;1kk;( )(1)kkyyUntil ;Return ;( )kvy5 应用5.1 对简化的网络进行等级分析在 2.2 节中给出了如下的三个简化的网络链接图，可以看出很有代表性，图2-2 是很理想的情形，从任一页面结点均可以通过有限步跳到任意其它任一页面结点处。图 2-3 存在悬点 D，此时当用户到达页面 D 时，将不存在任何其它的页面链接。图 2-4 存在子网络，AB，CD 分别构成一个子网。现实中的大型网络超链构成的有向图均

45、可由这三个简化图复合。应用幂法易得表 5-1 的三个简化图各结点的页面等级(PageRank)得分。ABCDABCDABCD图 5-1 理想图 图 5-2 存在悬点 图 5-3 存在子图表 5-1 简化图的等级图 结点ABCD图 5-102991020010399301015图 5-202788007150371002788图 5-302500025000250002500武汉纺织大学 2010 届毕业设计论文18图 5-1 中结点 A 的的分数来自于 B、C，但可以看出 A 把票均投给了 C，而 C只是投了一半的票给 A，从这点也可以推出结点 C 的分数比 A 高。图 5-2 发现B 没有来

46、自任何结点的投票，但从表 5-1 可以看出其等级并不为零而是0.0715，这样处理合理的理由是由于用户行为的多样性，对该网页可能来自其它形式的了解或是一种盲目的跳转，而有机会访问该网页，或者说访问者在访问页面的时候会不通过页面上的超链随机跳转到新的页面。比如，当用户并不知道其它站点对百度的超链接，但该用户知道其网址同样可以访问该网页。图5-3 两个子网存在访问的平衡性，也可推出等级是相同的。可见这种基于链接的PageRank 页面等级排序是合理的。5.2 对一个现实的复杂网络进行分析在 5.1 节验证了基于链接的 PageRank 页面等级排序的合理性，下面通过一个现实的网络来测试外推法的收敛

47、加速效果。测试数据 .dat 来源于19。这个数据库包含 4772 个网页和 8965 个超链接，相关的链接情况如下图 5-4。01000200030004000500060007000800090000500100015002000250030003500400045005000 图 5-4 复杂网络的链接图武汉纺织大学 2010 届毕业设计论文19为了体现出第 4 节中提供的外推法 The vector -algorithm 的效果，取阻尼因子=0.99 以降低收敛速率，使得外推法的作用更为明显。基于图 5-4 的现实网络，图 5-5 给出了这种情形下的幂法与外推法在

48、求其主特征值时的收敛情况。从图中可以看出幂法与外推法在迭代数次后均变得很平稳，其主特征值序列均收敛于 1。以误差容限为时，幂法迭代 341 次后符合要求，外推法迭代 93310次后符合要求。图 5-5 幂法与外推法的主特征值变化曲线同时为了更好的反映外推法对于阻尼因子的不同取值的加速效果，根据上面的伪代码，在 matlab7.1，Pentium(R)4 CPU 3.00GHz ,0.99GB 内存,Windows XP2环境上实现,程序参见附录。表 5-2 给出了此现实网络的的幂法与外推法迭代次数与运行时间。表 5-2 幂法与外推法的收敛测试表 Accel_PowerMothod 方法Powe

49、rMethod 方法主特征值迭代次数运行时间(秒)主特征值迭代次数运行时间(秒)0.991.0009936.17191.000534125.9531武汉纺织大学 2010 届毕业设计论文200.981.0009976.43751.000619113.23440.971.0009976.34381.00061379.17190.961.0009815.29691.00061097.26560.951.0009714.53130.9997905.89060.941.0008634.00001.0007775.03130.931.0008573.59380.9998684.39060.921.000

50、9513.32811.0007613.92190.911.0008472.98441.0008553.51560.901.0008432.70311.0007513.21880.891.0009392.45311.0007473.01560.881.0009372.31251.0008432.75000.871.0008352.17191.0007412.70310.861.0008332.04691.0008372.28130.851.0008311.93751.0008352.15630.841.0008291.79691.0008332.0781图 5-6 直观地反映了幂法与外推法 Th

51、e vector -algorithm 在应用中阻尼因子与迭代次数的关系比较。可以看出在计算大型网络的等级排序中外推法 The vector -algorithm 在收敛加速中有优异的表现。当阻尼因子取值较小时，加速不明显但仍然比传统的幂法收敛的快；当阻尼因子接近 1 时，有明显地加速效果（迭代次数不超过 100）。武汉纺织大学 2010 届毕业设计论文21图 5-6 幂法与外推法的迭代曲线6 结语与展望Google 可以说是当今最成功的搜索引擎之一，而国内对 Google 的研究文章较少，对其核心技术进行深入的剖析对于搜索引擎研究开发具有极大的借鉴作用。作为商业的搜索引擎，其最核心的技术细节

52、是保密的，文中主要参考资料多为 Google 商业化之前设计者公开发表的学术论文，因此在很大程度上增加了对这一技术介绍的难度。但是其排序算法的机理并没有本质的变化，PageRank技术仍然具有研究的价值。网页排序 PageRank 是一项复杂的计算，其本质就是求一个大型矩阵的主特征值（最大特征值）对应的特征向量，而传统的幂法是针对此类问题求法中最有效的一种数值方法，由于网络的复杂性，本文通过对转移矩阵的分析和修P正，同时利用网络结构中的这种稀疏性，将幂法作用于矩阵（完全稠密）转P化为由向量-矩阵乘积形式作用于大型稀疏矩阵实现，在此过程中无需构造并P存储修正矩阵和，极大的减少了存储空间。由于矩阵

53、是极为稀疏的，每PPP武汉纺织大学 2010 届毕业设计论文22行中非零元素平均不超过 10 个同时有很多全零行,使得幂法的收敛速度很快。在参考文献20，通过最小二乘法对整体进行外推计算得到的向量再次利用于原迭代中，而本文中给出的外推法仅仅检测原迭代得到的向量序列，并将此序列外推成一个新的更快收敛的序列，同时考察这个新序列的终止条件。与20不同的是并不将新的序列运用到原迭代中。当然幂法中收敛速度除了和特征值有关，还与开始的初始状态有关，所以可以考虑优化初始状态使其更快地收敛。对于大型稀疏阵也可以做一定的矩P阵的初等变换，使悬点下沉即全零行下沉，再利用矩阵分块的性质可以减少存储空间同时加速运算速

54、度，具体的理论可以参考21。当前有一些网站制作者通过站点链接和网站地图等来提高站内的 PageRank的反馈值。那么 Google 会不会对这样的站点内部链接投票值打折呢？而这样做会不会影响这种基于链接的等级排序计算方法？因为这本身偏偏正是 PageRank工作的最基本的机理，所以有人认为 PageRank 在 Google 排序算法中的作用已经下降,可对于超过 82 亿的页面的偌大网络链接图，人为影响又能多大呢？剖析 PageRank 技术也并非我们的最终目的，关键在于通过对 PageRank 排名算法的深入了解，以提出新的网络搜索引擎排名机制以及研究并运用一些新的运算加速算法。 网络变得越

55、来越庞杂，Google 的搜索效果也并非完美同时面临同行的竞争，排序算法的优化还有很长的路要走。参考文献：1 CNET.Google 检测独立页面量超 1 万亿EB/OL.http:/ /07/28/00 3599068 .shtml,2008-07.2 Toby Segaran.集体智慧编程M.北京:电子工业出版社.2009.3 Grimmett G, Stirzaker D. Probability and random processesM.Oxford University Press.1989.4 李庆扬,王能超,易大义.数值分析(第 4 版)M.武汉:华中科技大学出版社.2006.5 Amy N.Langville and Carl D.Meyer.Deeper inside PageRankJ.Internet Mathem