搜索引擎中的 PageRank和HITS算法

1. PageRank 算法概述

 PageRank,即网页排名，又称网页级别、Google 左侧排名或佩奇排名。

 是 Google 创始人拉里·佩奇和谢尔盖·布林于 1997 年构建早期的搜索系统原型时提出的链接分析算法，自从 Google 在

商业上获得空前的成功后，该算法也成为其他搜索引擎和学术界十分关注的计算模型。目前很多重要的链接分析算法都是在

PageRank 算法基础上衍生出来的。PageRank 是 Google 用于用来标识网页的等级/重要性的一种方法，是 Google 用来衡量

一个网站的好坏的唯一标准。在揉合了诸如 Title 标识和 Keywords 标识等所有其它因素之后，Google 通过 PageRank 来调

整结果，使那些更具“等级/重要性”的网页在搜索结果中另网站排名获得提升，从而提高搜索结果的相关性和质量。其级别从

0 到 10 级，10 级为满分。PR 值越高说明该网页越受欢迎（越重要）。例如：一个 PR 值为 1 的网站表明这个网站不太具有

效果。 PageRank 除了考虑到入链数量的影响，还参考了网页质量因素，两者相结合获得了更好的网页重要性评价标准。

对于某个互联网网页 A 来说，该网页 PageRank 的计算基于以下两个基本假设：Î

数量假设：在 Web 图模型中，如果一个页面节点接收到的其他网页指向的入链数量越多，那么这个页面越重要。

质量假设：指向页面 A 的入链质量不同，质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面

指向页面 A，则页面 A 越重要。

 利用以上两个假设，PageRank 算法刚开始赋予每个网页相同的重要性得分，通过迭代递归计算来更新每个页面节点的

PageRank 得分，直到得分稳定为止。 PageRank 计算得出的结果是网页的重要性评价，这和用户输入的查询是没有任何关

系的，即算法是主题无关的。假设有一个搜索引擎，其相似度计算函数不考虑内容相似因素，完全采用 PageRank 来进行排

序，那么这个搜索引擎的表现是什么样子的呢？这个搜索引擎对于任意不同的查询请求，返回的结果都是相同的，即返回

PageRank 值最高的页面。

PageRank 值平均分配到本页面包含的出链上，这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所

传入的权值求和，即可得到新的 PageRank 得分。当每个页面都获得了更新后的 PageRank 值，就完成了一轮 PageRank 计

算。Î



3.2 基本思想：

 如果网页 T 存在一个指向网页 A 的连接，则表明 T 的所有者认为 A 比较重要，从而把 T 的一部分重要性得分赋予 A。这

个重要性得分值为：PR（T）/L(T)

　ÎÎÎ 其中 PR（T）为 T 的 PageRank 值，L(T)为 T 的出链数

 则 A 的 PageRank 值为一系列类似于 T 的页面重要性得分值的累加。

即一个页面的得票数由所有链向它的页面的重要性来决定，到一个页面的超链接相当于对该页投一票。一个页面的

 继续假设 B 也有链接到 C，并且 D 也有链接到包括 A 的 3 个页面。一个页面不能投票 2 次。所以 B 给每个页面半票。以

同样的逻辑，D 投出的票只有三分之一算到了 A 的 PageRank 上。



 换句话说，根据链出总数平分一个页面的 PR 值。



例子：

 如图 1所示的例子来说明 PageRank 的具体计算过程。ÎÎ

 





Google 通过数学系统给了每个页面一个最小值。



 这个公式就是.S Brin 和 L. Page 在《The Anatomy of a Large- scale Hypertextual Web Search Engine Computer

Networks and ISDN Systems 》定义的公式。

 所以一个页面的 PageRank 是由其他页面的 PageRank 计算得到。Google 不断的重复计算每个页面的 PageRank。如果

给每个页面一个随机 PageRank 值（非 0），那么经过不断的重复计算，这些页面的 PR 值会趋向于正常和稳定。这就是搜

索引擎使用它的原因。



4. PageRank 幂法计算(线性代数应用)

4.1 完整公式：

关于这节内容，可以查阅：谷歌背后的数学

首先求完整的公式：

Arvind Arasu 在《Junghoo Cho Hector Garcia - Molina, Andreas Paepcke, Sriram Raghavan. Searching the Web》 更加准

如果网页 i 有指向网页 j 的一个链接，则