PAGERANK

Random surfer model — power iteration convergence

12
0.85
1x
PageRank (Page, Brin, Motwani, Winograd 1998) models a random surfer who follows a link with probability d (damping factor) or jumps to a random page with probability 1-d. The stationary distribution of this Markov chain gives each page's rank. Mathematically, PR(v) = (1-d)/N + d·Σ PR(u)/out(u). Power iteration converges geometrically at rate d — typically d=0.85 converges in ~50 iterations. The principal eigenvector of the modified adjacency matrix gives exact ranks. PageRank revolutionized web search and underlies modern network centrality measures in biology, citation analysis, and social networks.