PAGERANK a page is important if important pages point to it
The algorithm that launched Google: rank a web page by the chance a random surfer, clicking links forever, lands on it. That chance is the dominant eigenvector of the link matrix — found by multiplying a vector by the matrix over and over until it stops changing. The link matrix is a 2-D array (the box’s open want); one power-iteration step runs in real I-13.
THE TECHNIQUE power iteration with a damping factor
Every page starts equal. Each round, each page hands its score out evenly along its links; a damping factor (~0.85) mixes in a small chance of jumping anywhere (so dead-ends don’t swallow the score). Repeat until the scores settle — that fixed point is the ranking. Watch it converge on a small web. live demo
HISTORY & CREDIT an old idea, at web scale
“Page invented PageRank” — the ranking of things by who points to them was new in 1998 decades old; the leap was doing it on the whole web. cited
1953 / 1972 · Katz and Bonacich define centrality by who points to you, weighted by their own importance — eigenvector centrality, the same fixed-point idea. 1976 · Pinski & Narin rank journals by citation “influence weights” — the closest precedent: importance flows along citations, solved as an eigenvector. 1996–97 · Robin Li develops RankDex (1996; US patent filed 1997, granted 1999 — later a seed of Baidu) and Massimo Marchiori’s HyperSearch (WWW6, 1997 — Page saw it presented, and cited it) already rank pages by link structure. 1998 · Larry Page & Sergey Brin (Stanford; their 1996 project “BackRub” grew into it) apply it to the web’s link graph with a random-surfer damping term that guarantees a unique stationary distribution on the messy real web; the name puns on “web page” and on Page. Kleinberg’s HITS is contemporaneous. the engine · the ranking is a Markov chain’s stationary distribution = the principal eigenvector, and power iteration converges because the second eigenvalue is bounded by the damping factor.
The math was Katz’s and Pinski-Narin’s; the billion-page matrix was the moon-shot. eigenvector centrality
RECOMMEND FOR I-13 the link matrix is a 2-D array
Power iteration is matrix × vector, repeated. The link matrix is a genuine 2-D array; flattened row-major (i*n+j, like the Hungarian cost matrix), one step runs on the compiler:
$ i13 run matvec.i13 # one power-iteration step over a flattened link matrix
r0 = 5 r2 = 3 # row . vector, links as a 1-D row-major array
Recommend: presses PS-004 (a 2-D array) — with Smith-Waterman (054), knapsack (053), and the Hungarian algorithm (064). The multiply-accumulate is array reads and + *; the damping and normalisation are scalar arithmetic; no bignum, no bitwise. A flattened 1-D array runs the whole iteration today (verified above); a real 2-D array would let the matrix read like the textbook. Note: the fourth dart to land on the 2-D-array want — the campaign’s clearest signal after multiple-return that a matrix type is the next honest addition.