4
$\begingroup$

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.

$\endgroup$
3
  • 4
    $\begingroup$ 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. $\endgroup$
    – usul
    Sep 20 at 18:14
  • $\begingroup$ 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. $\endgroup$ Sep 20 at 19:12
  • $\begingroup$ 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). $\endgroup$
    – holf
    Sep 21 at 4:41
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.