1707611852
细心的读者可能注意到了，我们还遗漏了一样东西，那就是谷歌矩阵中描述虚拟用户“性格”的那个α参数。那个参数的数值是多少呢？从理论上讲，它应该来自于对真实用户平均行为的分析，不过实际上另有一个因素对它的选取产生了很大影响，那就是Gnp0收敛于p的快慢程度。由于G是一个NXN矩阵，而N为互联网上——确切地说是被谷歌所收录的——网页的总数，在谷歌成立之初为几千万，目前为几百亿（并且还在持续增加），是一个极其巨大的数字。因此G是一个超大型矩阵，甚至很可能是人类有史以来处理过的最庞大的矩阵。对于这样的矩阵，Gnp0收敛速度的快慢是关系到算法是否实用的重要因素，而这个因素恰恰与α有关。可以证明，α越小，Gnp0的收敛速度就越快。但α也不能太小，因为太小的话，“佩奇排序”中最精华的部分，即以网页间的彼此链接为基础的排序思路就被弱化了（因为这部分的贡献正比于α），这显然是得不偿失的。因此，在α的选取上有很多折中的考虑要做，佩奇和布林最终选择的数值是α=0.85。
1707611853
1707611854
以上就是谷歌背后最重要的数学奥秘。与以往那种凭借关键词出现次数所作的排序不同，这种由所有网页的相互链接所确定的排序是不那么容易做假的，因为作假者再是把自己的网页吹得天花乱坠，如果没有真正吸引人的内容，别人不链接它，一切就还是枉然[7]。而且“佩奇排序”还有一个重要特点，那就是它只与互联网的结构有关，而与用户具体搜索的东西无关。这意味着排序计算可以单独进行，而无需在用户键入搜索指令后才临时进行。谷歌搜索的速度之所以快捷，在很大程度上得益于此。
1707611855
1707611856
1707611857
1707611858
1707611859
因为星星在那里：科学殿堂的砖与瓦 [:1707611259]
1707611860
因为星星在那里：科学殿堂的砖与瓦 四、结语
1707611861
1707611862
在本文的最后，我们顺便介绍一点谷歌公司的历史。佩奇和布林对谷歌算法的研究由于需要收集和分析大量网页间的相互链接，从而离不开硬件支持。为此，早在研究阶段，他们就四处奔走，为自己的研究筹集资金和硬件。1998年9月，他们为自己的试验系统注册了公司——即如今大名鼎鼎的谷歌公司。但这些行为虽然近乎于创业，他们两人当时却并无长期从商的兴趣。1999年，当他们觉得打理公司干扰了自己的研究时，甚至萌生了卖掉公司的想法。
1707611863
1707611864
他们的开价是100万美元。
1707611865
1707611866
与谷歌在短短几年之后的惊人身价相比，那简直就是“跳楼大甩卖”。可惜当时却无人识货。佩奇和布林在硅谷“叫卖”了一圈，连一个买家都没找到。被他们找过的公司包括了当时搜索业巨头之一的Excite（该公司后来想必连肠子都悔青了）。为了不让自己的心血荒废，佩奇和布林只得将公司继续办了下去，一直办到今天，这就是谷歌的“发家史”。
1707611867
1707611868
谷歌成立之初跟其他一些“发迹于地下室”（one-man-in-basement）的IT公司一样寒酸：雇员只有一位（两位老板不算），工作场所则是一位朋友的车库。但它出类拔萃的排序算法很快为它赢得了声誉。公司成立仅仅3个月，PC Magzine杂志就把谷歌列为了年度最佳搜索引擎。2001年，佩奇为“佩奇排序”申请到了专利，专利的发明人为佩奇，拥有者则是他和布林的母校斯坦福大学。2004年8月，谷歌成为了一家初始市值约17亿美元的上市公司。不仅公司高管在一夜间成为了亿万富翁，就连当初给过他们几十美元“赞助费”的某些同事和朋友也得到了足够终身养老所用的股票回报。作为公司摇篮的斯坦福大学则因拥有“佩奇排序”的专利而获得了180万股谷歌股票。2005年12月，斯坦福大学通过卖掉那些股票获得了3.36亿美元的巨额收益，成为美国高校因支持技术研发而获得的有史以来最巨额的收益之一[8]。
1707611869
1707611870
1707611871
1707611872
1707611873
谷歌公司创始人佩奇（左）和布林（右）
1707611874
1707611875
谷歌在短短数年间就横扫整个互联网，成为搜索引擎业的新一代霸主，佩奇和布林的那个排序算法无疑居功至伟，可以说，是数学成就了谷歌[9]。当然，这么多年过去了，谷歌作为IT界研发能力最强的公司之一，它的网页排序方法早已有了巨大的改进，由当年单纯依靠“佩奇排序”演变为了由200多种来自不同渠道的信息——其中包括与网页访问量有关的统计数据——综合而成的更加可靠的方法。而当年曾给佩奇和布林带来过启示的学术界，则反过来从谷歌的成功中借鉴了经验，如今一些学术机构对论文影响因子（impact factor）的计算已采用了类似“佩奇排序”的算法。谷歌的发展极好地印证了培根（Francis Bacon）的一句名言：知识就是力量。
1707611876
1707611877
参考文献
1707611878
1707611879
[1] Austin D. How Google finds your needle in the Web’s haystack[OL]. http://www.ams.org/samplings/feature-column/fcarc-pagerank.
1707611880
1707611881
[2] Battelle J. The birth of Google[J]. Wired, August 2005.
1707611882
1707611883
[3] Brin S, Page L. The anatomy of a large-scale hypertextual web search engine[C]. Seventh International World-Wide Web Conference, Brisbane, Australia, April 14-18, 1998.
1707611884
1707611885
[4] Ibe O. Markov processes for stochastic modeling[M]. Amsterdam: Elsevier Academic Press, 2009.
1707611886
1707611887
[5] Langville A N, Meyer C D. Google’s page rank and beyond: the Science of search engine rankings[M]. Princeton: Princeton University Press, 2006.
1707611888
1707611889
[6] Rousseau C, Saint-Aubin Y. Mathematics and technology[M]. Berlin: Springer, 2008.
1707611890
1707611891
2010年12月4日写于纽约
1707611892
1707611893
[1]本文曾发表于《数学文化》2011年2月刊（山东大学与香港浸会大学合办）。
1707611894
1707611895
[2]马尔可夫过程，也称为马尔可夫链（Markov chain），是一类离散随机过程，它的最大特点是每一步的转移概率分布都只与前一步有关。而平稳马尔可夫过程则是指转移概率分布与步数无关的马尔可夫过程（体现在我们的例子中，即H与n无关）。另外要说明的是，本文在表述上不同于佩奇和布林的原始论文，后者并未使用诸如“马尔可夫过程”或“马尔可夫链”那样的术语，也并未直接运用这一领域内的数学定理。
1707611896
1707611897
[3]在更细致的分类中，这种每一列的矩阵元之和都为1的随机矩阵称为左随机矩阵（left stochastic matrix），以区别于每一行的矩阵元之和都等于1的所谓右随机矩阵（right stochastic matrix）。这两者在应用上基本是等价的，区别往往只在于约定。
1707611898
1707611899
[4]这种几乎满足随机矩阵条件，但有些列（或行）的矩阵元之和小于1的矩阵也有一个名称，叫做亚随机矩阵（substochastic matrix）。
1707611900
1707611901
[5]确切地说，这种所有矩阵元都为正的矩阵不仅是素矩阵，而且还是所谓的正矩阵（positive matrix）。这两者的区别是：正矩阵要求所有矩阵元都为正，而素矩阵只要求自己的某个正整数次幂为正矩阵。