排级算法

  PageRank是Google核心创新技术,其他搜索引擎大多借鉴使用了该方法的变种。下面介绍两种应用最广、最成功的排级算法PageRank和HITS。

  1.PagePank算法

  PageRank算法由Stanford大学的S. Brin和L. Page提出，算法的理论基础是图论，它将Web页面看做点，完全忽视访问内容。在该模型下，页面t被访问到的概率Pr(t)通过计算所有的点的入度与出度求得，即PageRank值根据下式计算:

算法：PageRank 
输入：各页面赋予相同的初值Pr(t)；
输出：各页面新的PageRank值Pr(t)。
Stepl: 给各页面赋初值Pr(t)（可以对各页面初值进行归一化，使得所有页面的PageRank之和为1）；
Step2：根据链接关系使用上面给出的公式计算各页面新的PageRank值，这时的PageRank可以视为各页面被访问到的概率；
Step3：当判断当前的结果是否收敛，如果不，则跳转至Step2;
Step4: 算法结束。

  PageRank 算法的优点如下：

  （1）直接高效。PageRank 算法直接对从 Internet 上模糊得来的“第一手资料”进行挖掘操作,没有中间步骤,实时性较高。而且,其思路是利用一个迭代公式进行计算,算法简单,效率较高。

  （2）主题集中。PageRank算法的操作完全针对某一主题,可以较精确返回与之相关的重要页面，较好克服“主题漂移”“问题。

  PageRank算法存在的缺陷如下：

  （1）完全忽略网页内容，干扰挖掘结果。例如，有相关内容的竞争对手网页没有链接，而无太多相关内容的合作伙伴网页互相链接的现象，会造成挖掘结果不准确。

  （2） 结果范围窄。同 HITS 算法的“知识范围扩大”与“主题漂移”类似，PageRank 算法的结果范围窄,无联想，这是“主题集中”的负面影响。