PageRank：圖上的隨機遊走#

把整個網際網路畫成一張圖：每個網頁是一個節點，每條超連結是一條有向邊。當你想做一個搜尋引擎，問題就來了——使用者搜「演算法」，可能有上百萬個頁面都符合，該把誰排在第一個？

光看頁面內容（誰提到「演算法」最多次）很容易被作弊：塞滿關鍵字的垃圾頁面就能霸榜。PageRank 換了一個角度：不看頁面自己說自己多重要，而是看整個網路怎麼看待它。

問題：如何衡量網頁的重要性？#

直覺上，一個網頁被越多其他網頁連結，它應該越重要。但「數連結的數量」太粗糙了，於是 PageRank 把「重要性」定義成一個遞迴關係：

一個網頁的重要性 = 所有指向它的網頁之重要性總和。

注意這裡的關鍵字是「重要性總和」，不是「連結數量」。這帶出兩個精妙之處：

• 連結來源的權威度不等值：來自一個權威大站（例如維基百科首頁）的一條連結，遠勝過來自一堆無名小站的連結。權威頁面的「背書」更值錢。
• 重要性會稀釋：如果一個頁面同時連向 100 個頁面，它分給每個頁面的「票」就只有 $\frac{1}{100}$；如果它只連向 1 個頁面，那一票就是滿滿的權重。

把這個規則寫成式子：設頁面 $u$ 連出的總數為 $L(u)$，頁面 $p$ 的重要性 $PR(p)$ 為

$$ PR(p) = \sum_{u \to p} \frac{PR(u)}{L(u)} $$

意思是：每個指向 $p$ 的頁面 $u$，把自己的重要性平均分給它連出的所有頁面，$p$ 收到其中一份。

先有雞還是先有蛋：迭代解法#

上面的式子有個尷尬：要算 $A$ 的重要性，得先知道指向它的 $B$ 的重要性；但要算 $B$，又得先知道指向 $B$ 的別人的重要性…… 一路追下去會繞回 $A$ 自己。這是典型的循環依賴——沒有任何一個頁面的分數可以「最先」算出來。

解法不是去解開這個循環，而是用迭代逼近它：

1. 初始化：所有頁面給相同的分數（例如都是 $\frac{1}{N}$，$N$ 是頁面總數）。
2. 傳遞：套用上面的規則，讓每個頁面把分數沿連結傳給它指向的頁面，算出一輪新的分數。
3. 重複：拿新分數再傳一輪、再傳一輪……

神奇的是，這個過程在數學上保證會收斂到一組穩定的分數——不管初始值怎麼設，反覆套用規則後，分數會趨於不再變動。實務上通常只要十幾次迭代就足夠精確。

如果把所有頁面的分數寫成一個向量 $B$，把「重要性沿連結傳遞」的規則寫成一個轉移矩陣 $M$，那一輪迭代就是一次矩陣乘法：

$$ B_i = M \cdot B_{i-1} $$

整個 PageRank 計算，本質上就是讓初始向量反覆乘上同一個矩陣，直到它穩定下來。

循環依賴在很多領域看起來無解，但只要這個系統有「收斂」的數學性質，迭代逼近往往比硬解析更簡單、更實用。先給個粗略起點，再讓規則一輪輪自我修正——這是處理自我參照問題的通用招式。

// graph[u] = u 指向的所有頁面；n = 頁面總數
fun pageRank(graph: Array<List<Int>>, iterations: Int = 20): DoubleArray {
    val n = graph.size
    var rank = DoubleArray(n) { 1.0 / n }  // 初始：均分

    repeat(iterations) {
        val next = DoubleArray(n)  // 全部歸零，準備接收這一輪傳入的分數
        for (u in 0 until n) {
            val outLinks = graph[u]
            if (outLinks.isEmpty()) continue  // 死胡同：此處簡化略過
            val share = rank[u] / outLinks.size  // 稀釋：平均分給每個外連結
            for (v in outLinks) {
                next[v] += share
            }
        }
        rank = next
    }

    return rank
}

兩個等價視角#

PageRank 真正高明的地方，是同一件事可以從兩個完全不同的角度理解，而兩者在數學上等價。

視角一：隨機遊走（random walk）#

想像一個隨機瀏覽者：他站在某個頁面上，每一步都隨機點擊當前頁面上的一條外連結，走到下一個頁面，然後再隨機點下一條……如此無止境地在網路上亂逛。

