一. 引言

在如今這個(gè)互聯(lián)網(wǎng)時(shí)代， 有一家公司家喻戶(hù)曉——它自 1998 年問(wèn)世以來(lái)， 在極短的時(shí)間內(nèi)就聲譽(yù)鵲起， 不僅超越了所有競(jìng)爭(zhēng)對(duì)手， 而且徹底改觀了整個(gè)互聯(lián)網(wǎng)的生態(tài)。 這家公司就是當(dāng)今互聯(lián)網(wǎng)上的第一搜索引擎： 谷歌 (Google)。

在這樣一家顯赫的公司背后， 自然有許許多多商戰(zhàn)故事， 也有許許多多成功因素。 但與普通商戰(zhàn)故事不同的是， 在谷歌的成功背后起著最關(guān)鍵作用的卻是一個(gè)數(shù)學(xué)因素。

本文要談的就是這個(gè)數(shù)學(xué)因素。

谷歌作為一個(gè)搜索引擎， 它的核心功能顧名思義， 就是網(wǎng)頁(yè)搜索。 說(shuō)到搜索， 我們都不陌生， 因?yàn)槟鞘欠驳厍蛉硕紩?huì)的技能。 我們?cè)谧值淅锊閭€(gè)生字， 在圖書(shū)館里找本圖書(shū)， 甚至在商店里尋一種商品， 等等， 都是搜索。 只要稍稍推究一下， 我們就會(huì)發(fā)現(xiàn)那些搜索之所以可能， 并且人人都會(huì)， 在很大程度上得益于以下三條：

1、搜索對(duì)象的數(shù)量較小——比如一本字典收錄的字通常只有一兩萬(wàn)個(gè)， 一家圖書(shū)館收錄的不重復(fù)圖書(shū)通常不超過(guò)幾十萬(wàn)種， 一家商店的商品通常不超過(guò)幾萬(wàn)種， 等等。

2、搜索對(duì)象具有良好的分類(lèi)或排序——比如字典里的字按拼音排序， 圖書(shū)館里的圖書(shū)按主題分類(lèi)， 商店里的商品按品種或用途分類(lèi)， 等等。

3、搜索結(jié)果的重復(fù)度較低——比如字典里的同音字通常不超過(guò)幾十個(gè)， 圖書(shū)館里的同名圖書(shū)和商店里的同種商品通常也不超過(guò)幾十種， 等等。

但互聯(lián)網(wǎng)的鮮明特點(diǎn)卻是以上三條無(wú)一滿(mǎn)足。 事實(shí)上， 即便在谷歌問(wèn)世之前， 互聯(lián)網(wǎng)上的網(wǎng)頁(yè)總數(shù)就已超過(guò)了諸如圖書(shū)館藏書(shū)數(shù)量之類(lèi)傳統(tǒng)搜索對(duì)象的數(shù)目。 而且這還只是冰山一角， 因?yàn)榕c搜索圖書(shū)時(shí)單純的書(shū)名搜索不同， 互聯(lián)網(wǎng)上的搜索往往是對(duì)網(wǎng)頁(yè)內(nèi)容的直接搜索， 這相當(dāng)于將圖書(shū)里的每一個(gè)字都變成了搜索對(duì)象， 由此導(dǎo)致的數(shù)量才是真正驚人的， 它不僅直接破壞了上述第一條， 而且連帶破壞了二、 三兩條。 在互聯(lián)網(wǎng)發(fā)展的早期， 象雅虎 (Yahoo) 那樣的門(mén)戶(hù)網(wǎng)站曾試圖為網(wǎng)頁(yè)建立分類(lèi)系統(tǒng)， 但隨著網(wǎng)頁(yè)數(shù)量的激增， 這種做法很快就 “掛一漏萬(wàn)” 了。 而搜索結(jié)果的重復(fù)度更是以快得不能再快的速度走向失控。 這其實(shí)是可以預(yù)料的， 因?yàn)閹缀跛芯W(wǎng)頁(yè)都離不開(kāi)幾千個(gè)常用詞， 因此除非搜索生僻詞， 否則出現(xiàn)幾十萬(wàn)、 幾百萬(wàn)、 甚至幾千萬(wàn)條搜索結(jié)果都是不足為奇的。

