一. 引言

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

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

本文要談的就是這個數學因素。

谷歌作為一個搜索引擎， 它的核心功能顧名思義， 就是網頁搜索。 說到搜索， 我們都不陌生， 因為那是凡地球人都會的技能。 我們在字典里查個生字， 在圖書館里找本圖書， 甚至在商店里尋一種商品， 等等， 都是搜索。 只要稍稍推究一下， 我們就會發現那些搜索之所以可能， 并且人人都會， 在很大程度上得益于以下三條：

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

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

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

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

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

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

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

二. 基本思路

正是在這種情況下， 1996 年初， 谷歌公司的創始人， 當時還是美國斯坦福大學 (Stanford University) 研究生的佩奇 (Larry Page) 和布林 (Sergey Brin) 開始了對網頁排序問題的研究。 這兩位小伙子之所以研究網頁排序問題， 一來是導師的建議 (佩奇后來稱該建議為 “我有生以來得到過的最好建議”)， 二來則是因為他們對這一問題背后的數學產生了興趣。

網頁排序問題的背后有什么樣的數學呢？ 這得從佩奇和布林看待這一問題的思路說起。

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

思路雖然有了， 具體計算卻并非易事， 因為按照這種思路， 想要知道一個網頁 Wi 的排序， 不僅要知道有多少網頁鏈接了它， 而且還得知道那些網頁各自的排序——因為來自排序靠前網頁的鏈接更有分量。 但作為互聯網大家庭的一員， Wi 本身對其它網頁的排序也是有貢獻的， 而且基于來自排序靠前網頁的鏈接更有分量的原則， 這種貢獻與 Wi 本身的排序也有關。 這樣一來， 我們就陷入了一個 “先有雞還是先有蛋” 的循環： 要想知道 Wi 的排序， 就得知道與它鏈接的其它網頁的排序， 而要想知道那些網頁的排序， 卻又首先得知道 Wi 的排序。

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

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

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

這里 pj→i 是一個描述互聯網鏈接結構的指標函數 (indicator function)， 其定義是： 如果網頁 Wj 有鏈接指向網頁 Wi， 則 pj→i 取值為 1， 反之則為 0。 顯然， 這條假設所體現的正是前面提到的佩奇和布林的排序原則， 因為右端求和式的存在表明與 Wi 有鏈接的所有網頁 Wj 都對 Wi 的排名有貢獻， 而求和式中的每一項都正比于 pj， 則表明來自那些網頁的貢獻與它們的自身排序有關， 自身排序越靠前 (即 pj 越大)， 貢獻就越大。

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

pn+1 = Hpn

這就是計算網頁排序的公式。

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

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

pn = Hnp0

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