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 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 next step adds up every way to get there, each one a conditional probability times the chance of being on page now:
Here is the number of links on page . 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 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.
DATA · Simple English Wikipedia dump
Objectives
Read-only. Log in to update progress.
VICTORY CONDITIONS
- 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>"`.
- Your ranks sum to 1 within 1e-9 after every step, and the whole run never builds a dense N × N matrix.
- A README with your top 20 pages and a short note on any page that surprised you.
Side quests
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.