8.3 PageRank與網頁搜尋#

概念說明#

TF-IDF 衡量「這份文件與查詢多相關」，但網路上有億萬份相關文件，哪個更重要？1998 年，Larry Page 與 Sergey Brin 提出 PageRank：一個網頁的重要性，由「連向它的網頁的重要性」決定——重要網頁投出的票更值錢。這把整個網頁連結圖變成一個遞迴定義的聲譽系統，也是 Google 起家的核心專利思想。

隨機遊走模型給了它漂亮的機率解釋：想像一個讀者在網頁圖上隨機漫遊——沿出邊等機率跳轉，偶爾（機率 1−d，d 稱為阻尼係數，常取 0.85）傳送到任一隨機頁面。長期而言，讀者停留在各頁面的穩定機率分布就是 PageRank 值。數學上這是馬可夫鏈的平穩分布，求解方法有二：解線性方程組，或冪迭代（power iteration）——反覆用轉移矩陣乘向量直到收斂。後者因可稀疏計算而成為實務標準。

形式化：設圖鄰接矩陣 M（列 = 目標頁、行 = 源頁，各行按出度正規化），PageRank 向量 r 滿足

r = d·M·r + (1−d)/N·𝟙

迭代的直觀意義：每輪，每個頁面把自己的分數均分給出邊（投票）；分數也會沿懸空節點（無出邊的頁面）流失，故補上傳送項 (1−d)/N 保證總分守恆為 1，且矩陣為正 → 收斂到唯一平穩分布（Perron-Frobenius 定理保證）。

應用遠超網頁：學術引用（PageRank 式引用權重）、社交網路影響力、推薦系統（item-item 圖）、蛋白質交互網路、交通流量。變體 Personalized PageRank（傳送偏向特定節點）是「找相似使用者/相似頁」的基礎，也是圖神經網路之前的經典圖演算法。

在搜尋引擎中的角色：PageRank 是查詢無關的預計算訊號（快取在索引裡），查詢時與 TF-IDF/BM25 等查詢相關訊號合成最終排名——「相關性」與「重要性」正交互補。現代 Google 已有數百個排名訊號（連結品質、使用者行為、BERT 語義理解），PageRank 仍是其中經典的一項。

演算法步驟（冪迭代）#

收集連結圖，建出邊表；處理懸空節點（無出邊）：視為連向所有頁面（或用隨機傳送項吸收）。
初始化 r⁰ = 1/N。
每輪：r^{t+1}[v] = (1−d)/N + d · Σ_{u→v} r^t[u]/outdeg(u)；懸空節點的分數均攤到全體。
檢查收斂：‖r^{t+1} − r^t‖₁ < ε（如 1e−8）即停止；否則繼續（實務 20–50 輪收斂）。
正規化（總和為 1），依值排序即為重要性排名。

Python 程式碼範例#

import numpy as np

links = {  # 玩具網頁圖：頁 -> 出邊
    "首頁":   ["演算法", "資料結構"],
    "演算法": ["首頁", "搜尋引擎", "排序"],
    "資料結構": ["首頁", "排序"],
    "排序":   ["演算法"],
    "搜尋引擎": ["演算法", "首頁"],
}
pages = list(links)
N = len(pages)
idx = {p: i for i, p in enumerate(pages)}
d = 0.85

def pagerank(links, d=0.85, eps=1e-9, max_iter=100):
    N = len(links)
    out = {p: len(links[p]) for p in links}
    dangling = [p for p in links if out[p] == 0]
    r = np.full(N, 1 / N)
    for it in range(max_iter):
        nxt = np.full(N, (1 - d) / N)
        for p in links:
            if out[p]:
                share = d * r[idx[p]] / out[p]
                for q in links[p]:
                    nxt[idx[q]] += share
        total_dangling = sum(r[idx[p]] for p in dangling)
        nxt += d * total_dangling / N
        if np.abs(nxt - r).sum() < eps:
            r = nxt; break
        r = nxt
    return {p: round(r[idx[p]], 4) for p in pages}

pr = pagerank(links)
for p, v in sorted(pr.items(), key=lambda x: -x[1]):
    print(f"{p:8s} {v:.4f}")
assert abs(sum(pr.values()) - 1) < 1e-3   # 總分守恆
# 「演算法」被最多人指且票源強 => PageRank 最高

# 驗證收斂輪數
def iters(links, d=0.85):
    r = np.full(len(links), 1 / len(links)); out = {p: len(links[p]) for p in links}
    for t in range(1, 101):
        nxt = np.full(len(links), (1 - d) / len(links))
        for p in links:
            for q in links[p]:
                nxt[idx[q]] += d * r[idx[p]] / out[p]
        if np.abs(nxt - r).sum() < 1e-9: return t
        r = nxt
print("收斂輪數:", iters(links))

複雜度分析#

冪迭代：每輪 O(|邊數| + N)（稀疏遍歷），收斂輪數 O(log(N/ε)/log(1/d))——d=0.85 時每輪誤差乘 0.85，約 100 輪可達 1e−7；總計近線性於圖規模，這是它能跑在整個網頁圖上的原因。
矩陣法：稠密矩陣每輪 O(N²) 不可行；實務用稀疏矩陣或 MapReduce 分塊。
空間：O(|邊數|)＋分數向量 O(N)；真正的網頁圖要分塊流式處理。
與其他訊號合成的複雜度：PageRank 預計算、查詢時 O(1) 查表——重要性訊號的「離線貴、線上免費」正是搜尋引擎的設計美學。

練習#

把圖改成「鏈狀 A→B→C→D→A」與「星狀中心指向四葉」，分別算 PageRank，驗證「被重要頁面指一次」勝過「被無名頁面指多次」。
實作 Personalized PageRank：傳送項改為偏向特定節點（如只在「演算法」重啟），輸出與查詢詞語義相近頁面的局部重要性，解釋它如何服務「相似頁推薦」。
在 1 萬節點的隨機圖（networkx.gnp_random_graph）上，比較你的冪迭代與 networkx.pagerank 的結果與收斂輪數；再調整 d = 0.5、0.9、0.99，觀察收斂速度與分數集中度的變化並解釋原因。