algo-seo-pagerank

asgard-ai-platform ｜ 行銷與 SEO ｜ 原文 ｜ MIT

用隨機瀏覽者模型計算網頁的 PageRank 重要性

---
name: "algo-seo-pagerank"
description: "實作 PageRank 演算法，用隨機瀏覽者模型計算網頁的重要性分數。當使用者需要依連結權威度替頁面排名、建立簡化的搜尋排名系統、或了解連結結構如何決定頁面重要性時使用，即使他們說的是「哪些頁面最重要」、「連結分析」或「頁面權威分數」也一樣。"
metadata:
  category: "WP-35 SEO 演算法"
  tags: ["seo", "pagerank", "graph-algorithm", "link-analysis"]
---

# PageRank 演算法

## 概述

PageRank 透過模擬一個隨機瀏覽者來計算網頁的重要性：他有機率 d（阻尼係數）順著連結走，有機率 1-d 跳到隨機的頁面。收斂複雜度 O(k * E)，k 是迭代次數，E 是邊的數量。

## 何時使用

**觸發條件：**
- 要從連結圖結構計算頁面重要性
- 要建立以連結為基礎的權威度評分系統
- 要分析引用網路，或任何有向圖的重要性

**何時不要用：**
- 只需要關鍵字相關性時（改用 TF-IDF）
- 圖是無向或無權重的（考慮中心性指標）

## 演算法

```
鐵律：PageRank 的收斂
- 阻尼係數 d「必須」< 1（通常是 0.85）
- 沒有阻尼的話，rank sink 和 spider trap 會破壞收斂
- 正確性不變量：所有 PageRank 值的總和 = 1.0
```

### 階段 1：輸入驗證
從連結資料建立鄰接表。驗證：不計入自我迴圈、所有節點都有交代（包含沒有外連的懸空節點）。
**關卡：** 圖的結構良好、懸空節點已辨識。

### 階段 2：核心演算法
1. 把所有 N 個頁面初始化為 PR = 1/N
2. 每次迭代：
   - 對每個頁面 p：PR(p) = (1-d)/N + d * Σ(PR(q)/L(q))，q 涵蓋所有連到 p 的頁面
   - 把懸空節點的 rank 平均分給所有頁面
3. 重複直到收斂（L1 範數的變化 < ε，通常 1e-6）

### 階段 3：驗證
檢查：所有 PR 值加總約為 1.0。把前 k 名的排名和已知的權威頁面比較。
**關卡：** |Σ PR - 1.0| < 0.001，且在最大迭代次數內達到收斂。

### 階段 4：輸出
回傳排序後的頁面分數，附上名次。

## 輸出格式

```json
{
  "rankings": [{"page": "url", "score": 0.042, "rank": 1}],
  "metadata": {"nodes": 1000, "edges": 5000, "iterations": 45, "damping": 0.85, "converged": true}
}
```

## 範例

### 輸入輸出範例
**輸入：** 頁面 A→B、A→C、B→C、C→A（3 個節點、4 條邊、d=0.85）
**預期輸出：** C: 0.390、A: 0.327、B: 0.283（近似值）

### 邊界情況
| 輸入 | 預期 | 原因 |
|-------|----------|-----|
| 單一節點、沒有連結 | PR = 1.0 | 唯一的節點拿走所有 rank |
| 所有節點都連到同一個 | 目標得到最高的 PR | 星狀拓撲會把 rank 集中 |
| 懸空節點（沒有外連） | 把它的 rank 平均分配 | 防止 rank 外洩 |

## 常見陷阱

- **懸空節點**：沒有外連的頁面會漏掉 rank。每次迭代都要把它們的 rank 平均重新分配給所有頁面。
- **Spider trap**：一群只互相連結的頁面會累積 rank。阻尼係數能防止這件事，但無法完全消除。
- **收斂速度**：稠密的圖收斂比較快。有長鏈的稀疏圖可能需要 100 次以上的迭代。
- **浮點數累積誤差**：大型的圖要用雙精度。單精度在 50 次以上的迭代後會明顯漂移。
- **個人化 PageRank**：標準 PageRank 用的是均勻的隨機跳躍。要做個人化推薦的話，把跳躍向量偏向種子頁面。

