PageRank at Web Scale

PageRank is a ranking prior for a graph. It asks a deliberately blunt question: if a random surfer follows links most of the time and teleports occasionally, which pages accumulate probability mass?

The update is:

$$r_{t+1} = \alpha P^\top r_t + (1 - \alpha) v$$

where $P$ is the normalized link matrix, $v$ is the teleport distribution, and $\alpha$ is usually around 0.85.

The Scaling Trick #

The web graph is sparse, so the implementation is mostly about careful sparse matrix-vector multiplication:

rank_next = teleport
for source in pages:
  share = alpha * rank[source] / out_degree[source]
  for target in out_links[source]:
    rank_next[target] += share

Dangling nodes need special handling because they have no outgoing links. A common approach is to redistribute their rank mass through the teleport vector.

What PageRank Is Not #

PageRank is not relevance. It is closer to authority or centrality. In a production ranking system, it is usually one feature among many: useful as a prior, dangerous as the whole answer.