13.6 网页排名算法 PageRank

1.网页排名算法 PageRank

PageRank,网页排名，又称网页级别，Google 左侧排名或佩奇排。是一种由搜索引擎根据网页之间相互的超链接计算的技术而作为网页排名的要素之一，以 Google 公司创办人（Larry Page）拉里.佩奇之姓来命名。

2.PageRank 让链接来投票

PageRank 通过超链接关系确定一个页面的等级。Google 吧从 A 页面到 B 页面的链接解释为 A 页面给 B 页面的投票，Goolge 根据投票来源（甚至来源的来源，即链接到 A 页面的页面）和投票目标的等级来决定新的等级。简单说，一个高等级的页面可以使其他低等级页面的等级提升。

一个页面的【得票数】由所以链向他的页面的重要性来决定，到一个页面的超链接相当于对该页投一票。一个页面的 PageRank 是有所有链向他的页面（链入页面）的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级，相反如果一个页面没有任何链入页面，那么它就没有等级。

3.PageRank 算法

假设一个由 4 个页面组成的小团体：A,B，C，D。如果所有页面都链向 A，那么 A 的 PR（PageRank）值将是 B，C，D 的 PageRank 综合。

PR(A)=PR(B)+PR(C)+PR(D)

继续假设 B 也有链接到 C，并且 D 也有链接到包含 A 的 3 个页面。一个页面不能投票 2 次。所以 B 给每个页面半票。以同样的逻辑，D 投出的票只有 1/3 算到了 A 的 PageRank 上。

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

互联网中一个网页只有对自己的出链，或者几个网页的出链形成一个循环圈。那么在不断的迭代过程中，

这一个或几个网页的 PR 值将只增不减，显然不合理。

如下图中的 C 网页就是刚刚说的只有对自己的出链的网页： 

为了解决这个问题。我们想象一个随机浏览网页的人，假定他有一个确定的概率会输入网址直接跳转到一个随机的网页，并且跳转到每个网页的概率是一样的。此图中 A 的 PR 值可表示为：

      a=0.85 概率

PageRank 计算公式：

P1,P2,.....Pn 被研究页面，

M(Pj):链入 Pi 页面的集合。

L(Pj):是 Pj 链出页面的数量，而 N 是所有页面的数量。

PageRank 值是一个特殊矩阵中的特征向量。这个特征向量为：

      d=0.85