Google(谷歌)使用PageRank算法给搜索结果排序的原理

时间：2022-05-29 03:30:01 | 来源：网络营销

时间：2022-05-29 03:30:01 来源：网络营销

一个正常的搜索引擎，其核心功能自然是网页搜索，那搜索结果应该怎样排序才最好呢？实际上，在谷歌主导互联网搜索之前，人们为此伤透了脑筋。

当时人们认为，通过判断能够得知哪个网页更重要，对搜索引擎的发展十分有帮助，很显然搜索引擎应该把重要的网页放到搜索结果中比较靠前的地方。这个问题看起来很容易，但是解决的方法却没有想象的那么简单。

一、网页排名和谷歌算法的诞生

在谷歌诞生之前那段时间，流行的网页排名算法都很类似，它们都使用了一个非常简单的思想：越是重要的网页，访问量就会越大，许多大公司就通过统计网页的访问量来进行网页排名。但是这种排名算法有两个很显著的问题：

1、因为只能够抽样统计，所以统计数据不一定准确，而且访问量的波动会比较大，想要得到准确的统计需要大量的时间和人力，还只能维持很短的有效时间。

2、访问量并不一定能体现网页的“重要程度”，可能一些比较早接触互联网的网民还记得，那时有很多人推出了专门“刷访问量”的服务。

那有没有更好的方法，不统计访问量就能够为网页的重要度排序呢？

就是在这种情况下，1996年初，谷歌公司的创始人，当时还是美国斯坦福大学研究生的佩奇和布林开始了对网页排序问题的研究。

在1999年，一篇以佩奇为第一作者的论文发表了，论文中介绍了一种叫做PageRank的算法（具体算法可查看亿企邦《pr值是什么》的相关介绍），这种算法的主要思想是：越“重要”的网页，页面上的链接质量也越高，同时越容易被其它“重要”的网页链接。

于是，算法完全利用网页之间互相链接的关系来计算网页的重要程度，将网页排序彻底变成一个数学问题，终于摆脱了访问量统计的框框。

二、模拟PageRank算法的运行过程

在详细讲述这个算法之前，不妨让我们用一个游戏，先来简单模拟一下PageRank算法的运行过程，以便读者更好地理解。

三兄弟分30颗豌豆，起初每人10颗，他们每次都要把手里的豌豆全部平均分给自己喜欢的人，下图表示了三兄弟各自拥有的初始豌豆数量，以及相互喜欢的关系（箭头方向表示喜欢，例如老二喜欢老大，老大喜欢老二和老三）。

第一次分配后，我们会得到结果如下：

就这样，让游戏一直进行下去，直到他们手中的豌豆数不再变化为止。

那么这个游戏到底是否可以结束呢，如果可以，最终的结果又是什么样的？

在此我们用电脑模拟了这个过程，得出的结果是：老大和老二的盘子里各有12颗豌豆，而老三的盘子里有6颗豌豆，这时候无论游戏怎么进行下去，盘子里的豌豆数量都不会再变化。

看到这里，读者可能会问：这个游戏和网页排序有什么关系？

实际上，PageRank会给每个网页一个数值，这个数值越高，就说明这个网页越“重要”。

而刚刚的游戏中，如果把豌豆的数量看作这个数值（可以不是整数），把孩子们看作网页，那么游戏的过程就是PageRank的算法，而游戏结束时豌豆的分配，就是网页的PageRank值。

三、PageRank算法的数学模型

不同于之前的访问量统计，PageRank求解了这样一个问题：一个人在网络上浏览网页，每看过一个网页之后就会随机点击网页上的链接访问新的网页。

如果当前这个人浏览的网页x已经确定，那么网页x上每个链接被点击的概率也是确定的，可以用向量Nx表示。

在这种条件下，这个人点击了无限多次链接后，恰好停留在每个网页上的概率分别是多少？

在这个模型中，我们用向量Ri来表示点击了i次链接之后可能停留在每个网页上的概率（则为一开始就打开了每个网页的概率，后面我们将证明的取值对最终结果没有影响）。很显然R i的L1范式为1 ，这也是PageRank算法本身的要求。

仍以上面的游戏为例，整个浏览过程的一开始，我们有：

