一. 引言

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

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

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

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

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

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

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

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

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

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

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

二. 基本思路

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

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

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

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

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

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

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

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

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

pn+1 = Hpn

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

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

上述公式的求解是簡單得不能再簡單的事情， 即：

pn = Hnp0

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