World of Mathematics数学烟云 +5 0.10 0.70 S 1 a 1.0 0.20 0.5 0.95 a a 0.5 04 0.05 a 06人a0 040 a 0.30 2 马尔可夫过程( Markov process在谷歌算法里占据了重要的地位。我们称离散的马尔可夫过程为马尔可夫链;其在各个时刻的状态转变由 个概率矩阵所控制。这是一个马尔可夫过程的例子 如果这三个问题的答案都是肯定的,那么网页排序问题样的网页,就会由于没有对外链接而永远停留在那里),这 就算解决了。反之,哪怕只有一个问题的答案是否定的,网显然是不合理的。这种不合理效应是如此显著,以至于在 页排序问题也就不能算是得到满意的解决。那么实际答案如个连通性良好的互联网上,哪怕只有一个“悬挂网页”,也足 何呢?很遗憾,是后一种,而且是其中最糟糕的情形,即 以使整个互联网的网页排序失效,可谓是“一粒老鼠屎坏了 个问题的答案全都是否定的。这可以由一些简单的例子看一锅粥”。 出。比方说,在只包含两个相互链接网页的迷你型互联网上, 为了解决这些问题,佩奇和布林对虚拟用户的行为进行 如果p=(1,0)2,极限就不存在(因为几率分布将在(1,0)了修正。首先,他们意识到无论真实用户还是虚拟用户,当 和(0,1)2之间无穷振荡)。而存在几个互不连通(即互不链他们访问到“悬挂网页”时,都不可能也不应该“在一棵树 接)区域的互联网则会使极限——即便存在一与p的选取上吊死”,而是会自行访问其它网页。对于真实用户来说,自 有关(因为把p选在不同区域内显然会导致不同极限)。至行访问的网页显然与各人的兴趣有关,但对于在平均意义上 于极限存在,并且与p的选取无关时它作为网页排序的依代表真实用户的虚拟用户来说,佩奇和布林假定它将会在整 据是否真的合理的问题,虽然不是数学问题,答案却也是否个互联网上随机选取一个网页进行访问。用数学语言来说 定的,因为任何一个“悬挂网页”都能象黑洞一样,把其它这相当于是把H的列向量中所有的零向量都换成e/N(其中 网页的几率“吸收”到自己身上(因为虚拟用户一旦进入那e是所有分量都为1的列向量,N为互联网上的网页总数)。 数学文化/第2卷第1期15World of Mathematics 数学烟云 数学文化/第2卷第1期 15 如果这三个问题的答案都是肯定的，那么网页排序问题 就算解决了。反之，哪怕只有一个问题的答案是否定的，网 页排序问题也就不能算是得到满意的解决。那么实际答案如 何呢？很遗憾，是后一种，而且是其中最糟糕的情形，即三 个问题的答案全都是否定的。这可以由一些简单的例子看 出。比方说，在只包含两个相互链接网页的迷你型互联网上， 如果 p0 = (1, 0) T ，极限就不存在 ( 因为几率分布将在 (1, 0) T 和 (0, 1) T 之间无穷振荡 )。而存在几个互不连通（即互不链 接）区域的互联网则会使极限——即便存在——与 p0的选取 有关（因为把 p0 选在不同区域内显然会导致不同极限）。至 于极限存在，并且与 p0 的选取无关时它作为网页排序的依 据是否真的合理的问题，虽然不是数学问题，答案却也是否 定的，因为任何一个“悬挂网页”都能象黑洞一样，把其它 网页的几率“吸收”到自己身上（因为虚拟用户一旦进入那 样的网页，就会由于没有对外链接而永远停留在那里），这 显然是不合理的。这种不合理效应是如此显著，以至于在一 个连通性良好的互联网上，哪怕只有一个“悬挂网页”，也足 以使整个互联网的网页排序失效，可谓是“一粒老鼠屎坏了 一锅粥”。 为了解决这些问题，佩奇和布林对虚拟用户的行为进行 了修正。首先，他们意识到无论真实用户还是虚拟用户，当 他们访问到“悬挂网页”时，都不可能也不应该“在一棵树 上吊死”，而是会自行访问其它网页。对于真实用户来说，自 行访问的网页显然与各人的兴趣有关，但对于在平均意义上 代表真实用户的虚拟用户来说，佩奇和布林假定它将会在整 个互联网上随机选取一个网页进行访问。用数学语言来说， 这相当于是把 H 的列向量中所有的零向量都换成 e/N（其中 e 是所有分量都为 1 的列向量，N 为互联网上的网页总数）。 马尔可夫过程 (Markov process) 在谷歌算法里占据了重要的地位。我们称离散的马尔可夫过程为马尔可夫链；其在各个时刻的状态转变由 一个概率矩阵所控制。这是一个马尔可夫过程的例子。 S S S 0 0 0 0 1 1 1 1 2 a a a a a a 0.5 0.5 0.6 1.0 0.4 0.20 0.70 0.10 +5 -1 0.95 0.05 0.40 0.30 0.30