一. 引言

在如今這個互聯(lián)網(wǎng)時代， 有一家公司家喻戶曉——它自 1998 年問世以來， 在極短的時間內(nèi)就聲譽鵲起， 不僅超越了所有競爭對手， 而且徹底改觀了整個互聯(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)頁搜索。 說到搜索， 我們都不陌生， 因為那是凡地球人都會的技能。 我們在字典里查個生字， 在圖書館里找本圖書， 甚至在商店里尋一種商品， 等等， 都是搜索。 只要稍稍推究一下， 我們就會發(fā)現(xiàn)那些搜索之所以可能， 并且人人都會， 在很大程度上得益于以下三條：

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

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

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

但互聯(lián)網(wǎng)的鮮明特點卻是以上三條無一滿足。 事實上， 即便在谷歌問世之前， 互聯(lián)網(wǎng)上的網(wǎng)頁總數(shù)就已超過了諸如圖書館藏書數(shù)量之類傳統(tǒng)搜索對象的數(shù)目。 而且這還只是冰山一角， 因為與搜索圖書時單純的書名搜索不同， 互聯(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ù)度更是以快得不能再快的速度走向失控。 這其實是可以預(yù)料的， 因為幾乎所有網(wǎng)頁都離不開幾千個常用詞， 因此除非搜索生僻詞， 否則出現(xiàn)幾十萬、 幾百萬、 甚至幾千萬條搜索結(jié)果都是不足為奇的。

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

這致命傷該如何治療呢？ 藥方其實很簡單， 那就是對搜索結(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ù)不能說毫無道理， 因為用戶搜索一個詞語， 通常表明對該詞語感興趣。 既然如此， 那該詞語在網(wǎng)頁中的出現(xiàn)次數(shù)越多， 就越有可能表示該網(wǎng)頁是用戶所需要的。 可惜的是， 這個貌似合理的方法實際上卻行不大通。 因為按照這種方法， 任何一個象祥林嫂一樣翻來復(fù)去倒騰某些關(guān)鍵詞的網(wǎng)頁， 無論水平多爛， 一旦被搜索到， 都立刻會 “金榜題名”， 這簡直就是廣告及垃圾網(wǎng)頁制造者的天堂。 事實上， 當(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)師的建議 (佩奇后來稱該建議為 “我有生以來得到過的最好建議”)， 二來則是因為他們對這一問題背后的數(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é)問題。

思路雖然有了， 具體計算卻并非易事， 因為按照這種思路， 想要知道一個網(wǎng)頁 Wi 的排序， 不僅要知道有多少網(wǎng)頁鏈接了它， 而且還得知道那些網(wǎng)頁各自的排序——因為來自排序靠前網(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 之后， 下一步點擊那些鏈接當(dāng)中的任何一個的幾率均為 1/Ni。 初看起來， 這一假設(shè)并不合理， 因為任何用戶都有偏好， 怎么可能以相同的幾率訪問一個網(wǎng)頁的所有鏈接呢？ 但如果我們考慮到佩奇和布林的虛擬用戶實際上是對互聯(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)的正是前面提到的佩奇和布林的排序原則， 因為右端求和式的存在表明與 Wi 有鏈接的所有網(wǎng)頁 Wj 都對 Wi 的排名有貢獻(xiàn)， 而求和式中的每一項都正比于 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

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

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

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

pn = Hnp0

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