<p>As suggested by the comments (thanks!), <strong>the answer is positive</strong> and rather easy.</p>
<p>We want to compute the pagerank of all vertices of a DAG (Directed Acyclic Graph) <span class="math-container">$G = (V,E)$</span> with <span class="math-container">$n$</span> vertices and <span class="math-container">$m$</span> edges. For any vertex <span class="math-container">$u$</span>, let us denote by <span class="math-container">$d^+(u)$</span> its out-degree: <span class="math-container">$d^+(u) = |\{v, (u,v)\in E\}|$</span>.</p>
<p>Pagerank is basically defined as the stationnary distribution of the following random walk, for a given parameter <span class="math-container">$\alpha$</span>. The walk starts at a uniformly chosen random vertex. When the walker is at vertex <span class="math-container">$v$</span>, it goes with probability <span class="math-container">$\alpha$</span> to a uniformly random out-neighbor of <span class="math-container">$v$</span>, and it goes with probability <span class="math-container">$1-\alpha$</span> to a uniformly random vertex. If <span class="math-container">$v$</span> has no out-going edge, then the walker stays at <span class="math-container">$v$</span> with probability <span class="math-container">$\alpha$</span>.</p>
<p>Then, the probability to be at vertex <span class="math-container">$x$</span> after <span class="math-container">$t$</span> steps is <span class="math-container">$p
_t(x) =  \frac{1-\alpha}{n} + \alpha\cdot\sum_{y, (y,x)\in E} \frac{p_{t-1}(y)}{d^+(y)}$</span>. Therefore, the pagerank of any vertex <span class="math-container">$v$</span> is <span class="math-container">$p(v)$</span> such that
<span class="math-container">$$
p(v) = \frac{1-\alpha}{n} + \alpha\cdot\sum_{u, (u,v)\in E} \frac{p(u)}{d^+(u)}
$$</span></p>
<p>Clearly, if a vertex has no in-coming edge, then its pagerank is <span class="math-container">$\frac{1-\alpha}{n}$</span>.</p>
<p>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.</p>
<p>As a consequence, one may obtain the pagerank of all vertices in <span class="math-container">$O(n+m)$</span> 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 <a href="https://en.wikipedia.org/wiki/Topological_sorting" rel="nofollow noreferrer">topological sorting</a> in <span class="math-container">$O(n+m)$</span> time and space.</p>
<p>This leads to <a href="https://cstheory.stackexchange.com/questions/50582/on-line-pagerank-in-a-streaming-dag-directed-acyclic-graph">new questions on the on-line computation of pagerank in a DAG</a>, that seem more difficult.</p>

CC BY-SA 4.0
2021-10-06T10:35:48.900Z
2021-10-07T09:37:03.583Z
2021-10-07T09:37:03.583Z
Matthieu Latapy
<p>I deal with <a href="https://en.wikipedia.org/wiki/PageRank" rel="nofollow noreferrer">pagerank</a> computations on large <a href="https://en.wikipedia.org/wiki/Directed_acyclic_graph" rel="nofollow noreferrer">directed <strong>acyclic</strong> graphs (DAG)</a>.</p>
<p>I found no reference to work on this specific case, only some work on pagerank in more specific cases, <em>e.g.</em>, <a href="https://hal.archives-ouvertes.fr/inria-00070168/" rel="nofollow noreferrer">PageRank of Scale Free Growing Networks</a>.</p>
<ul>
<li><p>Does anyone know any reference for DAGs?</p>
</li>
<li><p>Is there any way to use DAG features to speed pagerank computations up?</p>
</li>
</ul>
<p>A sequel of this question is posted <a href="https://cstheory.stackexchange.com/questions/50582/on-line-pagerank-in-a-streaming-dag-directed-acyclic-graph">here</a>.</p>

CC BY-SA 4.0
2021-09-20T18:14:10.753Z
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
CC BY-SA 4.0
2021-09-20T19:12:55.600Z
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.
Matthieu Latapy
CC BY-SA 4.0
2021-09-21T04:41:02.573Z
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
<graph-theory><graph-algorithms><directed-acyclic-graph><data-mining><ni.networking-internet>
Pagerank in directed *acyclic* graphs (DAG)
Matthieu Latapy
# Pagerank in directed *acyclic* graphs (DAG)

(Asked by: username_0 on 2021-09-20)

I deal with [pagerank](https://en.wikipedia.org/wiki/PageRank) computations on large [directed **acyclic** graphs (DAG)](https://en.wikipedia.org/wiki/Directed_acyclic_graph).

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](https://hal.archives-ouvertes.fr/inria-00070168/).

* 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](https://cstheory.stackexchange.com/questions/50582/on-line-pagerank-in-a-streaming-dag-directed-acyclic-graph).

**Tags:** graph-theory, graph-algorithms, directed-acyclic-graph, data-mining, ni.networking-internet

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: 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 username_1'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).  

---

## 1 answers

### Answer by username_0 on 2021-10-06. Score: 6 | Accepted answer

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](https://en.wikipedia.org/wiki/Topological_sorting) in $O(n+m)$ time and space.

This leads to [new questions on the on-line computation of pagerank in a DAG](https://cstheory.stackexchange.com/questions/50582/on-line-pagerank-in-a-streaming-dag-directed-acyclic-graph), that seem more difficult.


---

