9 月 27 日谷歌推出新款doodle，慶祝自己 13 歲生日。在這個世界上，谷歌幾乎無人不曉了。但鮮為人知的是，在13年前，拉裏 佩奇( Larry Page )和謝爾蓋 布林( Sergey Brin )正是依靠先進的算法發家並創立谷歌的。在這個世界上最自由和創新公司的生日裏，來聽聽死理性派講述它當年的數學故事吧。

　　一個正常的搜索引擎，其核心功能自然是網頁搜索。那搜索結果應該怎樣排序才最好呢？實際上，在谷歌主導互聯網搜索之前，人們為此傷透腦筋。

　　當時人們認為，通過判斷能夠得知哪個網頁更重要，對搜索引擎的發展十分有幫助——很顯然，搜索引擎應該把重要的網頁放到搜索結果中比較靠前的地方。

　　這個問題看起來很容易，但是解決的方法卻沒有想象的那麼簡單。

　　在谷歌誕生之前那段時間，流行的網頁排名算法都很類似，它們都使用了一個非常簡單的思想：越是重要的網頁，訪問量就會越大。許多大公司就通過統計網頁的訪問量來進行網頁排名。但是這種排名算法有兩個很顯著的問題：一是因為只能夠抽樣統計，所以統計數據不一定準確，而且訪問量的波動會比較大，想要得到準確的統計需要大量的時間和人力，還只能維持很短的有效時間；二是訪問量並不一定能體現網頁的“重要程度”——可能一些比較早接觸互聯網的網民還記得，那時有很多人推出了專門“刷訪問量”的服務。有沒有更好的方法，不統計訪問量就能夠為網頁的重要度排序呢？

　　就是在這種情況下,1996 年初，谷歌公司的創始人，當時還是美國斯坦福大學研究生的佩奇和布林開始了對網頁排序問題的研究。在1999年，一篇以佩奇為第一作者的論文發表了，論文仲介紹了一種叫做 PageRank 的算法，這種算法的主要思想是：越“重要”的網頁，頁面上的鏈結質量也越高，同時越容易被其它“重要”的網頁鏈結。於是，算法完全利用網頁之間互相鏈結的關係來計算網頁的重要程度，將網頁排序徹底變成一個數學問題，終於擺脫了訪問量統計的框框。

　　在詳細講述這個算法之前，不妨讓我們用一個遊戲，先來簡單模擬一下 PageRank 算法的運行過程，以便讀者更好地理解。

　　三兄弟分 30 顆豌豆。起初每人 10 顆，他們每次都要把手裏的豌豆全部平均分給自己喜歡的人。下圖表示了三兄弟各自擁有的初始豌豆數量，以及相互喜歡的關係（箭頭方向表示喜歡，例如老二喜歡老大，老大喜歡老二和老三）。

第一次分配後，我們會得到結果如下：

就這樣，讓遊戲一直進行下去。直到他們手中的豌豆數不再變化為止。

　　那麼這個遊戲到底是否可以結束呢，如果可以，最終的結果又是什麼樣的？在此我們用電腦模擬了這個過程，得出的結果是：老大和老二的盤子裏各有 12 顆豌豆，而老三的盤子裏有 6 顆豌豆。這時候無論遊戲怎麼進行下去，盤子裏的豌豆數量都不會再變化。

　　看到這裡，讀者可能會問：這個遊戲和網頁排序有什麼關係？實際上， PageRank 會給每個網頁一個數值，這個數值越高，就説明這個網頁越“重要”。而剛剛的遊戲中，如果把豌豆的數量看作這個數值（可以不是整數），把孩子們看作網頁，那麼遊戲的過程就是 PageRank 的算法，而遊戲結束時豌豆的分配，就是網頁的 PageRank 值。

　　不同於之前的訪問量統計，PageRank 求解了這樣一個問題：一個人在網絡上瀏覽網頁，每看過一個網頁之後就會隨機點擊網頁上的鏈結訪問新的網頁。如果當前這個人瀏覽的網頁 x 已經確定，那麼網頁 x 上每個鏈結被點擊的概率也是確定的，可以用向量 Nx 表示。在這種條件下，這個人點擊了無限多次鏈結後，恰好停留在每個網頁上的概率分別是多少？

　　在這個模型中，我們用向量 Ri 來表示點擊了 i 次鏈結之後可能停留在每個網頁上的概率（ R 0 則為一開始就打開了每個網頁的概率，後面我們將證明 R 0 的取值對最終結果沒有影響）。很顯然 R i 的 L1 範式為 1 ，這也是 PageRank 算法本身的要求。

　　仍以上面的遊戲為例，整個瀏覽過程的一開始，我們有：

　　其中， A 表示每一次點擊鏈結概率的矩陣。 A 的第 i 列第 j 行 A i, j 的含義是，如果當前訪問的網頁是網頁i，那麼下一次點擊鏈結跳轉到網頁 j 的概率為 A i, j 。

　　這樣設計矩陣 A 的好處是，通過矩陣 A 和向量 R n-1 相乘，即可得出點擊一次鏈結後每個網頁可能的停留概率向量 R n 。例如，令 R 1　= A R 0 ，可以得到點擊一次鏈結後停留在每個網頁的概率：

