Assume a DAG (Directed Acyclic Graph) is given as a stream of edges such that edge $(u,v)$ is given only after all incoming edges of $u$ are given. Let us denote by $n$ and $m$ the number of vertices and edges in this graph. Notice that, here, $n$ is in $O(m)$.
We want to output the pagerank of vertices in this graph on-line: we cannot store it nor read it several times, and we want to output pagerank values as soon as possible.
This question on pagerank in DAG and its answer show that this is feasible in $O(n)$ space and $O(m)$ time, if the number $n$ of vertices is known.
My first questions are: can we do better for space with a specific ordering of the edge stream? maybe with assumptions on maximal in- and out-degrees?
Most importantly, the approach above requires that $n$ is known from the beginning. What if $n$ is unknown?
Since the results depend on $n$, one has to store some information for each of the $n$ vertices and then output the value when one reaches the end of input, which gives $O(n)$ space.
This leads to my second, more important set of questions: would it be possible to output some values (or some expressions) such that the pagerank of all vertices can be easily computed from them once $n$ is known? With what space and time complexity?
