The PageRank Algorithm: Random Surfer Models, Damping Factors & Power Iteration

PageRank revolutionized internet search by treating the web hyperlink structure as a democratic citation graph, calculating the structural authority of every indexed document.

The Random Surfer Model

PageRank models an idealized web surfer who follows links at random. With probability d (the damping factor, typically set to 0.85), the surfer clicks an outgoing hyperlink on the current page; with probability 1 - d, the surfer teleports to a completely random URL across the web.

Computing PageRank at Scale: Power Iteration

For graphs with billions of nodes, PageRank is computed as the principal eigenvector of the stochastic transition matrix using power iteration until the rank vector converges within an epsilon tolerance.