互聯(lián)網(wǎng)的這些 “不良特點(diǎn)” 給搜索引擎的設(shè)計(jì)帶來(lái)了極大的挑戰(zhàn)。 而在這些挑戰(zhàn)之中， 相對(duì)來(lái)說(shuō)， 對(duì)一、 二兩條的破壞是比較容易解決的， 因?yàn)槟侵饕菍?duì)搜索引擎的存儲(chǔ)空間和計(jì)算能力提出了較高要求， 只要有足夠多的錢(qián)來(lái)買(mǎi) “裝備”， 這些都還能算是容易解決的——套用電視連續(xù)劇《蝸居》中某貪官的臺(tái)詞來(lái)說(shuō)， “能用錢(qián)解決的問(wèn)題就不是大問(wèn)題”。 但對(duì)第三條的破壞卻要了命了， 因?yàn)闊o(wú)論搜索引擎的硬件如何強(qiáng)大， 速度如何快捷， 要是搜索結(jié)果有幾百萬(wàn)條， 那么任何用戶(hù)想從其中 “海選” 出自己真正想要的東西都是幾乎不可能的。 這一點(diǎn)對(duì)早期搜索引擎來(lái)說(shuō)可謂是致命傷， 而且它不是用錢(qián)就能解決的問(wèn)題。

這致命傷該如何治療呢？ 藥方其實(shí)很簡(jiǎn)單， 那就是對(duì)搜索結(jié)果進(jìn)行排序， 把用戶(hù)最有可能需要的網(wǎng)頁(yè)排在最前面， 以確保用戶(hù)能很方便地找到它們。 但問(wèn)題是： 網(wǎng)頁(yè)的水平千差萬(wàn)別， 用戶(hù)的喜好更是萬(wàn)別千差， 互聯(lián)網(wǎng)上有一句流行語(yǔ)叫做： “在互聯(lián)網(wǎng)上， 沒(méi)人知道你是一條狗” (On the Internet, nobody knows you're a dog)。 連用戶(hù)是人是狗都 “沒(méi)人知道”， 搜索引擎又怎能知道哪些搜索結(jié)果是用戶(hù)最有可能需要的， 并對(duì)它們進(jìn)行排序呢？

在谷歌主導(dǎo)互聯(lián)網(wǎng)搜索之前， 多數(shù)搜索引擎采用的排序方法， 是以被搜索詞語(yǔ)在網(wǎng)頁(yè)中的出現(xiàn)次數(shù)來(lái)決定排序——出現(xiàn)次數(shù)越多的網(wǎng)頁(yè)排在越前面。 這個(gè)判據(jù)不能說(shuō)毫無(wú)道理， 因?yàn)橛脩?hù)搜索一個(gè)詞語(yǔ)， 通常表明對(duì)該詞語(yǔ)感興趣。 既然如此， 那該詞語(yǔ)在網(wǎng)頁(yè)中的出現(xiàn)次數(shù)越多， 就越有可能表示該網(wǎng)頁(yè)是用戶(hù)所需要的。 可惜的是， 這個(gè)貌似合理的方法實(shí)際上卻行不大通。 因?yàn)榘凑者@種方法， 任何一個(gè)象祥林嫂一樣翻來(lái)復(fù)去倒騰某些關(guān)鍵詞的網(wǎng)頁(yè)， 無(wú)論水平多爛， 一旦被搜索到， 都立刻會(huì) “金榜題名”， 這簡(jiǎn)直就是廣告及垃圾網(wǎng)頁(yè)制造者的天堂。 事實(shí)上， 當(dāng)時(shí)幾乎沒(méi)有一個(gè)搜索引擎不被 “祥林嫂” 們所困擾， 其中最具諷刺意味的是： 在谷歌誕生之前的 1997 年 11 月， 堪稱(chēng)早期互聯(lián)網(wǎng)巨子的當(dāng)時(shí)四大搜索引擎在搜索自己公司的名字時(shí)， 居然只有一個(gè)能使之出現(xiàn)在搜索結(jié)果的前十名內(nèi)， 其余全被 “祥林嫂” 們擠跑了。

二. 基本思路

正是在這種情況下， 1996 年初， 谷歌公司的創(chuàng)始人， 當(dāng)時(shí)還是美國(guó)斯坦福大學(xué) (Stanford University) 研究生的佩奇 (Larry Page) 和布林 (Sergey Brin) 開(kāi)始了對(duì)網(wǎng)頁(yè)排序問(wèn)題的研究。 這兩位小伙子之所以研究網(wǎng)頁(yè)排序問(wèn)題， 一來(lái)是導(dǎo)師的建議 (佩奇后來(lái)稱(chēng)該建議為 “我有生以來(lái)得到過(guò)的最好建議”)， 二來(lái)則是因?yàn)樗麄儗?duì)這一問(wèn)題背后的數(shù)學(xué)產(chǎn)生了興趣。