　　之後一直迭代下去，有：

　　對於上面的例子，迭代結果如下圖：

可以看到，每個網頁停留的概率在振蕩之後趨於穩定。

　　在這種穩定狀態下，我們可以知道，無論如何迭代，都有 R n = R n-1 。這樣我們就獲得了一個方程：

　　而整個迭代的過程，就是在尋求方程 R = AR 的解。而無論 R 0 是多少，迭代無限多次之後，一定會取得令 R = AR 成立的 R 值。整個求解 R 的過程，就如同一個人在一張地圖上的不同位置之間隨機地行走一樣，所以被稱為“隨機行走模型”。

　　隨機行走模型有一個顯著的特點，那就是每一次迭代的結果只與前一次有關，與更早的結果完全無關。這種過程又被稱為馬爾可夫過程（ Markov Process ）或馬爾可夫鏈（ Markov Chain ）。

　　馬爾可夫過程的數學定義是：如果對於一個隨機變量序列 X 0 、 X 1 、 X 2 、…， 其中 X n 表示時間 n 的狀態及轉移概率P，有：

　　即 X n 只受 X n-1 的影響，則此過程成為馬爾可夫過程。其中 P( X n+1 | X n ) 稱作“一步轉移概率”，而兩步、三步轉移概率則可以通過一步轉移概率的積分求得。

　　當狀態空間有限時，轉移概率可以用用一個矩陣 A 來表示，稱作轉移矩陣（ transition matrix ）。此時轉移概率的積分即為矩陣的冪，k步轉移概率可以用 A k 表示，這也是隨機行走模型中的情況。而對於一個正的（每個元素都為正的）轉移矩陣 A ，可以證明一定有：

這就完整解釋了為什麼 R 0 的取值對最終結果沒有影響。

　　但是這裡有一個問題：即便 R 0 的取值對最終結果沒有影響，用 R 作為網頁排序的依據是否真的合理？

　　其實並不合理，因為當一個網頁只有鏈入鏈結沒有鏈出鏈結的時候，這個網頁就會像一個“黑洞”一樣，將同一個連通子圖中其它網頁流向它的 PageRank 慢慢“吞掉”（因為算法中虛擬的用戶一旦進入那樣的網頁， 就會由於沒有對外鏈結而永遠停留在那裏），這種網頁我們稱之為“懸挂網頁”（ Dangling Link ）。這種“黑洞”效應是如此顯著， 以至於在一個連通性良好的互聯網上， 哪怕只有一個 “懸挂網頁”， 也足以使整個互聯網的網頁排序失效， 可謂是 “一粒老鼠屎壞了一鍋粥”。

　　為了解決這個問題，佩奇和布林進行了修正。他們意識到， 當用戶訪問到 “懸挂網頁” 時， 都不可能也不應該就停留在了這個頁面， 而是會自行訪問其它網頁。雖然對每個用戶來説， 自行訪問的網頁與各人的興趣有關，但在平均意義上來講，佩奇和布林假定用戶將會在整個互聯網上隨機選取一個網頁進行訪問。

　　所以他們給 PageRank 算法加入了一個新的向量 E。它的作用是，按照其中所描述的比例來向全部網頁分配懸挂網頁每一次“吞掉”的 PageRank。這樣，相當於為懸挂網頁添加了鏈向網絡上全部網頁的鏈結，避免了懸挂鏈結的出現。

　　以上就是谷歌背後最重要的數學奧秘。 與以往那種憑藉關鍵詞出現次數所作的排序不同， 這種由所有網頁的相互鏈結所確定的排序是不那麼容易做假的， 因為做假者再是把自己的網頁吹得天花亂墜， 如果沒有真正吸引人的內容， 別人不鏈結它， 一切就還是枉然。 而且 “佩奇排序” 還有一個重要特點， 那就是它只與互聯網的結構有關， 而與用戶具體搜索的東西無關。 這意味著排序計算可以單獨進行， 而無需在用戶鍵入搜索指令後才臨時進行。 谷歌搜索的速度之所以快捷， 在很大程度上得益於此。

　　不過要強調的是，雖然PageRank是Google搜索結果排序的重要依據並以此發家，不過它並不是全部依據——實際上，Google發展到現在，已同時用了數百種不同的算法來確定最終顯示給用戶的搜索結果順序。

　　關於PageRank還有一個小故事。拉裏 佩奇是Google的創始人之一，也是現任Google的CEO。有意思的是：“佩奇”的英文是“Page”，恰好與“PageRank”的“Page”相吻合。這是巧合還是有意為之呢？在網絡上筆者可以找到的許多資料中，均提到PageRank是以拉裏 佩奇的姓命名。但是所有這些資料都沒有提到這條信息的來源，所以其真實性無從得證。

　　不過，既然佩奇本人沒有出來解釋，那我們也沒有必要糾結于Page的含義了。或許這個詞本身就是佩奇利用雙關語向我們開的一個小玩笑呢！

　　參考資料：

　　[1] 盧昌海， 谷歌背後的數學

　　[2] L. Page, S. Brin, R. Motwani and T. Winograd. The PageRank Citation Ranking: Bring Order to the Web. Jan, 1998.

　　[3] 維基百科： 馬爾可夫過程