PageRank Algorithm Deep-Dive

The Wikifita Atlas uses a standard iterative PageRank algorithm to assign importance scores to every page in the wiki corpus. These scores determine search result ranking, homepage suggestions, and the visual size of nodes in the interactive graph. The implementation lives in lib/wiki.ts, function computePagerank (lines 419-445).

This page documents the exact algorithm, its mathematical foundation, convergence properties, and all downstream consumers.

Mathematical Foundation

PageRank models a "random surfer" who, at each step, either follows a link from the current page (with probability $d$ ) or teleports to a random page (with probability $1 - d$ ). The stationary distribution of this Markov chain is the PageRank vector.

Standard Formula

For a corpus of $N$ pages, the PageRank $r(i)$ of page $i$ is computed iteratively:

r(i)^{(t+1)} = \frac{1 - d}{N} + d \cdot \left( \sum_{j \in \text{inlinks}(i)} \frac{r(j)^{(t)}}{\text{outdegree}(j)} + \frac{\text{danglingMass}^{(t)}}{N} \right)

Where:

$d = 0.85$ is the damping factor
$\text{inlinks}(i)$ is the set of pages that link to page $i$
$\text{outdegree}(j)$ is the number of outgoing links from page $j$
$\text{danglingMass}^{(t)} = \sum_{j : \text{outdegree}(j) = 0} r(j)^{(t)}$ is the total rank of all dangling nodes

The formula has two additive components:

Teleport term: $\frac{1 - d}{N}$ -- ensures every page receives a minimum rank regardless of inlinks
Link term: $d \cdot \sum \frac{r(j)}{\text{outdegree}(j)}$ -- rank inherited from incoming links, scaled by the damping factor

Parameters

Parameter	Value	Description
`damping`	`0.85`	Probability the random surfer follows a link. Standard value from Brin & Page (1998).
`tolerance`	`1e-10`	L1 convergence threshold. Iteration stops when $\sum_i
`maxIterations`	`200`	Hard cap. If convergence is not reached within 200 iterations, the algorithm stops.

The choice of $d = 0.85$ is the canonical value from the original PageRank paper. Higher values (closer to 1.0) increase the influence of the link structure; lower values increase the teleport probability, making ranks more uniform.

The tolerance of $1e-10$ is extremely tight. In practice, the Wikifita corpus (typically 50-200 pages) converges in 30-60 iterations, well before the 200-iteration cap.

Algorithm in Detail

Pseudocode

function computePagerank(paths, outlinksByPath, damping=0.85, tolerance=1e-10, maxIterations=200):
    N = length(paths)

    // Step 1: Initialize all ranks uniformly
    rank = new Map()
    for each page in paths:
        rank[page] = 1 / N

    // Step 2: Iterate until convergence
    for iteration = 1 to maxIterations:
        // 2a: Compute dangling mass
        danglingMass = 0
        for each page in paths:
            if outlinksByPath[page].length == 0:
                danglingMass += rank[page]

        // 2b: Compute base contribution (teleport + dangling redistribution)
        base = (1 - damping) / N + damping * danglingMass / N

        // 2c: Initialize next ranks with base
        next = new Map()
        for each page in paths:
            next[page] = base

        // 2d: Distribute rank from pages with outlinks
        for each page in paths:
            if outlinksByPath[page].length > 0:
                share = damping * rank[page] / outlinksByPath[page].length
                for each target in outlinksByPath[page]:
                    next[target] += share

        // 2e: Compute convergence delta (L1 norm)
        delta = 0
        for each page in paths:
            delta += |next[page] - rank[page]|

        rank = next

        if delta < tolerance:
            break  // Converged

    // Step 3: Normalize so all ranks sum to exactly 1.0
    total = sum of all rank values
    for each page in paths:
        rank[page] /= total

    return rank

Step-by-Step Walkthrough

Step 1 -- Initialization: Every page starts with equal rank $\frac{1}{N}$ . This is a uniform prior with no bias toward any page.

Step 2a -- Dangling mass: Pages with zero outlinks (leaf nodes, stub pages, or pages whose links all resolved to external URLs) accumulate rank that would otherwise be lost. The algorithm captures this mass.

Step 2b -- Base contribution: Every page receives a guaranteed minimum rank from two sources:

The teleport probability: $\frac{1 - d}{N} = \frac{0.15}{N}$
The dangling redistribution: $d \cdot \frac{\text{danglingMass}}{N}$

