Before PageRank, search engines ranked results by how many times the search term appeared on the page. That was gameable: stuff a page with keywords and you’d rank for them. PageRank’s insight was that a link from one page to another is an implicit endorsement. A page linked to by many high-quality pages is probably high quality itself.

The Algorithm#

Each page starts with a rank of 1/N (where N is the total number of pages). On each iteration:

A page’s rank is the sum of (rank / outgoing_links) from every page that links to it. Add a damping factor: with probability 0.85, the user follows a link; with probability 0.15, they jump to a random page. This prevents rank from pooling in link sink pages (pages with no outgoing links).

PR(page) = (1 - d) / N + d * sum(PR(incoming_page) / outgoing_links(incoming_page))

Where d = 0.85 damping factor

This is iterated until ranks converge (change less than a threshold per iteration). Typically 50-100 iterations on the full web graph.

Why It Requires Distributed Computing#

The web has hundreds of billions of pages. The PageRank matrix (one row per page, one column per link) doesn’t fit in memory on any single machine. PageRank is computed using MapReduce or a graph processing framework.

One iteration of MapReduce PageRank:

Map: for each page, emit (linked_page, PR(current_page) / outgoing_links) for each link.

Reduce: sum all contributions for each page, apply the damping factor formula.

50 iterations means 50 MapReduce jobs, each reading and writing the full page rank dataset. Even distributed, a full PageRank computation on the web takes days.

graph TD A[Page A: PR=0.4, links to B and C] --> B[Emit: B receives 0.2] A --> C[Emit: C receives 0.2] D[Page D: PR=0.6, links to B] --> E[Emit: B receives 0.6] B --> F[Reduce: B new PR = damping factor times sum of contributions] E --> F F --> G[Iterate 50 times until convergence] style A fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style B fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style C fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style D fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style E fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style F fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style G fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff

PageRank Today#

Google still uses link-based signals, but PageRank alone hasn’t been the primary ranking signal for over a decade. Machine-learned ranking models that consider hundreds of signals have replaced it at the top of the stack. PageRank remains one input.

The algorithm also applies beyond search: finding influential users in social graphs, identifying important nodes in infrastructure dependency graphs, recommending “similar” content based on link structure rather than content similarity.

At Oracle#

We analyzed configuration dependency graphs to find which configs were most “important” in the sense of having many dependents. A change to a widely-depended-on config was high-risk. We computed a simplified PageRank on the dependency graph: configs that many other configs depended on got high scores. High-score configs required extra review before changes were deployed. It caught several near-misses where a low-level config was about to be changed without realizing it affected 200+ downstream configs.

What I’m Learning#

PageRank is an eigenvector calculation disguised as an iterative algorithm. The distributed systems challenge is running it on a graph that doesn’t fit in memory. The conceptual insight, that link structure encodes authority, is applicable far beyond web search.

Have you used graph-based ranking or influence scoring in systems outside of search?