你的网站价值几何？让PageRank告诉你答案

Shared by Doublel
好文，可是有点长。等有时间了慢慢看……

本文同时发表在果壳网死理性派栏目，传送门：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上每个链接被点击的概率也是确定的，可以用向量N_x表示。在这种条件下，这个人点击了无限多次链接后，恰好停留在每个网页上的概率分别是多少？
在这个模型中，我们用向量R_i来表示点击了i次链接之后可能停留在每个网页上的概率（R₀则为一开始就打开了每个网页的概率，后面可以看到R₀的取值对最终结果没有影响）。很显然R_i的L1范式[4]为1，这也是PageRank算法本身的要求。
于是，整个浏览过程的一开始，我们有：

其中，A是一个表示每一次点击链接概率的矩阵。A的第i列第j行A_{i, j}的含义是，如果当前访问的网页是网页i，那么下一次点击链接跳转到网页j的概率为A_{i, j}。
这样设计矩阵A的好处是，通过矩阵A和向量R_n-1相乘，即可得出点击一次链接后每个网页可能的停留概率向量R_n。例如，令R₁=AR₀，可以得到点击一次链接后停留在每个网页的概率：

之后一直迭代下去，有：

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

可以看到，每个网页停留的概率在振荡之后趋于稳定。
在这种稳定状态下，我们可以知道，无论如何迭代，都有R_n=R_n-1。这样我们就获得了一个方程：

而整个迭代的过程，就是在寻求方程R=AR的解。这也是为什么R₀的取值对结果没有影响：无论R₀是多少，迭代无限多次之后，一定会取得令R=AR成立的R值。整个求解R的过程，就如同一个人在一张地图上的不同位置之间随机地行走一样，所以被称为“随机行走模型”。
随机行走模型有一个显著的特点，那就是每一次迭代的结果只与前一次有关，与更早的结果完全无关。这种过程又被称为马尔可夫过程（Markov Process）或马尔可夫链（Markov Chain）[7]。
马尔可夫过程的数学定义是：如果对于一个随机变量序列X₀、X₁、X₂、…，其中X_n表示时间n的状态及转移概率（transition possibility）P，有：

即X_n只受X_n-1的影响，则此过程成为马尔可夫过程。其中P(X_n+1|X_n)称作“一步转移概率”，而两步、三步转移概率则可以通过一步转移概率的积分求得。
当状态空间有限时，转移概率可以用用一个矩阵A来表示，称作转移矩阵（transition matrix）。此时转移概率的积分即为矩阵的幂，k步转移概率可以用A^k表示，这也是随机行走模型中的情况。而对于一个正的（每个元素都为正的）转移矩阵A，可以证明一定有：

这也解释了为什么在这段开始笔者提到，R₀的取值对最终结果没有影响。
上述有限状态空间的马尔可夫过程只是马尔可夫过程的一个小分支。马尔可夫过程作为一种有效的随机过程模型，已经在更广泛的领域中得以应用。除了PageRank算法外，LZMA压缩算法[8]也使用了马尔可夫过程作为信号模型；此外，生物学和机器写作的领域都有马尔可夫过程的身影。

悬挂网页和个性化PageRank

不知道细心的读者发现没有，以上叙述的算法有时并不能解决问题——在某些情况下，算法的结果中有很多网页的PageRank都是0，甚至结果就是一个零向量。
这是为什么呢？其实，当一个网页只有链入链接没有链出链接的时候，这个网页就会像一个“黑洞”一样，将同一个连通子图中其它网页流向它的PageRank慢慢“吞掉”，这种网页我们称之为“悬挂网页”（Dangling Link）。此时的转移矩阵A，对于任意自然数n，Aⁿ都不会是一个正的转移矩阵——A中对应着悬挂网页的位置永远是0。
为了解决这个问题，PageRank算法加入了一个新的向量E。它的作用是，按照其中所描述的比例来向全部网页分配悬挂网页每一次“吞掉”的PageRank。这样，相当于为悬挂网页添加了链向网络上全部网页的链接，避免了悬挂链接的出现。
E的取值如何确定呢？论文中提到，一般可以直接使用平均分配的方式把悬挂网页的PageRank分配给所有网页。但是，因为抓取的数据库通常是不完全的，所以悬挂网页的数量一般来说非常巨大，E的改变也会对PageRank的结果造成影响。于是，通过设定不同的E，我们就可以人为干预PageRank的结果。这样得到的PageRank，称作“个性化PageRank”（Personalized PageRank）。
事实上，这样的干预是很重要的。在PageRank算法的真正实现中，会增加一个常系数c，即：

以此来人为“制造”悬挂网页。

佩奇和“佩奇的排名”

之前提到过，PageRank算法的论文中，第一作者的名字叫做拉里•佩奇，即Larry Page。
佩奇是Google的创始人之一，现任Google的CEO。这里有一件很有意思的事情出现了：“佩奇”的英文是“Page”，恰好与“PageRank”的“Page”相吻合。这是巧合还是有意为之呢？
在网络上笔者可以找到的许多资料中，均提到PageRank是以拉里•佩奇的姓命名。但是所有这些资料都没有提到这条信息的来源，所以其真实性无从得证。
不过，既然佩奇本人没有出来解释，那我们也没有必要纠结于Page的含义了。或许这个词本身就是佩奇利用双关语向我们开的一个小玩笑呢！

脚注与参考资料

[1] 虽然PageRank是Google搜索结果排序的重要依据，不过它并不是全部依据——实际上，Google用了数百种不同的算法来确定最终显示给用户的搜索结果顺序。
[2] SEO，即Search Engine Optimization，意为搜索引擎优化，主要是将网站的内容、布局等针对搜索引擎进行优化，使得页面更容易在搜索结果上被显示。
[3] L. Page, S. Brin, R. Motwani and T. Winograd. The PageRank Citation Ranking: Bring Order to the Web. Jan, 1998.
[4] 这里的描述不是非常准确：首先，在PageRank的算法中，要求结果向量的L2范式为1，所以需要将每个孩子的豌豆数量减少到例子中的1/30；另外，我们看到的网页PageRank值，实际上是通过对算法的结果求对数得到的。但算法的本质没有大的不同，所以这里不再赘述。
[5] 随机行走模型，来自Wikipedia：http://en.wikipedia.org/wiki/Random_walk
[6] 向量的L1范式，即向量中每一项的绝对值之和。
[7] 马尔可夫过程，来自Wikipedia：http://en.wikipedia.org/wiki/Markov_chain
[8] LZMA算法，来自Wikipedia：http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Markov_chain_algorithm