This ensures no page has zero rank, and dangling nodes do not act as rank sinks.

Step 2c-2d -- Rank propagation: Each page with outgoing links distributes its rank equally among its link targets, scaled by $d$ . A page with rank $r$ and $k$ outlinks sends $\frac{d \cdot r}{k}$ to each target.

Step 2e -- Convergence check: The L1 norm $\sum |r^{(t+1)} - r^{(t)}|$ measures how much the rank vector changed. When this falls below $10^{-10}$ , the distribution is stable.

Step 3 -- Normalization: After iteration, all ranks are divided by their sum to ensure $\sum r(i) = 1.0$ exactly. This corrects any floating-point drift accumulated over iterations.

Dangling Node Handling

Dangling nodes -- pages with no outgoing links -- are a critical edge case. Without special treatment, they act as rank sinks, absorbing rank from the network without redistributing it.

The Wikifita Approach

The algorithm redistributes dangling node mass uniformly across all pages, combined with the teleport term:

\text{base} = \frac{1 - d}{N} + d \cdot \frac{\text{danglingMass}}{N}

This means a dangling page's rank is not lost -- it flows back into the system equally. A dangling page B that is linked from a high-rank page A will still accumulate significant rank through the incoming link, but it will also leak rank back through the dangling redistribution.

Practical Effect

In the Wikifita corpus, dangling nodes include:

Pages with only external links (all links resolve to state: "external")
Stub pages with no body content
Pages whose internal links all failed resolution (state: "missing")

The test suite explicitly verifies that a dangling page B (linked from A, no outlinks) receives higher rank than A (the linker). This is because B accumulates rank from A, while A distributes its rank among its outlinks (including B).

Convergence Properties

Typical Convergence

For the Wikifita corpus (50-200 pages), the algorithm typically converges within 30-60 iterations:

Corpus Size	Typical Iterations	Final Delta
~50 pages	25-35	~10^{-12}
~100 pages	35-50	~10^{-11}
~200 pages	45-65	~10^{-11}

Theoretical Bounds

The PageRank iteration is a contraction mapping with Lipschitz constant $d = 0.85$ . After $k$ iterations, the error is bounded by $d^k$ times the initial error. For the tolerance of $10^{-10}$ :

0.85^k < 10^{-10} \implies k > \frac{-10}{\log_{10}(0.85)} \approx 143

In practice, convergence is faster because the spectral gap of the link matrix is typically much larger than $1 - d$ .

Test Verification

The test suite checks two invariants:

Sum invariant: $\sum r(i) = 1.0$ within tolerance $10^{-9}$
Dangling rank invariant: A dangling page B (linked from page A, no outlinks) has $r(B) > r(A)$

How PageRank Is Used

PageRank scores are consumed by four subsystems in the Wikifita Atlas.

1. Search Scoring

In the search system, PageRank provides a boost to the BM25 text-relevance score:

\text{pagerankBoost} = \frac{r(i)}{r_{\max}} \times 1.25

Where $r_{\max} = \max_j r(j)$ is the highest PageRank in the corpus. This normalization means the top-ranked page gets a boost of exactly 1.25, and all other pages get proportionally less.

The boost is added to the final score:

\text{finalScore} = \text{bm25} \times 1.8 + \text{titleBoost} + \text{pagerankBoost} + \text{proximityBoost}

See wikifita-site-search-system for the complete scoring formula.

2. Top Suggestions

The home page and sidebar display the top 3 pages by PageRank. The topSuggestedPages function sorts pages by:

PageRank descending (primary)
Title alphabetically ascending (tiebreaker)

This surfaces the most "important" pages in the wiki -- those that are most referenced and link to other important pages.

3. Graph Visualization

In the D3 force-directed graph, node radius is computed as:

\text{radius}(i) = 5 + \sqrt{\frac{r(i)}{r_{\max}}} \times 18

Normalized Rank	Radius (px)	Visual
1.0 (highest)	23	Largest circle
0.5	17.7	Medium-large
0.1	10.7	Small
0.01 (lowest)	6.3	Near-minimum

The square root scaling prevents the highest-rank node from dominating the visualization while still providing clear visual differentiation. The minimum radius of 5px ensures all nodes are clickable.

4. Search Result Tiebreaking

