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\).
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
Every column of \(P\) sums to one. The PageRank vector is the stationary distribution:
With our column convention, the product is \(P\mathbf r\), not \(P^\top\mathbf r\). A common solver uses power iteration:
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:
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:
These are not yet normalized PageRank probabilities. In topological order, compute each entry as
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:
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
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:
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
- NetworkX PageRank documentation, including its default dangling-node convention.
- PageRank in directed acyclic graphs, the discussion linked in the original note.