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
- 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).
- 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.