When two search results have identical composite scores, PageRank serves as the first tiebreaker:

Sort by: score DESC, pagerank DESC, path ASC

This means the more "important" page wins ties, ensuring well-connected pages surface above isolated ones.

Integration with the Corpus Pipeline

PageRank is computed as Phase 7 of the corpus building pipeline wikifita-site-corpus-pipeline, after all links have been extracted and resolved (Phase 5). The computation requires:

paths: A list of all page paths in the corpus
outlinksByPath: A map from each page path to its list of resolved outgoing link destinations (excluding self-links)

The output is a Map<string, number> mapping each page path to its normalized PageRank score. This map is then stored on each WikiPage object as the pagerank field.

flowchart LR
    A[Phase 5: Link Resolution] -->|outlinksByPath| B[Phase 7: PageRank]
    B -->|pagerank Map| C[WikiPage.pagerank]
    C --> D[Search Scoring]
    C --> E[Top Suggestions]
    C --> F[Graph Node Radius]
    C --> G[Client Data]

Mathematical Properties

Stochastic Matrix

The PageRank iteration implicitly constructs a column-stochastic matrix $M$ where:

M_{ij} = \begin{cases} \frac{1}{\text{outdegree}(j)} & \text{if page } j \text{ links to page } i \\ \frac{1}{N} & \text{if page } j \text{ is a dangling node} \end{cases}

The full transition matrix with damping is:

G = d \cdot M + \frac{1 - d}{N} \cdot \mathbf{1}\mathbf{1}^T

$G$ is irreducible (the teleport term ensures a fully connected graph) and aperiodic (the teleport term introduces self-loops), guaranteeing a unique stationary distribution.

Uniqueness

Because $G$ is a primitive stochastic matrix (irreducible and aperiodic), the Perron-Frobenius theorem guarantees:

A unique stationary distribution $\pi$ exists
$\pi$ is the dominant eigenvector of $G$ with eigenvalue 1
The iteration converges to $\pi$ regardless of the initial distribution

The uniform initialization ( $r(i)^{(0)} = 1/N$ ) is one valid starting point. Any initial distribution would converge to the same result.

Sensitivity to Link Structure

The final PageRank vector is highly sensitive to the link topology:

Hub pages (pages with many outgoing links) distribute their rank widely but receive less concentrated rank
Authority pages (pages with many incoming links from important pages) accumulate high rank
Isolated clusters (pages that only link within their group) form local rank peaks
Bridge pages (pages linking across clusters) act as rank conduits

In the Wikifita corpus, directive pages (e.g., preferencias-tecnicas.md) tend to have high PageRank because they are referenced from many project and research pages. Memory index pages also rank highly due to their central position in the link graph.

Edge Cases

Empty Corpus

If the corpus contains zero pages, computePagerank returns an empty map. No normalization is attempted.

Single Page

A single-page corpus has PageRank $r = 1.0$ (after normalization). The page has no outlinks (dangling), so all mass is redistributed to itself.

Fully Disconnected Graph

If no page links to any other page, all pages are dangling. After normalization, every page receives rank $\frac{1}{N}$ . The damping factor and teleport term ensure uniform distribution.

Self-Links

Self-links are filtered during graph construction (Phase 5). A page cannot boost its own PageRank by linking to itself. This filtering happens before computePagerank is called, so the algorithm never sees self-loops.

Comparison with Standard PageRank

Aspect	Standard PageRank	Wikifita Implementation
Damping factor	0.85	0.85 (identical)
Dangling handling	Redistribute uniformly	Redistribute uniformly (identical)
Convergence	Varies	L1 < 1e-10, max 200 iterations
Normalization	Implicit (stochastic matrix)	Explicit post-normalization to sum=1
Self-links	Not typically filtered	Filtered during graph construction
Matrix representation	Explicit sparse matrix	Iterative (no matrix construction)

The implementation avoids constructing an explicit adjacency matrix, instead iterating directly over the outlinks map. This is more memory-efficient for sparse graphs (which wikis typically are).

wikifita-site-search-system -- BM25 scoring with PageRank boost integration
wikifita-site-graph-construction -- How the link graph (nodes and edges) is built
wikifita-site-corpus-pipeline -- The 7-phase pipeline where PageRank is computed
wikifita-site-architecture -- Full technical architecture
wikifita-site-rendering-pipeline -- HTML rendering of the wiki pages