網(wǎng)頁(yè)排序問(wèn)題的背后有什么樣的數(shù)學(xué)呢？ 這得從佩奇和布林看待這一問(wèn)題的思路說(shuō)起。

在佩奇和布林看來(lái)， 網(wǎng)頁(yè)的排序是不能靠每個(gè)網(wǎng)頁(yè)自己來(lái)標(biāo)榜的， 無(wú)論把關(guān)鍵詞重復(fù)多少次， 垃圾網(wǎng)頁(yè)依然是垃圾網(wǎng)頁(yè)。 那么， 究竟什么才是網(wǎng)頁(yè)排序的可靠依據(jù)呢？ 出生于書(shū)香門(mén)第的佩奇和布林 (兩人的父親都是大學(xué)教授) 想到了學(xué)術(shù)界評(píng)判學(xué)術(shù)論文重要性的通用方法， 那就是看論文的引用次數(shù)。 在互聯(lián)網(wǎng)上， 與論文的引用相類(lèi)似的是顯然是網(wǎng)頁(yè)的鏈接。 因此， 佩奇和布林萌生了一個(gè)網(wǎng)頁(yè)排序的思路， 那就是通過(guò)研究網(wǎng)頁(yè)間的相互鏈接來(lái)確定排序。 具體地說(shuō)， 一個(gè)網(wǎng)頁(yè)被其它網(wǎng)頁(yè)鏈接得越多， 它的排序就應(yīng)該越靠前。 不僅如此， 佩奇和布林還進(jìn)一步提出， 一個(gè)網(wǎng)頁(yè)越是被排序靠前的網(wǎng)頁(yè)所鏈接， 它的排序就也應(yīng)該越靠前。 這一條的意義也是不言而喻的， 就好比一篇論文被諾貝爾獎(jiǎng)得主所引用， 顯然要比被普通研究者所引用更說(shuō)明其價(jià)值。 依照這個(gè)思路， 網(wǎng)頁(yè)排序問(wèn)題就跟整個(gè)互聯(lián)網(wǎng)的鏈接結(jié)構(gòu)產(chǎn)生了關(guān)系， 正是這一關(guān)系使它成為了一個(gè)不折不扣的數(shù)學(xué)問(wèn)題。

思路雖然有了， 具體計(jì)算卻并非易事， 因?yàn)榘凑者@種思路， 想要知道一個(gè)網(wǎng)頁(yè) Wi 的排序， 不僅要知道有多少網(wǎng)頁(yè)鏈接了它， 而且還得知道那些網(wǎng)頁(yè)各自的排序——因?yàn)閬?lái)自排序靠前網(wǎng)頁(yè)的鏈接更有分量。 但作為互聯(lián)網(wǎng)大家庭的一員， Wi 本身對(duì)其它網(wǎng)頁(yè)的排序也是有貢獻(xiàn)的， 而且基于來(lái)自排序靠前網(wǎng)頁(yè)的鏈接更有分量的原則， 這種貢獻(xiàn)與 Wi 本身的排序也有關(guān)。 這樣一來(lái)， 我們就陷入了一個(gè) “先有雞還是先有蛋” 的循環(huán)： 要想知道 Wi 的排序， 就得知道與它鏈接的其它網(wǎng)頁(yè)的排序， 而要想知道那些網(wǎng)頁(yè)的排序， 卻又首先得知道 Wi 的排序。

