PageRank

Project 6/10 of the beacon-search-engine ecosystem — Ranking and Relevance category. Repository: github.com/juanmmm21/pagerank-link-analysis

The algorithm that put Google on the map, implemented from scratch: iterative PageRank with a configurable teleportation (damping) factor, computing a stationary authority distribution over a crawled link graph via sparse matrix power iteration. No networkx, no graph-processing library: the transition matrix, the dangling-node mass redistribution, and the convergence criterion are all implemented here with scipy.sparse and numpy.

What problem it solves

BM25 tells you how well a document's text matches a query. It says nothing about whether the web itself considers that document important. Two pages can contain the exact same words with the exact same frequency, yet one is a central reference other pages link to constantly and the other is an obscure dead end nobody points at — that difference in structural authority is exactly what a purely lexical signal cannot see. PageRank answers this by modeling a "random surfer" who follows outbound links most of the time and occasionally jumps to a random page in the corpus (the teleportation, or damping, factor): the fraction of time the surfer spends on each page, at the process's stationary distribution, is that page's authority. This project computes exactly that distribution, from a real crawled link graph, using sparse linear algebra so it scales to corpora with far more pages than would fit in a dense adjacency matrix.

Role in beacon-search-engine

web-crawler-scheduler
        │ link_graph.jsonl (outbound link graph)
        │                          inverted-index-builder
        │                                  │ documents.jsonl (doc_id ↔ url)
        ▼                                  ▼
        ┌───────────────────────────────────┐
        │      pagerank-link-analysis        │   (this project)
        │      link graph → authority score  │
        └─────────────────┬───────────────────┘
                           │ doc_id → pagerank_score
                           ▼
                learning-to-rank-reranker
                           ▲
                           │ doc_id → BM25 score
                  bm25-ranking-engine
                           │
                           ▼
              (converges in beacon-search-console)

pagerank-link-analysis sits alongside bm25-ranking-engine as one of the two ranking signals learning-to-rank-reranker combines: where BM25 scores lexical relevance to a specific query, this project scores structural authority independent of any query, computed once per corpus (or recomputed whenever the link graph changes) rather than per search. It depends on the outbound link graph produced by web-crawler-scheduler and on the doc_id space assigned by inverted-index-builder, but never on document text — that is what lets it be recalculated on a fresh crawl without rebuilding the inverted index at all.

Goal and skills demonstrated

