在群山環抱的「Page 國」,有七千戶人家。
國中有個古老習俗:每戶門前懸一口「水罐燈」。水罐里的水位,就是那戶人家的風望。客人路過遠處,不必進門,看一眼一列水罐燈的高低,就知道該往哪兒投宿、該信誰家的話。
水從哪兒來?不是天上落的,是沿著一條條「敬意之河」流來的。每戶門楣上都掛一塊「信榜」,記下這戶最敬重哪幾家鄰居。每天拂曉鐘響,全國同時行一次「注水禮」:各家把自己罐裡的水,平均分給信榜上的每一戶,傾注過去;然後各家門前的罐子,又因為別人的傾注而重新漲起來。
年輕的水官小林,奉國王密旨:「找出全國最有風望的七戶,在他們門前點起長明烽火,好讓迷路的旅人認路。」
小林用了最樸素的辦法:天天記錄水位。第一天,水位全動了;第二天,又動了;十個清晨過去,水位還在動——只是動得越來越慢。他在心裡算:要等水位「真正不再動」,恐怕要等上一百年。
更糟的是,國境兩處怪地方。
第一處叫「回音谷」。谷裡的人世代只信谷內的幾戶東家西家:東家把水注給西家,西家再注回東家。外人的水進不來,谷裡的水也出不去。於是谷裡的燈一天比一天亮,全國其餘地方的燈一天比一天暗——水被鎖死在谷裡了。
第二處叫「枯井村」。那裡的人性子孤絕,信榜上一個名字也不寫,只守一條家規:「我不欠誰,水全倒進井裡。」日復一日,枯井村的燈先暗了,全國的水又一點一點漏進井裡,再也回不來。
小林差點放棄。這時,從山上走下來一位老水官,名叫佩倫(Perron)。他沒有教他怎麼算,只教他在注水禮裡加兩條規矩:
「第一條:每戶每天拂曉,先把罐中水的一成五撥進國中的『大池』;而分注之前,各家先從大池裡領取一份均額的水。
「第二條:枯井村那種不欠誰的人家,他們的水不再入井,一律直接撥進大池。」
第一條一立,大池的水不再死水一潭:它變成國王回贈全國的一場「敬意之雨」——不論住在回音谷還是枯井村,每天拂曉都有一份均勻落下的雨。谷裡的人越是互注,水越高,被全境的雨稀釋得越多;枯井村漏掉的水,也隨雨回到了循環裡。
第二條一立,水再也不會漏進死井。
小林重開帳簿。這一次他看見:無論從哪一村開始記、無論起先寫下什麼水位,約莫一百個清晨之後,七千戶的燈全都沉入同一個「止水之勢」——一個不再動一毫分毫的分佈,就算鐘再響一千年,也不再變。而且這個勢是唯一的:他試過全境水位相同的開頭,試過把所有水都先澆給一村人的開頭,最終沉下去的止水,都是同一個。
「可見,」老佩倫說,「這止水不屬於『你的帳本』,只屬於敬意之河的結構本身。它才是這國的真實風望。」
國王依止水之勢,在水位最高的七戶點起烽火。迷路的旅人照著烽火走,總能找到值得信賴的人家。
後人把這套法門刻在大池旁的石碑上,稱之為「Page 之序」。碑文只有一句:
「水無出,則淤為死潭;水無源,則涸為枯井。每次注水,混入一滴全境的雨,則全國之燈,永歸一水。」
寓言講完,該說說真話了
這七千戶,就是網頁(或圖的節點);信榜是出鏈;水罐燈的水位,就是那一頁的重要度分數。國王密旨要解決的問題,正是一個經典的譜理論問題:给定全圖的出鏈結構,如何給每個節點算一個 PageRank。
這則寓言在講什麼:Perron–Frobenius 與功率迭代
把「鄰里注水」寫成數學:令 $M$ 為列隨機矩陣(每列加總為 1——「一戶的水平均分給它敬重的人家」),那麼每天一次的注水,就是
$$R_{k+1} = M R_k$$
從任意外向初始水位 $R_0$ 出發迭代,就是在找 $M$ 特徵值為 1 的特徵向量——這叫功率法(power iteration),而它收斂的理論靠山是 Perron–Frobenius 定理:正矩陣(或不可約非負矩陣)存在唯一的正特徵向量,且功率迭代收斂到它。
寓言裡那兩處怪地方,正是定理條件失守的兩個經典病態:
- 回音谷=閉合的互通類(closed communicating class):節點群體只互相指認,質量被鎖死,功率迭代不再收斂到全圖的唯一致點。
- 枯井村=懸垂節點(dangling node):沒有出鏈,質量直接漏掉,$R^T \mathbf{1} = 1$ 的 $\ell_1$ 守恆被破壞。
老佩倫的兩條規矩,正是 Google PageRank 的衰減係數 $d$(通常 $0.85$):
$$R = d, M R + (1-d), v$$
- 大池與雨:節點以機率 $1-d$ 不再順著出鏈走,而是「傳送」到任意一頁;$v$ 是均勻傳送向量,每頁分得 $\frac{1-d}{N}$。這就是故事裡「一成五撥進大池、再均勻落雨」。
- 枯井村改撥大池:dangling node 的質量也進 $v$,總質量得以守恆。
衰減之後,$P = dM + (1-d),v\mathbf{1}^T$ 變成嚴格正矩陣,Perron–Frobenius 定理完整適用:特徵值 1 的特徵向量唯一且全正、是全局吸引子、任何開頭都收斂到同一止水。收斂速度由次大特徵值決定:誤差大致按 $(d\lambda_2(M))^k$ 衰減;在 $\ell_1$ 範數下,收縮係數恰為 $d<1$,這也解釋了故事裡「約百個清晨」——實際實現裡幾十次迭代就夠用,而且每步只是一次稀疏矩陣向量乘,計算量遠小於全對全比較。
一句話直白的版本:PageRank 就是隨機瀏覽者(random surfer)的位置分佈——他以機率 $d$ 沿著出鏈亂走,以機率 $1-d$ 隨機「傳送」到任意一頁;PageRank 向量正是這個馬可夫鏈的穩態。
寓言隱喻對照表
| 故事元素 | 對應概念 |
|---|---|
| Page 國、七千戶 | 網頁 / 圖的 $N$ 個節點 |
| 水罐燈、水位高低 | 節點的重要度分數 / PageRank 值 |
| 信榜(敬重誰) | 出鏈(out-links) |
| 每天拂曉同時分注 | $R_{k+1} = M R_k$,功率法一步迭代 |
| 水位動得越來越慢、終歸止水 | 迭代收斂到特徵向量 |
| 回音谷(只注谷內) | 閉合互通類,質量被鎖死、不可約性破壞 |
| 枯井村(無榜、水入井) | dangling node(無出鏈節點),質量漏失 |
| 大池 | 傳送池 / 吸收態(teleport pool) |
| 「一成五撥入大池、雨均撒全境」 | 衰減係數 $d=0.85$、均勻傳送向量 $v$,$1-d=0.15$ |
| 枯井村改撥大池 | dangling 質量併入 $v$,保持 $\ell_1$ 守恆 |
| 無論從哪開頭都沉入同一止水 | Perron–Frobenius 特徵向量唯一 + 全局收斂 |
| 水位最高七戶點烽火 | 依 PageRank 排序取 top-$k$ |
| 老佩倫(老水官) | Oskar Perron(Perron–Frobenius 定理) |
一句話總結:敬意順著出鏈流,會淤成死潭、漏進死井;混入一成五的「全境之雨」,全燈便歸唯一止水——那是 Perron–Frobenius 的承諾,也是 PageRank 的秘密。