本文同时发表在果壳网死理性派栏目，传送门：http://www.guokr.com/article/65304/。因为字数原因，所以编辑对死理性派上发表的文章进行了一定的删减和修正。这里发出的是未删减的版本，表示“太理性了，看不懂”的童鞋们可以来围观此文。 如果你安装过Google工具栏，如果你建立过独立博客或个人网站，那么你肯定和PageRank打过照面。而即使是从未考虑建站的读者，也有很大一部分听说过PageRank，毕竟作为Google搜索结果排序的重要依据[1]，这个算法已经被广泛应用于网络的每一个角落。而PageRank值的大小，也早已与网站的SEO[2]成功与否紧密相连。 那么PageRank的名称从何而来？PageRank究竟如何准确表示网页重要度，它的算法又是如何高效准确运行的呢？在PageRank的背后，有什么数学理论的支持？且听笔者为您一一道来。 三个孩子和豌豆游戏 从前有一个死理性派老爸，他有三个孩子。老爸是个懒人，他在家里把三个孩子叫做老大、老二和老三。 一天，三个孩子正在玩游戏，老爸把他们叫到身边。“我这里有三十颗豌豆，”老爸说，“我们来用它们玩一个游戏，游戏结束之后按照游戏结果把豌豆分给你们，好不好啊？” “好！”三个孩子异口同声地答应了。 “你们先在这张纸上写下你们喜欢的人，如果你认为另外两个兄弟你都很喜欢，那就把两个人的名字都写下来。比如我知道老二很喜欢老大，那么老二就在纸上写老大的名字。” 三个孩子很快写好了，然后老爸把纸收了上来。老大的纸上写了老二和老三的名字，而老二写了老大，老三写了老二。三个人互相喜欢的结果如图： 老爸清了一下嗓子，继续向孩子们解释规则：“接下来，我会给你们每个人分十颗豌豆。桌上有三个盘子，分别代表你们三个人，豌豆都放在盘子里。在我喊‘预备’的时候，你们要把盘子里的豌豆全都拿到手里。在我喊‘开始’的时候，你们要把手里的豌豆全部平均分给自己喜欢的人。” 老二举手：“那就是说，我每次都要把自己盘子里的豌豆全部拿起来，然后放到老大的盘子里吗？” “没错，”老爸说，“老三和老大也类似。大家都明白规则了吗？” 三个孩子点头。“好，那游戏开始！” 一开始三个孩子盘子里豌豆的情况如图： “预备！”妈妈喊到，“开始！” 三个孩子开始分配自己手中的豌豆。老二把十颗豌豆都给了老大；老三把十颗豌豆都给了老二；老大则是给老二和老三一人分配了五颗豌豆，如图： 三个孩子很快就麻利地分配好了自己手中的豌豆。这时三个人的盘子变成了这种情况： 老大有点不高兴了：“为什么我的豌豆比老二的还少啊？这个游戏不公平！” 老爸说：“这个游戏还没有结束。接下来我还会继续吹哨，你们也还要继续这个游戏，直到你们盘子里的豌豆数不再变化为止。公平不公平，到时候就能看出来了。” 老大虽然有点疑惑，不过还是点头同意了。 就这样，游戏一直进行下去。在下一轮的交换豌豆后，老大的盘子里有了15颗豌豆，老二有10颗，而老三只有五颗。当然故事在这里还没有结束，不过我们的描述要结束了。因为这个游戏将会持续很长很长时间——这点大概是死理性派老爸没有想到的。当然如果继续分下去，豌豆的数量将不再是整数，这一点我们也不深究了，游戏怎么能进行下去，就留给老爸想办法吧。 那么这个游戏最终的结果是什么样的呢？我们可以用电脑模拟这个过程，得出的结果是：老大和老二的盘子里各有12颗豌豆，而老三的盘子里有6颗豌豆。这时候无论游戏怎么进行下去，盘子里的豌豆数量都不会再变化。 网页排名和PageRank 在互联网刚刚发展的时代，人们曾经为网页的排名问题伤透脑筋。网页排名，顾名思义，就是为互联网上成千上万（当然，现在互联网上的网页数量已经不只是成千上万的程度了）的网页按照重要度进行排序。能够得知哪个网页更重要，对搜索引擎的发展十分有帮助——很显然，搜索引擎应该把重要的网页放到搜索结果中比较靠前的地方。 这个问题看起来很容易，但是解决的方法却没有想象的那么简单。 最初，一些比较流行的网页排名算法都很类似，它们都使用了一个非常简单的思想：越是重要的网页，访问量就会越大。于是，许多大公司就通过统计网页的访问量来进行网页排名。但是这种排名算法有两个很显著的问题：一是因为只能够抽样统计，所以统计数据不一定准确，而且访问量的波动会比较大，想要得到准确的统计需要大量的时间和人力，还只能维持很短的有效时间；二是访问量并不一定能体现网页的“重要程度”——可能一些比较早接触互联网的网民还记得，那时有很多人推出了专门“刷访问量”的服务。 有没有更好的方法，不统计访问量就能够为网页的重要度排序呢？在1999年，一篇以拉里•佩奇（Larry Page）为第一作者的论文[3]发表了。论文中介绍了一种叫做PageRank的算法，这种算法的主要思想是：越“重要”的网页，页面上的链接质量也越高，同时越容易被其它“重要”的网页链接。于是，算法完全利用网页之间互相链接的关系来计算网页的重要程度，终于摆脱了访问量统计的框框。 不过，不知道我们的死理性派老爸是不是了解，实际上刚刚他和孩子玩的游戏，就是PageRank算法的运行过程。 PageRank会给每个网页一个数值，这个数值越高，就说明这个网页越“重要”。而刚刚的游戏中，如果把豌豆的数量看作这个数值（可以不是整数），把孩子们看作网页，那么游戏的过程就是PageRank的算法，而游戏结束时豌豆的分配，就是网页的PageRank值。[4] 随机行走模型和马尔可夫过程 PageRank算法的思想基于“随机行走模型”（Random Walk Model）[5]。实际上，PageRank求解了这样一个问题：一个人在网络上浏览网页，每看过一个网页之后就会随机点击网页上的链接访问新的网页。如果当前这个人浏览的网页x已经确定，那么网页x上每个链接被点击的概率也是确定的，可以用向量Nx表示。在这种条件下，这个人点击了无限多次链接后，恰好停留在每个网页上的概率分别是多少？ 在这个模型中，我们用向量Ri来表示点击了i次链接之后可能停留在每个网页上的概率（R0则为一开始就打开了每个网页的概率，后面可以看到R0的取值对最终结果没有影响）。很显然Ri的L1范式[4]为1，这也是PageRank算法本身的要求。 于是，整个浏览过程的一开始，我们有： 其中，A是一个表示每一次点击链接概率的矩阵。A的第i列第j行Ai, j的含义是，如果当前访问的网页是网页i，那么下一次点击链接跳转到网页j的概率为Ai, j。 这样设计矩阵A的好处是，通过矩阵A和向量Rn-1相乘，即可得出点击一次链接后每个网页可能的停留概率向量Rn。例如，令R1=AR0，可以得到点击一次链接后停留在每个网页的概率： … Continue reading →