← All Base Form Math projects
BM-10NOT STARTEDBASE FORM · LINEAR ALGEBRAMATHPYTHON

Wikipedia ranker

Rank the most important pages in Simple English Wikipedia from its link graph using a random-surfer model.

EST.8 h
REWARD+100 XP
AFTERNayuki

ML-ARENA BENCHMARKS

YOUR NUMBER VS THE INDUSTRY'S
METRICINDUSTRYMINE
top-100 ranking
GOAL · Spearman ρ ≥ 0.99
networkx.pagerank—
no results yet
YOUR RESULTS

Your recorded results appear here.

Brief

Which Wikipedia page matters most? You will answer that from the links alone, with the idea behind Google's original PageRank. A page is important if important pages link to it. That sounds circular, and it is: the answer is an eigenvector, the same kind you found in BM-07.

Picture a random surfer. On each step, with probability d=0.85d = 0.85 it clicks a random link on the current page, and otherwise it jumps to any page at random. A page's rank is the long-run probability of finding the surfer there. This is your first use of probability rules. The chance of being on page ii next step adds up every way to get there, each one a conditional probability P(i∣j)P(i \mid j) times the chance P(j)P(j) of being on page jj now:

ri=1−dN+d∑j→irjout(j)r_i = \frac{1 - d}{N} + d \sum_{j \to i} \frac{r_j}{\text{out}(j)}

Here out(j)\text{out}(j) is the number of links on page jj. Probabilities must sum to 1, so a dangling page with no links shares its rank evenly with every page.

The graph has a few hundred thousand articles. A dense N×NN \times N matrix of float64 would take hundreds of gigabytes, but each page links to only a handful of others. A sparse matrix stores just those links, and one step of power iteration is one sparse matrix-vector product.

VISUALFig. 1
Bigger circle, higher rank. Ranks are probabilities and sum to 1. E links nowhere, so the surfer jumps from E to a random page. A 0.360 B 0.199 C 0.369 D 0.036 E 0.036
Five pages, damping 0.85. A and C trade links and collect most of the rank. D and E get only the random jumps. Why it's here: A graph small enough to check by hand. Objective 4 uses it to test your ranker before the full dump.
HINT · OBJECTIVE 2
Stuck? Hints stay hidden until you ask.
HINT · OBJECTIVE 5
Stuck? Hints stay hidden until you ask.

DATA · Simple English Wikipedia dump

Objectives

0 / 6 CLEARED

Read-only. Log in to update progress.

VICTORY CONDITIONS

  1. Spearman ρ ≥ 0.99 between your ranks and networkx.pagerank on its top 100 pages, recorded with `python tools/mlarena.py record BM-10 "rho = <your value>"`.
  2. Your ranks sum to 1 within 1e-9 after every step, and the whole run never builds a dense N × N matrix.
  3. A README with your top 20 pages and a short note on any page that surprised you.

Side quests

Personalise the jump. Send the surfer only to science pages when it teleports, and see how the top 20 changes.
Plot the change per step on a log scale and check that it shrinks at least as fast as a factor of 0.85 per step.

Terms in plain words

Sparse matrix
A matrix that is almost all zeros, stored as a list of its non-zero entries only. The link matrix has a few million entries instead of tens of billions.
CSR format
Compressed sparse row, the scipy.sparse layout that stores each row's non-zero values and column numbers back to back, so multiplying by a vector is fast.
Conditional probability
P(A | B) is the chance of A given that B happened. Here, the chance of clicking to page i given that you are on page j.
Random surfer and damping
An imaginary reader who follows a random link with probability d (usually 0.85) and otherwise jumps to a random page.
Dangling page
A page with no outgoing links. The surfer has nowhere to click, so it jumps to a random page instead.