核心概念#

本章介紹 Google 的核心算法之一——PageRank，一種基於「民主表決」思想的網頁排名技術。搜索結果的排名取決於兩組資訊：網頁的質量（Quality）和與查詢的相關性（Relevance），本章聚焦於前者。

1. PageRank 算法的原理#

• 最早嘗試給互聯網排序的是雅虎（目錄分類方式），但當時的搜索引擎（包括 AltaVista、Inktomi）都無法很好地排序搜索結果
• 這些公司注意到網頁之間的鏈接和錨文本（Anchor Text）可用於排序，但方法都不夠完善
• PageRank 的核心思想：如果一個網頁被很多其他網頁鏈接，說明它受到普遍認可和信賴，排名就高
• 不同網頁的鏈接權重不同：來自排名高的網頁的鏈接更可靠，給予較大權重——類似股東大會的表決權（Voting Power）

PageRank 的高明之處在於把整個互聯網當作一個整體來對待，而非將每個網頁視為獨立個體。這是一種系統論的觀點。

• 計算方式：網頁 $Y$ 的排名等於所有指向它的網頁 $X_1, X_2, \ldots, X_K$ 的權重之和
• 「先有雞還是先有蛋」的問題：計算網頁排名需要用到其他網頁的排名。佩奇想到用網頁本身的排名作為權重，布林則將問題轉化為二維矩陣相乘，用迭代法解決
• 迭代法：先假定所有網頁排名相同，根據初始值算出第一次排名，再據此算出第二次，如此反覆。不論初始值如何選取，排名最終會收斂到真實值
• 由於網頁間鏈接的矩陣非常稀疏，佩奇和布林利用稀疏矩陣計算技巧大大簡化了計算
• 2003 年，Google 工程師 Jeffrey Dean 和 Sanjay Ghemawat 發明了 MapReduce，實現 PageRank 的完全自動化並行計算

2. 延伸閱讀：PageRank 的計算方法#

• 假設向量 $B = (b_1, b_2, \ldots, b_N)^T$ 為 N 個網頁的排名，矩陣 $A$ 記錄網頁之間的鏈接數
• 迭代公式：$B_i = A \cdot B_{i-1}$，初始假設 $B_0 = (1/N, 1/N, \ldots, 1/N)$
• 可證明 $B_i$ 最終會收斂，一般約 10 次迭代即可
• 由於需要處理零概率或小概率事件，加入平滑處理，公式變為：

$$B_i = \left[\frac{\alpha}{N} \cdot I + (1-\alpha)A\right] \cdot B_{i-1}$$

• 其中 $\alpha$ 是一個較小的常數，$I$ 是單位矩陣
• 計算主要是矩陣相乘，容易分解為並行任務，在多台計算機上執行

本章小結#

PageRank 在學術界被公認為文獻檢索中最大的貢獻之一，佩奇也因此在 30 歲時當選美國工程院院士。雖然今天搜索引擎已比最初複雜許多，PageRank 的作用也在縮小，但它奠定了 Google 成功的基礎，其受專利保護也為早期的 Google 提供了重要的競爭屏障。