Pagerank in directed *acyclic* graphs (DAG)

I deal with pagerank computations on large directed acyclic graphs (DAG).

I found no reference to work on this specific case, only some work on pagerank in more specific cases, e.g., PageRank of Scale Free Growing Networks.

• Does anyone know any reference for DAGs?

• Is there any way to use DAG features to speed pagerank computations up?

A sequel of this question is posted here.

• You should be able to compute in closed form the pagerank of a vertex with no incoming edges. And so on for a vertex once all its in-neighbors' pageranks are known. So a topological sort followed by a single pass should do the trick.
– usul
Sep 20 '21 at 18:14
• This would be wonderful, and I am amazed that no paper seems to detail this! Still looking for a reference, or I will have to write it myself. Sep 20 '21 at 19:12
• I am far from an expert but from the definition I see on wikipedia: you need to have non-zero pagerank for the sources of your dag, otherwise it will be $0$ everywhere (seems to be related to so-called "damping factor" in wikipedia). And I agree with usul's comment: $pagerank(u) = f(pangerank(v_1), \dots, pangerank(v_k))$ with $v_1, \dots, v_k$ being ingoing neighbors of $u$ and $f$ being computable with $O(k)$ arithmetic operations so the whole thing is computable in $O(|E|)$ arithmetic operations, where $E$ are the edges ($O(1)$ operations per edge).
– holf
Sep 21 '21 at 4:41

As suggested by the comments (thanks!), the answer is positive and rather easy.

We want to compute the pagerank of all vertices of a DAG (Directed Acyclic Graph) $$G = (V,E)$$ with $$n$$ vertices and $$m$$ edges. For any vertex $$u$$, let us denote by $$d^+(u)$$ its out-degree: $$d^+(u) = |\{v, (u,v)\in E\}|$$.

Pagerank is basically defined as the stationnary distribution of the following random walk, for a given parameter $$\alpha$$. The walk starts at a uniformly chosen random vertex. When the walker is at vertex $$v$$, it goes with probability $$\alpha$$ to a uniformly random out-neighbor of $$v$$, and it goes with probability $$1-\alpha$$ to a uniformly random vertex. If $$v$$ has no out-going edge, then the walker stays at $$v$$ with probability $$\alpha$$.

Then, the probability to be at vertex $$x$$ after $$t$$ steps is $$p _t(x) = \frac{1-\alpha}{n} + \alpha\cdot\sum_{y, (y,x)\in E} \frac{p_{t-1}(y)}{d^+(y)}$$. Therefore, the pagerank of any vertex $$v$$ is $$p(v)$$ such that $$p(v) = \frac{1-\alpha}{n} + \alpha\cdot\sum_{u, (u,v)\in E} \frac{p(u)}{d^+(u)}$$

Clearly, if a vertex has no in-coming edge, then its pagerank is $$\frac{1-\alpha}{n}$$.

And, clearly too, if one knows the pagerank of all in-neighbors of a given vertex, the formula above gives the pagerank of this vertex.

As a consequence, one may obtain the pagerank of all vertices in $$O(n+m)$$ time and space by iteratively processing vertices such that all their in-neighbors have already been processed. An appropriate order may be obtained through a topological sorting in $$O(n+m)$$ time and space.

This leads to new questions on the on-line computation of pagerank in a DAG, that seem more difficult.