08_pagerank

Example 08 — PageRank

What it demonstrates

Runs search/centrality.PageRank over an immutable CSR snapshot of a seeded, scale-free directed web, reads the per-node stationary ranks back through the adjacency-list mapper, and prints a deterministic top-k of pages ordered most to least important. Because the web's in-degree distribution is heavy-tailed, PageRank is genuinely non-uniform — a stable, clearly separated set of authority pages emerges rather than the all-equal scores a symmetric cycle would give.

It then exercises two further PageRank capabilities:

• Personalised PageRank (centrality.PersonalisedPushPageRank, the Andersen-Chung-Lang local-push algorithm) seeded at the top authority — a "who to read next" recommendation that re-ranks the web around one page rather than globally. The seed tops its own personalised ranking, and the overlap between the personalised and global top-k quantifies how much the view shifts.
• The reusable centrality.PageRanker — a stateful computer that caches the CSR-derived topology so repeated Run calls skip the one-time allocations the one-shot PageRank pays every call. The example verifies its result is bit-for-bit identical to the one-shot vector and shows a reused Run allocating essentially nothing per call, the same stateless/stateful split as search.Dijkstra vs search.DijkstraInto.

Domain / scenario

A directed web of pages that hyperlink to one another. An edge points from the linking page to the linked page, so a page's in-degree is how many other pages link to it, and PageRank concentrates stationary mass on high-in-degree pages that are themselves linked from high-mass pages.

The web is generated by Price's directed scale-free model (de Solla Price, 1965/1976) — the canonical directed citation/web preferential- attachment model and the directed counterpart of Barabási–Albert (classic BA is undirected). Each new page emits -links out-edges to existing pages chosen with probability proportional to their current in-degree plus an additive attractiveness constant -attract, which puts the heavy tail on the in-degree (the link targets) and keeps even never-linked pages reachable. The resulting in-degree power-law exponent is gamma_in = 2 + attract/links, so attract < links yields a tail heavier than BA's gamma = 3 and a more concentrated PageRank top-k. Targets are sampled in O(1) amortised time per edge by the redirection / edge-copying technique, so the whole web is built in O(V·links) = O(E) time in a single seeded math/rand pass and a fixed -seed fixes the shape exactly. (This topology choice was confirmed with the project's graph-theory-expert.)

The earliest-created core pages accumulate the most incoming mass (preferential attachment rewards age), so the top of the ranking is dominated by the low-index seed-core pages and is stable across runs and machines for a fixed seed. Ties on rank — common in the long tail of pages nobody links to, which sit at the teleport floor — are broken by ascending page id, so the printed top-k is fully deterministic.

How to run

go run ./examples/08_pagerank                                  # small deterministic default
go run ./examples/08_pagerank -pages 1000000 -links 8 -seed-net 16 -seed 7  # observable-scale run

Scale and flags

The default builds and ranks in well under a millisecond, comfortably inside the short-test budget. The large run grows the graph to millions of edges, where PageRank's per-iteration cost, parallel mat-vec, and live-heap footprint become observable.

Expected output

At the default config (go run ./examples/08_pagerank) the deterministic fact lines are:

config.pages=500
config.links=4
config.attract=1
config.seed_net=5
config.top_k=10
config.seed=1
nodes.pages=500
edges.links=1985
rank.1=page0000003
rank.2=page0000004
rank.3=page0000000
rank.4=page0000001
rank.5=page0000002
rank.6=page0000006
rank.7=page0000007
rank.8=page0000018
rank.9=page0000005
rank.10=page0000012
distinct_ranks=117
ppr.seed=page0000003
ppr.seed_is_top1=true
ppr.top.1=page0000003
ppr.top.2=page0000004
pageranker.matches_oneshot=true
pageranker.reuse_allocs_below_oneshot=true

The five highest-ranked pages are exactly the seed-core pages (0..4). The volatile telemetry is printed as # -prefixed lines and varies per run and per machine, for example:

# pagerank.iterations=65
# pagerank.elapsed=236µs
# build.elapsed=261µs
# build.edge_rate=7607783 edges/s
# mem.transient_mallocs=4698
# mem.heap_alloc=226.12 KiB
# mem.heap_growth=27.84 KiB
# mem.num_gc=1
# rank.1.score=0.147069
...

Note the gap between rank 5 (# rank.5.score≈0.14) and rank 6 (# rank.6.score≈0.013): the five authorities are an order of magnitude ahead of the long tail.

Evidence it collects

This is a centrality example, so it reports the dimensions the standard's taxonomy assigns to centrality work:

• Convergence iterations — # pagerank.iterations, how many power-iteration steps the run took to reach the tolerance.
• Wall-clock timing — # pagerank.elapsed (the ranking pass) and # build.elapsed / # build.edge_rate (the generation pass).
• Transient allocations — # mem.transient_mallocs, the runtime.MemStats.Mallocs delta across build + snapshot + PageRank.
• Live heap — # mem.heap_alloc and # mem.heap_growth, measured after a forced GC so they reflect reachable bytes.

When you scale up with -pages 1000000 -links 8, watch how the iteration count stays roughly flat (PageRank's convergence is largely size-independent for a fixed damping), how # pagerank.elapsed grows with the edge count as the parallel mat-vec engages, how distinct_ranks climbs (the heavy tail producing many distinct authority ranks), and how live heap scales with the graph rather than with the working set.

Key APIs

• graph/adjlist.New / AdjList.AddEdge — build the mutable directed graph.
• graph/adjlist.AdjList.Compact — right-size the adjacency arrays after the bulk build so the reported heap reflects the tight snapshot.
• graph/adjlist.AdjList.Mapper / graph.Mapper.Lookup — resolve page names to compact NodeIDs to read only the live entries from the rank slice.
• graph/csr.BuildFromAdjList — freeze the builder into an immutable CSR snapshot for the analytics pass.
• search/centrality.PageRank — power-iteration PageRank returning the per-NodeID rank slice and the iteration count to convergence.
• search/centrality.DefaultPageRankOptions — the classic Brin-Page parameters (damping 0.85, max 100 iterations, tolerance 1e-6).
• search/centrality.PersonalisedPushPageRankCtx / DefaultPPRPushOptions — Andersen-Chung-Lang local-push personalised PageRank seeded at one node.
• search/centrality.NewPageRanker / PageRanker.Run — a reusable stateful PageRank computer whose repeated runs reuse cached topology and buffers (bit-for-bit identical to the one-shot result).

Further reading

• search/centrality — centrality algorithms package documentation
• graph/csr — the immutable CSR snapshot used as the query surface
• graph/adjlist — the mutable adjacency-list builder
• Example 01 — basic shortest paths — the minimal build-snapshot-query flow this example extends
• Example 26 — social scale benchmark — the reference seeded, scale-parametrised example this one follows
• docs/examples-standard.md — the standard every example follows