為了打破這個(gè)循環(huán)， 佩奇和布林采用了一個(gè)很巧妙的思路， 即分析一個(gè)虛擬用戶(hù)在互聯(lián)網(wǎng)上的漫游過(guò)程。 他們假定： 虛擬用戶(hù)一旦訪問(wèn)了一個(gè)網(wǎng)頁(yè)后， 下一步將有相同的幾率訪問(wèn)被該網(wǎng)頁(yè)所鏈接的任何一個(gè)其它網(wǎng)頁(yè)。 換句話(huà)說(shuō)， 如果網(wǎng)頁(yè) Wi 有 Ni 個(gè)對(duì)外鏈接， 則虛擬用戶(hù)在訪問(wèn)了 Wi 之后， 下一步點(diǎn)擊那些鏈接當(dāng)中的任何一個(gè)的幾率均為 1/Ni。 初看起來(lái)， 這一假設(shè)并不合理， 因?yàn)槿魏斡脩?hù)都有偏好， 怎么可能以相同的幾率訪問(wèn)一個(gè)網(wǎng)頁(yè)的所有鏈接呢？ 但如果我們考慮到佩奇和布林的虛擬用戶(hù)實(shí)際上是對(duì)互聯(lián)網(wǎng)上全體用戶(hù)的一種平均意義上的代表， 這條假設(shè)就不象初看起來(lái)那么不合理了。 那么網(wǎng)頁(yè)的排序由什么來(lái)決定呢？ 是由該用戶(hù)在漫游了很長(zhǎng)時(shí)間——理論上為無(wú)窮長(zhǎng)時(shí)間——后訪問(wèn)各網(wǎng)頁(yè)的幾率分布來(lái)決定， 訪問(wèn)幾率越大的網(wǎng)頁(yè)排序就越靠前。

為了將這一分析數(shù)學(xué)化， 我們用 pi(n) 表示虛擬用戶(hù)在進(jìn)行第 n 次瀏覽時(shí)訪問(wèn)網(wǎng)頁(yè) Wi 的幾率。 顯然， 上述假設(shè)可以表述為 (請(qǐng)讀者自行證明)：

pi(n+1) = Σj pj(n)pj→i/Nj

這里 pj→i 是一個(gè)描述互聯(lián)網(wǎng)鏈接結(jié)構(gòu)的指標(biāo)函數(shù) (indicator function)， 其定義是： 如果網(wǎng)頁(yè) Wj 有鏈接指向網(wǎng)頁(yè) Wi， 則 pj→i 取值為 1， 反之則為 0。 顯然， 這條假設(shè)所體現(xiàn)的正是前面提到的佩奇和布林的排序原則， 因?yàn)橛叶饲蠛褪降拇嬖诒砻髋c Wi 有鏈接的所有網(wǎng)頁(yè) Wj 都對(duì) Wi 的排名有貢獻(xiàn)， 而求和式中的每一項(xiàng)都正比于 pj， 則表明來(lái)自那些網(wǎng)頁(yè)的貢獻(xiàn)與它們的自身排序有關(guān)， 自身排序越靠前 (即 pj 越大)， 貢獻(xiàn)就越大。

為符號(hào)簡(jiǎn)潔起見(jiàn)， 我們將虛擬用戶(hù)第 n 次瀏覽時(shí)訪問(wèn)各網(wǎng)頁(yè)的幾率合并為一個(gè)列向量 pn， 它的第 i 個(gè)分量為 pi(n)， 并引進(jìn)一個(gè)只與互聯(lián)網(wǎng)結(jié)構(gòu)有關(guān)的矩陣 H， 它的第 i 行 j 列的矩陣元為 Hij = pj→i/Nj， 則上述公式可以改寫(xiě)為：

pn+1 = Hpn

這就是計(jì)算網(wǎng)頁(yè)排序的公式。

熟悉隨機(jī)過(guò)程理論的讀者想必看出來(lái)了， 上述公式描述的是一種馬爾可夫過(guò)程 (Markov process)， 而且是其中最簡(jiǎn)單的一類(lèi)， 即所謂的平穩(wěn)馬爾可夫過(guò)程 (stationary Markov process)， 而 H 則是描述馬爾可夫過(guò)程中的轉(zhuǎn)移概率分布的所謂轉(zhuǎn)移矩陣 (transition matrix)。 不過(guò)普通馬爾可夫過(guò)程中的轉(zhuǎn)移矩陣通常是隨機(jī)矩陣 (stochastic matrix)， 即每一列的矩陣元之和都為 1 的矩陣 (請(qǐng)讀者想一想， 這一特點(diǎn)的 “物理意義” 是什么？)。 而我們的矩陣 H 卻可能有一些列是零向量， 從而矩陣元之和為 0， 它們對(duì)應(yīng)于那些沒(méi)有對(duì)外鏈接的網(wǎng)頁(yè)， 即所謂的 “懸掛網(wǎng)頁(yè)” (dangling page)。

上述公式的求解是簡(jiǎn)單得不能再簡(jiǎn)單的事情， 即：

pn = Hnp0

其中 p0 為虛擬讀者初次瀏覽時(shí)訪問(wèn)各網(wǎng)頁(yè)的幾率分布 (在佩奇和布林的原始論文中， 這一幾率分布被假定為是均勻分布)。