其中，A表示每一次点击链接概率的矩阵，A的第i列第j行的含义是如果当前访问的网页是网页i，那么下一次点击链接跳转到网页j的概率为 。

这样设计矩阵A的好处是，通过矩阵A和向量相乘，即可得出点击一次链接后每个网页可能的停留概率向量。例如，令，可以得到点击一次链接后停留在每个网页的概率：

之后一直迭代下去，有：

对于上面的例子，迭代结果如下图：

由上图我们可以看到，每个网页停留的概率在振荡之后趋于稳定。

在这种稳定状态下，我们可以知道，无论如何迭代，都有，这样我们就获得了一个方程：

而整个迭代的过程，就是在寻求方程R = AR的解，而无论是多少，迭代无限多次之后，一定会取得令R = AR成立的R值，整个求解R的过程，就如同一个人在一张地图上的不同位置之间随机地行走一样，所以被称为“随机行走模型”。

随机行走模型有一个显著的特点，那就是每一次迭代的结果只与前一次有关，与更早的结果完全无关，这种过程又被称为马尔可夫过程（Markov Process）或马尔可夫链（Markov Chain）。

马尔可夫过程的数学定义是：如果对于一个随机变量序列， 其中X n表示时间n的状态及转移概率P，有：

即只受的影响，则此过程成为马尔可夫过程。其中称作“一步转移概率”，而两步、三步转移概率则可以通过一步转移概率的积分求得。

当状态空间有限时，转移概率可以用用一个矩阵A来表示，称作转移矩阵（transition matrix），此时转移概率的积分即为矩阵的幂，k步转移概率可以用表示，这也是随机行走模型中的情况，而对于一个正的（每个元素都为正的）转移矩阵A ，可以证明一定有：

这就完整解释了为什么的取值对最终结果没有影响。

四、修正“悬挂网页”带来的不良影响

但是这里有一个问题：即便的取值对最终结果没有影响，用R作为网页排序的依据是否真的合理？

在亿企邦看来，这个其实并不合理，因为当一个网页只有链入链接没有链出链接的时候，这个网页就会像一个“黑洞”一样，将同一个连通子图中其它网页流向它的PageRank慢慢“吞掉”（因为算法中虚拟的用户一旦进入那样的网页，就会由于没有对外链接而永远停留在那里），这种网页我们称之为“悬挂网页”（Dangling Link）。

这种“黑洞”效应是如此显著，以至于在一个连通性良好的互联网上，哪怕只有一个“悬挂网页”，也足以使整个互联网的网页排序失效，可谓是“一粒老鼠屎坏了一锅粥”。

为了解决这个问题，佩奇和布林进行了修正，他们意识到，当用户访问到“悬挂网页”时，都不可能也不应该就停留在了这个页面，而是会自行访问其它网页。

虽然对每个用户来说，自行访问的网页与各人的兴趣有关，但亿企邦觉得从平均意义上来讲，佩奇和布林假定用户将会在整个互联网上随机选取一个网页进行访问。

所以他们给PageRank算法加入了一个新的向量E，它的作用是，按照其中所描述的比例来向全部网页分配悬挂网页每一次“吞掉”的PageRank。

这样，相当于为悬挂网页添加了链向网络上全部网页的链接，避免了悬挂链接的出现。

以上就是谷歌背后最重要的PageRank算法奥秘，与以往那种凭借关键词出现次数所作的排序不同，这种由所有网页的相互链接所确定的排序是不那么容易做假的，因为做假者再是把自己的网页吹得天花乱坠，如果没有真正吸引人的内容，别人不链接它，一切就还是枉然。

而且“佩奇排序”还有一个重要特点，那就是它只与互联网的结构有关，而与用户具体搜索的东西无关，这意味着排序计算可以单独进行，而无需在用户键入搜索指令后才临时进行，谷歌搜索的速度之所以快捷，在很大程度上得益于此。

亿企邦点评：

最后，我要强调的一点是，虽然PageRank是Google搜索结果排序的重要依据，并以此发家，不过它并不是全部依据，实际上，Google发展到现在，已同时用了数百种不同的算法来确定最终显示给用户的搜索结果顺序。