## 參考資料

- 收斂證明的數學推導，見 `references/convergence-proof.md`
- 高效的稀疏矩陣實作，見 `references/sparse-implementation.md`

---
name: "algo-seo-pagerank"
description: "Implement PageRank algorithm to compute web page importance scores using the random surfer model. Use this skill when the user needs to rank pages by link authority, build a simplified search ranking system, or understand how link structure determines page importance — even if they say 'which pages are most important', 'link analysis', or 'page authority score'."
metadata:
  category: "WP-35 SEO 演算法"
  tags: ["seo", "pagerank", "graph-algorithm", "link-analysis"]
---

# PageRank Algorithm

## Overview

PageRank computes the importance of web pages by modeling a random surfer who follows links with probability d (damping factor) and jumps to a random page with probability 1-d. Converges in O(k * E) where k is iterations and E is number of edges.

## When to Use

**Trigger conditions:**
- Computing page importance from link graph structure
- Building link-based authority scoring systems
- Analyzing citation networks or any directed graph importance

**When NOT to use:**
- When you only need keyword relevance (use TF-IDF instead)
- When the graph is undirected or unweighted (consider centrality measures)

## Algorithm

```
IRON LAW: PageRank Convergence
- Damping factor d MUST be < 1 (typically 0.85)
- Without damping, rank sinks and spider traps break convergence
- Correctness invariant: sum of all PageRank values = 1.0
```

### Phase 1: Input Validation
Build adjacency list from link data. Verify: no self-loops counted, all nodes accounted for (including dangling nodes with no outlinks).
**Gate:** Graph is well-formed, dangling nodes identified.

### Phase 2: Core Algorithm
1. Initialize all N pages with PR = 1/N
2. For each iteration:
   - For each page p: PR(p) = (1-d)/N + d * Σ(PR(q)/L(q)) for all q linking to p
   - Distribute dangling node rank equally to all pages
3. Repeat until convergence (L1 norm change < ε, typically 1e-6)

### Phase 3: Verification
Check: all PR values sum to ~1.0. Compare top-k rankings against known authority pages.
**Gate:** |Σ PR - 1.0| < 0.001 and convergence achieved within max iterations.

### Phase 4: Output
Return sorted page scores with rank position.

## Output Format

```json
{
  "rankings": [{"page": "url", "score": 0.042, "rank": 1}],
  "metadata": {"nodes": 1000, "edges": 5000, "iterations": 45, "damping": 0.85, "converged": true}
}
```

## Examples

### Sample I/O
**Input:** Pages A→B, A→C, B→C, C→A (3 nodes, 4 edges, d=0.85)
**Expected Output:** C: 0.390, A: 0.327, B: 0.283 (approximate)

### Edge Cases
| Input | Expected | Why |
|-------|----------|-----|
| Single node, no links | PR = 1.0 | Only node gets all rank |
| All nodes link to one | Target gets highest PR | Star topology concentrates rank |
| Dangling node (no outlinks) | Distribute its rank equally | Prevents rank leakage |

## Gotchas

- **Dangling nodes**: Pages with no outgoing links leak rank. Redistribute their rank equally across all pages each iteration.
- **Spider traps**: A group of pages that only link to each other accumulate rank. Damping factor prevents this but doesn't eliminate it entirely.
- **Convergence speed**: Dense graphs converge faster. Sparse graphs with long chains may need 100+ iterations.
- **Floating point accumulation**: For large graphs, use double precision. Single precision drifts noticeably after 50+ iterations.
- **Personalized PageRank**: Standard PageRank uses uniform random jump. For personalized recommendations, bias the jump vector toward seed pages.

## References

- For mathematical derivation of convergence proof, see `references/convergence-proof.md`
- For efficient sparse matrix implementation, see `references/sparse-implementation.md`