問一個問題：長期下來，這個瀏覽者停留在每個頁面的機率是多少？

答案就是該頁面的 PageRank。重要的頁面（被很多重要頁面指向的）會被瀏覽者更頻繁地經過，停留機率自然更高。

這在數學上是一個馬可夫鏈（Markov chain）：下一步只取決於當前所在的頁面。PageRank 向量，正是這條馬可夫鏈的穩態分佈（stationary distribution）——當系統跑到不再變化時，各狀態的機率分佈。

flowchart LR
    A((A)) --> B((B))
    A --> C((C))
    B --> C
    C --> A
    B --> A
    style C fill:#e8f5e9

被指向最多、且來源也重要的 C，長期停留機率最高。

視角二：矩陣的主特徵向量#

回到 $B = M \cdot B$ 這個式子。當迭代收斂、向量不再變動時，新向量等於舊向量，於是穩定的 PageRank 向量 $B$ 滿足

$$ M \cdot B = B $$

這正是特徵向量（eigenvector）的定義式（特徵值為 1）。換句話說，PageRank 向量就是網頁轉移矩陣 $M$ 的主特徵向量（principal eigenvector）。而前面那個「反覆乘矩陣直到穩定」的迭代，數學上就叫冪迭代法（power iteration）——求主特徵向量最直接的數值方法。

兩個視角描述的是同一個數值，只是穿著不同的數學外衣。這種「一個概念、多種等價詮釋」，往往是一個想法真正深刻的標誌。

阻尼係數（damping factor）#

純粹的隨機遊走有兩個會卡死的麻煩：

• 死胡同（dangling node）：某些頁面沒有任何外連結，瀏覽者走到這裡就無路可走，整個遊走停擺。
• 孤島 / 陷阱：幾個頁面互相連結、卻不連向外界，瀏覽者一旦走進去就再也出不來，所有機率都困在這個小圈圈裡。

這兩種情況都會破壞收斂，讓穩態分佈失真。PageRank 的修補辦法非常聰明：讓瀏覽者偶爾不點連結，直接「瞬移」到全網路任一個隨機頁面。

具體做法是：每一步，瀏覽者有大約 85% 的機率照常點擊外連結，另有大約 15% 的機率（這就是阻尼係數，damping factor，通常記為 $d \approx 0.85$，跳轉機率即 $1 - d$）放棄當前頁面、隨機跳到任一頁面重新開始。加入這個平滑項後，公式變成：

$$ PR(p) = \frac{1 - d}{N} + d \sum_{u \to p} \frac{PR(u)}{L(u)} $$

這個「隨機跳轉」項一舉解決所有問題：

• 死胡同不再致命——瀏覽者卡住時會直接跳走。
• 孤島不再是陷阱——總有 15% 機率跳出來。
• 數學上，它讓轉移矩陣變得「處處可達」，保證穩態分佈存在且唯一，迭代必然收斂。

阻尼係數常被理解成「模擬使用者厭倦了、直接打開新網址」。它既符合真實上網行為的直覺，又恰好補上了純隨機遊走的數學漏洞——一個工程上的小技巧，同時兼顧了真實感與嚴謹性。

圖的真實應用#

PageRank 是「把圖論用在真實世界」的經典範例，它和本章其他內容環環相扣：

• 要算 PageRank，得先有圖——而這張網頁圖是怎麼來的？靠爬蟲（crawler）順著超連結一頁頁地走訪。這正是 BFS 與 DFS 的遍歷在做的事：從種子頁面出發，沿著邊不斷探索新節點，把整張圖的結構抓回來。
• 抓回來之後，網頁、連結、入度出度這些概念，都是 圖的基礎 裡的有向圖術語。PageRank 不過是在這張有向圖上定義了一個「重要性」的數值。

PageRank 的高明，在於它把整個網路當成一個整體來看，而非孤立地看每個頁面。一個頁面的分數，取決於指向它的頁面，而那些頁面的分數又取決於更上游……最終是整張圖的全局結構共同決定了每個節點的排名。這種「全局視角」正是圖論的威力所在——很多問題，唯有把節點放回它所處的整張網路裡，才看得清楚。

小結#

PageRank 把一個看似主觀的問題（「哪個網頁比較重要」）轉化成一個有唯一解、可計算、能收斂的圖論問題。它最深的啟發或許是：當你不知道怎麼替一群互相影響的事物排名時，先寫下它們之間的遞迴關係，剩下的交給迭代與收斂。