• PageRank derived directly from the random-surfer model, not copied from a graph library: the transition matrix, the (1 - d)/N teleportation term, and the dangling-node mass-redistribution term are each implemented and justified on their own, not hidden behind a single opaque .rank() call.
• Sparse matrix algebra at every step: the adjacency matrix is built and iterated as a scipy.sparse.csr_matrix; each power-iteration step is one sparse matrix-vector product, so the cost per iteration is proportional to the number of edges in the link graph, never to the square of the number of pages — the difference between an algorithm that scales to a real crawl and one that only works in a classroom example.
• Explicit, tested dangling-node handling: pages with no resolvable outbound links (either because they truly have none, or because every link they had points outside the indexed corpus) would silently leak probability mass out of the system on every iteration if left unhandled. Their mass is redistributed uniformly across all documents each iteration, and this is covered by a dedicated test asserting the rank vector still sums to 1.0.
• Deterministic, hand-verified correctness: the two canonical PageRank textbook examples — a star graph (one hub, several leaves, hub as the dangling node) and a cycle graph (uniform distribution is an exact fixed point for any damping factor) — are solved analytically in the test docstrings and asserted against the algorithm's output with math.isclose, never == (../CLAUDE.md, section 2.C).
• Independent, minimal re-implementation of a sibling repo's URL normalization, not an import of it: joining link_graph.jsonl (whose url field is the crawler's post-redirect URL) against documents.jsonl (whose url field is the crawler's pre-redirect URL) requires canonicalizing both sides the same way — implemented here from scratch, entirely independently of web-crawler-scheduler's own package, the same polyrepo integration contract bm25-ranking-engine applied to a binary format.

How it works

1. Resolving doc_ids (document_resolver.py): documents.jsonl from inverted-index-builder is loaded once into a url (normalized) → doc_id map. total_documents is max(doc_id) + 1 — the same convention bm25-ranking-engine relies on for a dense, gap-free doc_id space.
2. Normalizing URLs (url_normalizer.py): lowercases scheme and host, drops default ports, drops fragments, sorts query parameters, and strips trailing slashes — standard URL canonicalization, needed because link_graph.jsonl's url field is the post-redirect URL while documents.jsonl's url field is pre-redirect, and because outbound links as they appear in raw HTML carry trivial formatting variance that would otherwise fail to match an indexed page.
3. Building the graph (graph_builder.py): link_graph.jsonl is read lazily, line by line; each entry's URL and each of its (deduplicated) outlinks are resolved to a doc_id. Entries or links that don't resolve — external URLs, or pages crawled but never indexed — are dropped explicitly and counted in GraphBuildStats, never silently. The result is a total_documents x total_documents sparse adjacency matrix, sized to the full doc_id space so that documents absent from the link graph still get a baseline authority score.
4. Power iteration (pagerank.py): the adjacency matrix is row-normalized by out-degree into a transition matrix (dangling rows are left at zero and handled separately); starting from a uniform rank vector, each iteration computes d * (Mᵀ·rank + dangling_mass/N) + (1-d)/N as sparse matrix-vector arithmetic, and stops when the L1 distance between consecutive rank vectors drops below tolerance or max_iterations is reached — an explicit, bounded convergence criterion, never an unbounded loop.
5. Orchestration (pipeline.py): PageRankPipeline ties the resolver, the graph builder, and the algorithm together behind a single compute() method, and scores_io.py persists the result as its own on-disk format (manifest.json + pagerank_scores.jsonl + convergence.json), the same manifest-plus-JSONL convention inverted-index-builder and index-compression-codec use for their own index directories.

Architecture

src/pagerank_link_analysis/
├── models.py                 # DocumentRecord, PageRankParams, PageRankScore,
│                              # GraphBuildStats, ConvergenceInfo, PageRankRunResult
├── protocols.py                # DocumentIdResolver interface
├── url_normalizer.py            # independent URL canonicalization for cross-repo joins
├── document_resolver.py          # JsonlDocumentIdResolver: url -> doc_id, backed by documents.jsonl
├── link_graph_reader.py           # lazy line-by-line reader of link_graph.jsonl
├── graph_builder.py                # link_graph.jsonl + resolver -> sparse adjacency matrix
├── pagerank.py                      # power iteration: damping, dangling nodes, convergence
├── scores_io.py                      # on-disk output format (manifest + scores + convergence)
├── pipeline.py                        # PageRankPipeline: ties everything together
└── __main__.py                        # CLI (`compute`, `top`)

Requirements and installation

• Python >=3.11
• Runtime dependencies: numpy and scipy — scipy.sparse is what makes the power iteration viable on graphs with thousands of nodes instead of a dense matrix that would not fit in memory at real crawl scale (../CLAUDE.md, section 1 and AGENTS.md's Definition of Done).

git clone https://github.com/juanmmm21/pagerank-link-analysis.git
cd pagerank-link-analysis
python3 -m venv .venv && source .venv/bin/activate
pip install -e ".[dev]"

Usage (CLI)

# Compute PageRank from a crawler's link graph and an indexed corpus
pagerank-link-analysis compute ./documents.jsonl ./link_graph.jsonl ./output

# Tune the damping factor, convergence tolerance, and iteration cap
pagerank-link-analysis compute ./documents.jsonl ./link_graph.jsonl ./output \
  --damping-factor 0.85 --tolerance 1e-8 --max-iterations 200

# Inspect the highest-authority documents of an already-computed result
pagerank-link-analysis top ./output --documents ./documents.jsonl --top-k 10

Try it against the small, hand-built graph checked into samples/tiny_example/ (one hub linked by two leaves, plus one fully isolated page and one external link that intentionally doesn't resolve):

pagerank-link-analysis compute \
  samples/tiny_example/documents.jsonl samples/tiny_example/link_graph.jsonl /tmp/pagerank-example
pagerank-link-analysis top /tmp/pagerank-example --documents samples/tiny_example/documents.jsonl

It can also be invoked as a module: python -m pagerank_link_analysis compute ....

Data formats

Input — documents.jsonl, produced by inverted-index-builder: one JSON object per line, at minimum doc_id and url (see that project's README for the full schema). total_documents is derived as max(doc_id) + 1.

Input — link_graph.jsonl, produced by web-crawler-scheduler: one JSON object per line, outbound links per page (see that project's README):

{"url": "http://example.com/", "outlinks": ["http://example.com/a", "http://example.com/b"]}

Output — --output-dir produces a directory with three files:

manifest.json — format version and file names:

{
  "format_version": 1,
  "scores_file": "pagerank_scores.jsonl",
  "convergence_file": "convergence.json"
}

pagerank_scores.jsonl — one line per document, ordered by ascending doc_id, the direct integration contract with learning-to-rank-reranker:

{"doc_id": 0, "pagerank_score": 0.02380952380952381}

Scores across the whole corpus sum to 1.0 by construction (they are a probability distribution over the random surfer's position), so every individual value already falls within [0, 1] without any additional rescaling.

convergence.json — parameters, convergence outcome, and graph-build statistics for that run, useful for debugging and for the benchmark below:

{
  "damping_factor": 0.85,
  "tolerance": 1e-06,
  "max_iterations": 100,
  "iterations_run": 14,
  "converged": true,
  "final_delta": 9.36e-07,
  "elapsed_seconds": 0.000195,
  "total_documents": 2000,
  "resolved_edges": 11448,
  "dangling_documents": 103,
  "unresolved_source_entries": 0,
  "unresolved_target_links": 193
}

Programmatic usage

from pathlib import Path

from pagerank_link_analysis.models import PageRankParams
from pagerank_link_analysis.pipeline import PageRankPipeline

pipeline = PageRankPipeline.from_documents_path(Path("./documents.jsonl"))
result = pipeline.compute(
    Path("./link_graph.jsonl"), PageRankParams(damping_factor=0.85, tolerance=1e-8)
)

print(result.convergence.converged, result.convergence.iterations_run)
for scored in sorted(result.scores, key=lambda s: s.score, reverse=True)[:5]:
    document = pipeline.document(scored.doc_id)
    print(scored.doc_id, scored.score, document.title if document else None)

Convergence benchmark

Measured against samples/benchmark/, a reproducible synthetic reference graph (python samples/generate_benchmark_graph.py, fixed seed 42): 2,000 documents, Poisson-distributed out-degree (mean 6), 5% of pages dangling by construction, and roughly 10% of pages carrying one link outside the crawled corpus — deliberately mirroring how a real crawl's link graph loses mass to unindexed pages.

Resolved edges: 11,448. Dangling documents: 103. Unresolved target links (pointing outside the corpus): 193. The dominant cost is the sparse matrix-vector product per iteration (O(edges)), not the number of documents — this is exactly why the adjacency matrix is never densified: a dense 2000 x 2000 matrix would already be 32 MB of mostly zeros for a graph with barely 11,448 real edges, and the gap only widens at real crawl scale.

Development

pytest
ruff check .
ruff format --check .
mypy --strict src/

Tests cover the domain models (PageRankParams validation), the URL normalizer (default ports, fragments, query ordering, trailing slashes), the document resolver (exact and trivially-varied URL matches, duplicate detection), the link graph reader, the adjacency matrix builder (edge deduplication, unresolved source/target counting, dangling detection), the PageRank algorithm itself (hand-derived star and cycle graphs, mass conservation with dangling nodes, non-convergence reporting, single-document and empty-graph edge cases), the on-disk output format (round-trip), the end-to-end pipeline, and the CLI.

Troubleshooting

• A document I know is linked keeps showing up with only the baseline teleportation score: check unresolved_target_links and unresolved_source_entries in convergence.json — if the crawler's link_graph.jsonl entry for that page uses a URL that doesn't normalize to the same string as its documents.jsonl entry (a redirect chain the crawler didn't fully resolve, or a URL shape url_normalizer.py doesn't canonicalize), the edge is silently dropped by design rather than guessed at.
• ValueError: no se puede calcular PageRank sobre un corpus de 0 documentos: documents.jsonl is empty or missing doc_id/url fields — rebuild it with inverted-index-builder before recomputing PageRank.
• ValueError: URL normalizada duplicada tras normalización: two different doc_ids in documents.jsonl normalize to the same canonical URL — a data-integrity issue upstream (the crawler is supposed to deduplicate by normalized URL before a page ever reaches indexing), not something this project silently works around.
• Convergence takes far more than the iterations shown in the benchmark above: a smaller damping_factor converges faster (more teleportation mass smooths the distribution each iteration) at the cost of authority scores that lean more uniform; a link graph with many disconnected clusters typically needs more iterations than one where every page is reachable from every other.
• mypy fails under tests/: expected — only src/ is type-checked in --strict mode; test fixtures use deliberately looser typing.

License

MIT — see LICENSE.