← All Cracked Math projects
PM-B06NOT STARTEDBEGINNERMATHPYTHONIMPACT ★☆☆☆☆

PageRank of the Python standard library

Which standard-library module is the most important? Let power iteration decide.

EST.6 h
REWARD+200 XP
AFTERoriginal

ML-ARENA BENCHMARKS

PROOF: BENCH
METRICINDUSTRYMINE
L1 distance to the reference ranking, iterations to reach 1e-10, wall time
GOAL · L1 <= 1e-9 vs networkx; >= 5x faster than networkx on the same graph; observed per-iteration error ratio (how much the error shrinks each step) within 5% of |lambda_2|
networkx.pagerank · measured locally—
no results yet
YOUR RESULTS

Your recorded results appear here.

Brief

Parse every module in CPython's Lib/ folder with Python's `ast` module to build the import graph (an edge from A to B when module A imports module B). Store the graph in a CSR structure you write yourself (compressed sparse row: arrays that store only the nonzero entries of each row). Rank modules with power iteration: multiply a vector by the matrix again and again until it stops changing. Include dangling-node handling (modules that import nothing) and damping (a fixed chance of jumping to a random module instead of following an import). Separately, compute |lambda_2| of the Google matrix (the size of its second-largest eigenvalue) and show that the measured convergence rate tracks it.

VICTORY CONDITIONS

  1. L1 <= 1e-9 vs networkx; >= 5x faster than networkx on the same graph; observed per-iteration error ratio (how much the error shrinks each step) within 5% of |lambda_2| (L1 distance to the reference ranking, iterations to reach 1e-10, wall time).
  2. A public repository with a README that shows your result and how to reproduce it.

Terms in plain words

PageRank
A score for each node in a graph equal to the long-run share of time a random walker spends there.
Power iteration
Finding a matrix's dominant eigenvector by multiplying a vector by the matrix repeatedly and normalising.
CSR (compressed sparse row)
A storage format for sparse matrices that keeps only the nonzero values, their column indices, and where each row starts.
Google matrix and damping
The PageRank transition matrix after mixing in a small chance of jumping to a random node; the damping factor sets that mix.
|lambda_2|
The size of the second-largest eigenvalue; power iteration's error shrinks by about this factor every step.

Why it rates ★☆☆☆☆

The graph is toy-sized. It matters only as the first step toward A06 and W02.