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

{
  "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

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