Google的成功意味着PageRank算法值得特别的关注。PageRank算法是少数几个公开的排序算法之一。PageRank算法对数学要求很高，但可以做些简单的解释，以分析它对网络空间的影响。搜索引擎的其他排序算法也可能获得与PageRank算法相同的结果，尽管他们没有公开任何与其相关的信息。HITS算法是另一个基于链接的排序算法，与PageRank算法形成鲜明对比，下面的引述概括了链接对于搜索引擎的价值。 “通过分析网页间的链接关系，搜索引擎可以判定出一个网页是关于什么的，也可以判断它是否很重要并值得列入排序列表中去。”

搜索引擎在排序过程中不考虑链接因素，而使用一个基于关键词词频的公式，该公式在潜在匹配文档中统计以用户为中心的查询的关键词的词频。例如，检索“动物学”时，引擎可能返回文档标题、头部和正文或是在URL中出现该词语的所有网页。这种排序算法可能无法判定哪些是关于“动物学”的最权威的网页，而只能判定哪些页面中与“动物学”相关的词语最多。但PageRank算法却可以通过链接结构，判别出哪个是最权威的网页——排名位于最前面的那个，即拥有最多入链的网页。这就使得引擎能够返回一个真正的权威网页，而不是一个类似于“动物学”课程表的网页。

1998年Google的PageRank算法的设计者和奠基者Brin和Page将其核心部分公开。随后，在1999年他们和Motwani、Winogriad对其进行了更为详细地阐述。直到2004年，该算法仍在使用，只是作为一个更大规模的算法集的一部分，该算法集采用100多个指标来判定网页是否和用户的查询相关，并对它们进行排序。Google官方声明：“虽然我们有许多工程师在为全面提高Google的各个方面而努力，但PageRank算法仍然是我们网络搜索工具技术的基础。”下面是支撑PageRank算法的两个基本理念：

·人链是衡量目标网页重要性的很好的指标。

·源于重要网页的人链比源于次要网页的人链更能说明该网页的重要性。

将对PageRank算法进行阐述。在这里，使用Google网站和其他地方所用的“投票”这一比喻代替原来的“随机冲浪”一词所表达的含义。

在一个简单的基于链接的投票系统中，可以给每个网页投票，并允许网页将其一票平分后投给它所链接的网页，最后统计每个网页的最终票数便可形成一个排序系统。在这一过程中，拥有较多人链的网站能获得较高的票数。然而，这个简单的投票系统不足以说明问题。如受欢迎的列表网页的入链很多，就会获得很多投票，但该页面只有一票，可平分给它所链接的目标网页，这些目标网页中可能含有有价值的内容。重复这个投票过程，使得每个网页在前一轮中获得的票数平分给其目标网页。然而遗憾的是，当投票系统陷入循环时，或遇到一个没有出链的网页时，投票的重复过程便无法进行下去了。

对此，Brin和Page提出的解决方案是，在每次投票时，网页回收一部分票数，而不全部传递给它的链接目标网页。他们建议保留15%的票数，这样，每次投票时，网页只将其85％的票数平分给其链接目标网页，而另外15％的票数供系统中所有的URL平分。运用数学算法可以有效地实现这一投票系统。重复这样的投票过程，直至所有网页的票数都趋于稳定，即在新的一轮投票中，网页票数的变化很小，这样，PageRank算法便诞生了。

有两种PageRank算法和修正算法，修正后的算法有明显的不同。实践中，Google采用的可能是PageRank修正算法。第一种修正算法是由Lifantsel在2000年提出的，即将PageRank的投票统计建立在网站的基础上，而不是对单个网页进行投票统计。第二种修正算法是由Page、Brin、Motwain和Winograd于1999年提出的，即自动赋予一个网站的首页较高的票数。Google似乎同时采用了这两种修正算法，可能是与基于网页的标准算法相结合，也可能是完全将其取代，但这些都只是猜测 。

评论 (0) All

登陆 还没注册？