Graph algorithms

PageRank for DAGs

A topological order turns repeated updates into a single pass. The key is handling nodes with no outgoing edges correctly.

PageRank is usually computed by updating every node’s score again and again. On a directed acyclic graph, or DAG, there is a simpler route: process the nodes in topological order, then normalize the scores.

The result is an \(O(N + E)\) algorithm. There is one important condition: we must specify what happens when the random walk reaches a node with no outgoing edges.

Start with the random walk

The intuition behind PageRank is recursive: a node is important when important nodes link to it. A random walk turns that idea into a probability distribution.

Let the graph have \(N > 0\) nodes and \(E\) directed edges. Let \(d_j\) be the number of outgoing edges from node \(j\). We use a column convention: the entry \(M_{ij}\) describes a step from node \(j\) to node \(i\).

\[ M_{ij} = \begin{cases} \dfrac{1}{d_j} & \text{if } j \to i,\\[4pt] 0 & \text{otherwise}. \end{cases} \]

If a node has three outgoing edges, each gets one third of its outgoing probability. If it has no outgoing edges, its column in \(M\) is zero. Such a node is called a dangling node, or a sink.

Choose a damping factor \(0 < \alpha < 1\). At a node with outgoing edges, follow a random edge with probability \(\alpha\), and jump to a uniformly chosen node with probability \(1-\alpha\). At a dangling node, jump to a uniformly chosen node. This is the usual uniform-teleportation, uniform-dangling convention.

Write \(\mathbf v = \frac{1}{N}\mathbf 1\). Let \(s_j=1\) for a dangling node and \(s_j=0\) otherwise. The full transition matrix is

\[ P = M + \mathbf v\mathbf s^\top. \]

Every column of \(P\) sums to one. The PageRank vector is the stationary distribution:

\[ \mathbf r = \alpha P\mathbf r + (1-\alpha)\mathbf v, \qquad \mathbf 1^\top\mathbf r = 1. \]

With our column convention, the product is \(P\mathbf r\), not \(P^\top\mathbf r\). A common solver uses power iteration:

\[ \mathbf r^{(t+1)} = \alpha P\mathbf r^{(t)} + (1-\alpha)\mathbf v. \]

For a sparse graph, each update costs \(O(N+E)\). Running \(k\) updates costs \(O(k(N+E))\). A DAG lets us avoid those repeated updates.

What the DAG gives us

A DAG has no directed cycles. Its nodes can be placed in a topological order \(v_1,\ldots,v_N\), so every edge \(v_i\to v_j\) satisfies \(i<j\).

With destination rows and source columns, this makes \(M\) strictly lower triangular:

\[ M = \begin{bmatrix} 0 & 0 & 0 & \cdots & 0\\ M_{21} & 0 & 0 & \cdots & 0\\ M_{31} & M_{32} & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ M_{N1} & M_{N2} & M_{N3} & \cdots & 0 \end{bmatrix}. \]

Each node receives contributions only from earlier nodes. The catch is that \(P\) is not triangular: the dangling-node jumps can point anywhere. We therefore solve a simpler triangular system first.

Compute scores in one pass

Define an intermediate vector \(\mathbf q\) using the original edges only:

\[ \mathbf q = (1-\alpha)\mathbf v + \alpha M\mathbf q. \]

These are not yet normalized PageRank probabilities. In topological order, compute each entry as

\[ q_i = \frac{1-\alpha}{N} + \alpha\sum_{j:\,j\to i}\frac{q_j}{d_j}. \]

The denominator is \(d_j\), the outgoing degree of the source node. Every \(q_j\) in the sum is already known. A node with no incoming edges starts with \((1-\alpha)/N\).

After processing all nodes, normalize once:

\[ Z=\sum_{i=1}^{N}q_i, \qquad r_i=\frac{q_i}{Z}. \]

This gives the PageRank distribution for the random walk defined above. It needs one pass over the edges, plus a pass over the nodes to normalize.

Why normalization handles the sinks

Let \(D=\mathbf s^\top\mathbf r\) be the total PageRank probability at dangling nodes. Expanding the full PageRank equation gives

\[ \mathbf r =\alpha M\mathbf r +\bigl((1-\alpha)+\alpha D\bigr)\mathbf v. \]

Both teleportation and dangling-node jumps use the same vector \(\mathbf v\). Together, they add one common scale factor to that vector.

Since \(M\) is strictly lower triangular, \(I-\alpha M\) is invertible. Both \(\mathbf r\) and \(\mathbf q\) are therefore scalar multiples of the same vector:

\[ \begin{aligned} \mathbf q &= (1-\alpha)(I-\alpha M)^{-1}\mathbf v,\\ \mathbf r &= \bigl((1-\alpha)+\alpha D\bigr) (I-\alpha M)^{-1}\mathbf v. \end{aligned} \]

Normalizing \(\mathbf q\) selects the multiple whose entries sum to one. That is \(\mathbf r\). No matrix inverse needs to be formed in code; the topological pass solves the triangular system directly.

The sink rule matters. If dangling nodes keep their probability through self-loops, or redistribute it using a different vector, this normalization argument no longer applies unchanged. The same derivation does work with a nonuniform personalization vector, provided teleportation and dangling-node redistribution both use that vector.

The useful distinction

The DAG structure makes the link-only system triangular. The sink policy tells us how to turn its solution into PageRank. With matching teleportation and dangling-node distributions, the recipe is simple: compute in topological order, then normalize.

References

Back to the blog