第 10 章 PageRank——Google民主表决式网页排名技术
Last updated
Last updated
对于一个特定的查询，搜索结果取决于网页的质量信息，和这个查询与每个网页的相关性信息。
如果一个网页被很多其他网页所链接，说明它受到普遍的承认和信赖。比如说，对于来自不同网页的链接区别对待，因为网页排名高的网页链接更可靠，于是要给这些链接以较大的权重。
计算结果的网页排名需要用到网页本身的排名。布林破解了这个怪圈，把这个问题变成了一个二维矩阵相乘的问题，并用迭代的方法解除了这个问题。先假设所有的网页排名是相同的，并根据这个初始值，算出各个网页的第一次迭代排名，然后根据第一次迭代排名算出第二代的排名。
代初始时每个网页的权重是一样的，然后通过计算更新每个网页的权重，规则如下：
当一个网页被越多的网页引用时，它的权重越大。
当一个网页的权重越大时，它引用的网页的权重也随之变大。
当一个网页引用的网页越多时，被它引用的网页获得的权重就越小。
如此反复迭代，算法最终会收敛到一个固定的排名。
网页排名的高明之处在于它把整个互联网系统当作一个整体对待。以前的信息检索把每个网页当做独立的个体对待，只注意到网页内容和查询语句的相关性，忽略了网页之间的关系。
假定向量为第一、第二...第个网站的网页排名。初始假设值为 。
矩阵为网页之间的链接数目，其中代表第个网页指向第个网页的链接数。 已知，未知。
假定是第次迭代结果，那么：
在学术界，衡量网页质量的这个算法被公认为是文献检索中最大的贡献之一。
最终会收敛于，当与的结果差异非常小时，就可以停止迭代运算。（注：计算访问概率较小的网站时，需要做平滑处理）
网页的排名是一个一维向量，对它的平滑处理只能用一个小的常数。这时，公式（10.1）变成：
其中是互联网网页的数量， 是一个（较小的）常数，是单位矩阵。