第 10 章 PageRank——Google民主表决式网页排名技术

对于一个特定的查询，搜索结果取决于网页的质量信息，和这个查询与每个网页的相关性信息。

PageRank算法核心思想

如果一个网页被很多其他网页所链接，说明它受到普遍的承认和信赖。比如说，对于来自不同网页的链接区别对待，因为网页排名高的网页链接更可靠，于是要给这些链接以较大的权重。

计算结果的网页排名需要用到网页本身的排名。布林破解了这个怪圈，把这个问题变成了一个二维矩阵相乘的问题，并用迭代的方法解除了这个问题。先假设所有的网页排名是相同的，并根据这个初始值，算出各个网页的第一次迭代排名，然后根据第一次迭代排名算出第二代的排名。

代初始时每个网页的权重是一样的，然后通过计算更新每个网页的权重，规则如下：

当一个网页被越多的网页引用时，它的权重越大。
当一个网页的权重越大时，它引用的网页的权重也随之变大。
当一个网页引用的网页越多时，被它引用的网页获得的权重就越小。

如此反复迭代，算法最终会收敛到一个固定的排名。

网页排名的高明之处在于它把整个互联网系统当作一个整体对待。以前的信息检索把每个网页当做独立的个体对待，只注意到网页内容和查询语句的相关性，忽略了网页之间的关系。

PageRank的计算方法

假定向量 $B=\left[ b_1,\ b_2,\ \cdots ,\ b_n \right]$ 为第一、第二...第个网站的网页排名。初始假设值为 $B_0=\left[ \frac{1}{N},\ \frac{1}{N},\ \cdots ,\ \frac{1}{N} \right]$ 。

矩阵 $A=\left[ \begin{matrix} a_{11}& \cdots& a_{1M}\\ \cdots& a_{mn}& \cdots\\ a_{M1}& \cdots& a_{MM}\\ \end{matrix} \right]$ 为网页之间的链接数目，其中 $a_{mn}$ 代表第个网页指向第个网页的链接数。已知，未知。

假定 B_i 是第次迭代结果，那么：

最终 B_i 会收敛于，当 B_i 与 $B_{i-1}$ 的结果差异非常小时，就可以停止迭代运算。（注：计算访问概率较小的网站时，需要做平滑处理）

网页的排名是一个一维向量，对它的平滑处理只能用一个小的常数 $\alpha$ 。这时，公式（10.1）变成：

其中是互联网网页的数量， $\alpha$ 是一个（较小的）常数，是单位矩阵。

小结

在学术界，衡量网页质量的这个算法被公认为是文献检索中最大的贡献之一。

Previous第 9 章图论和网络爬虫 Next第 11 章如何确定网页和查询的相关性

Last updated 7 years ago