谷歌背后的数学( 三 ) _小知识

上述公式的求解是简单得不能再简单的事情，即：
pn = Hnp0
其中 p0 为虚拟读者初次浏览时访问各网页的几率分布 (在佩奇和布林的原始论文中，这一几率分布被假定为是均匀分布) 。
如前所述，佩奇和布林是用虚拟用户在经过很长 (理论上为无穷长) 时间的漫游后访问各网页的几率分布，即 limn→∞pn，来确定网页排序的。这个定义要想管用，显然要解决三个问题：
极限 limn→∞pn 是否存在?
如果极限存在，它是否与 p0 的选取无关?
如果极限存在，并且与 p0 的选取无关，它作为网页排序的依据是否真的合理?
如果这三个问题的答案都是肯定的，那么网页排序问题就算解决了。反之，哪怕只有一个问题的答案是否定的，网页排序问题也就不能算是得到满意的解决。那么实际答案如何呢? 很遗憾，是后一种，而且是其中最糟糕的情形，即三个问题的答案全都是否定的。这可以由一些简单的例子看出。比方说，在只包含两个相互链接网页的迷你型互联网上，如果 p0 = (1, 0)T，极限就不存在 (因为几率分布将在 (1, 0)T和 (0, 1)T 之间无穷振荡) 。而存在几个互不连通 (即互不链接) 区域的互联网则会使极限——即便存在——与 p0 的选取有关 (因为把 p0 选在不同区域内显然会导致不同极限) 。至于极限存在，并且与 p0 的选取无关时它作为网页排序的依据是否真的合理的问题，虽然不是数学问题，答案却也是否定的，因为任何一个 “悬挂网页” 都能象黑洞一样，把其它网页的几率 “吸收” 到自己身上 (因为虚拟用户一旦进入那样的网页，就会由于没有对外链接而永远停留在那里)，这显然是不合理的。这种不合理效应是如此显著，以至于在一个连通性良好的互联网上，哪怕只有一个 “悬挂网页”，也足以使整个互联网的网页排序失效，可谓是 “一粒老鼠屎坏了一锅粥” 。
为了解决这些问题，佩奇和布林对虚拟用户的行为进行了修正。首先，他们意识到无论真实用户还是虚拟用户，当他们访问到 “悬挂网页” 时，都不可能也不应该 “在一棵树上吊死”，而是会自行访问其它网页。对于真实用户来说，自行访问的网页显然与各人的兴趣有关，但对于在平均意义上代表真实用户的虚拟用户来说，佩奇和布林假定它将会在整个互联网上随机选取一个网页进行访问。用数学语言来说，这相当于是把 H 的列向量中所有的零向量都换成 e/N (其中 e 是所有分量都为 1 的列向量， N 为互联网上的网页总数) 。如果我们引进一个描述 “悬挂网页” 的指标向量 (indicator vector) a，它的第 i 个分量的取值视 Wi 是否为 “悬挂网页” 而定，如果是 “悬挂网页”，取值为 1，否则为零，并用 S 表示修正后的矩阵，则：
S = H + aeT/N
显然，这样定义的 S 矩阵的每一列的矩阵元之和都是 1，从而是一个不折不扣的随机矩阵。这一修正因此而被称为随机性修正 (stochasticity adjustment) 。这一修正相当于剔除了 “悬挂网页”，从而可以给上述第三个问题带来肯定回答 (当然，这一回答没有绝对标准，可以不断改进) 。不过，这一修正解决不了前两个问题。为了解决那两个问题，佩奇和布林引进了第二个修正。他们假定，虚拟用户虽然是虚拟的，但多少也有一些 “性格”，不会完全死板地只访问当前网页所提供的链接。具体地说，他们假定虚拟用户在每一步都有一个小于 1 的几率 α 访问当前网页所提供的链接，同时却也有一个几率 1-α 不受那些链接所限，随机访问互联网上的任何一个网站。用数学语言来说 (请读者自行证明)，这相当于是把上述 S 矩阵变成了一个新的矩阵 G：
G = αS + (1-α)eeT/N
这个矩阵不仅是一个随机矩阵，而且由于第二项的加盟，它有了一个新的特点，即所有矩阵元都为正 (请读者想一想，这一特点的 “物理意义” 是什么?)，这样的矩阵是所谓的素矩阵 (primitive matrix)[注四] 。这一修正因此而被称为素性修正 (primitivity adjustment) 。
经过这两类修正，网页排序的计算方法就变成了：
pn = Gnp0
这个算法能给上述问题提供肯定答案吗? 是的，它能。因为随机过程理论中有一个所谓的马尔可夫链基本定理 (Fundamental Theorem of Markov Chains)，它表明在一个马尔可夫过程中，如果转移矩阵是素矩阵，那么上述前两个问题的答案就是肯定的。而随机性修正已经解决了上述第三个问题，因此所有问题就都解决了。如果我们用 p 表示 pn 的极限[注五]，则 p 给出的就是整个互联网的网页排序——它的每一个分量就是相应网页的访问几率，几率越大，排序就越靠前。