7
$\begingroup$

I'm interested in the statistics of strongly connected components in random directed graphs. However, I'm unable to find any results on this, partly because I don't know the terminology to search for.

By "random directed graph" I mean a digraph with $N$ nodes, where every possible edge has a uniform probability $p$ of being included in the graph, independently of the other edges. For undirected graphs this is sometimes known (possibly erroneously) as the Erdös-Rényi model, but for digraphs I don't know the correct term.

Equivalently, given a random (in general non-symmetric) matrix where every element has an independent probability of being non-zero, one can do a change of basis using a permutation matrix to put it in block upper triangular form; I'm interested in the statistics of the number and size of the resulting blocks on the diagonal.

I'm most interested in knowing the expected number of strongly connected components of size $>1$, for a given $N$ and $p$, but any results concerning the statistics of the strongly connected components (e.g. the size of the largest one) would be enormously helpful. I'm interested primarily in the limit of large $N$, for non-extreme values of $p$.

$\endgroup$
  • $\begingroup$ This m.se question might be useful. $\endgroup$ – Ben Barber Feb 3 '15 at 9:19
  • $\begingroup$ What exactly do you mean by "non-extreme values of $p$"? For fixed $p\in(0,1)$ and $N\to\infty$ there will still be a unique component w.h.p. ... $\endgroup$ – Vincent Beffara Feb 6 '15 at 11:55
  • $\begingroup$ @VincentBeffara I just meant that I'm not just interested in the easier cases where p is close to 0 or 1, I care about the intermediate values as well. $\endgroup$ – Nathaniel Feb 7 '15 at 3:02
  • $\begingroup$ This is a good paper to start with: Karp, R. M. (1990). The transitive closure of a random digraph. Random Structures Algorithms 1, 73–93 $\endgroup$ – Valentas Mar 17 '15 at 21:25
  • $\begingroup$ @Nathaniel Although this is a year old post, but since then, have you finally come across relevant bits of the graph theory literature in regard to study of random digraphs? I am very much interested as well. $\endgroup$ – Phonon Jun 17 '16 at 13:47
6
+50
$\begingroup$

Two quick remarks.

First, given a directed graph you can always forget about edge orientation (saying that an unoriented edge is open iff one of its orientations was open in the directed version), and by domination, if $p \leq c/N$ with $c<1/2$ the usual Erdös-Renyi results will tell you something: the largest strongly connected component will be at most logarithmic in $N$, and the number of components will be linear in $N$. For a lower bound you might want to look for open cycles, I didn't check what you get this way but I would expect it to be sharp.

If you just have $p \leq c/N$ with $c<1$, the Erdös-Renyi results tell you little but the proofs (based on cluster explorations) would still work, because they essentially look at edges in a directed fashion, and you would still get $\log N$ as an upper bound. And again the lower bound would have to be obtained separately.

Second, you can build a directed graph from a pair of undirected graphs (one for each orientation), and two vertices that are connected in both are strongly connected in the oriented version. From that, if $p \geq c/N$ with $c>1$, both unoriented copies will have a giant component of size $N-O(\log N)$ and so will the directed version.

Now within the critical window, things might become trickier...

$\endgroup$
2
$\begingroup$

First, this model is typically denoted $D(n,p)$. I'm not aware of a formal name, but personally I like to call it the Bernoulli random digraph. For $p=c/n$, note that the number of vertices with out-degree zero is going to be on the order of $n$. So in this range, the number of strong components will also be on the order of $n$.

The phase transition for this model where a large strongly connected component emerges is due to Richard Karp and Tomasz Łuczak (Łuczak considers the analogous model $D(n,m)$ where $m$ directed edges are uniformly at random chosen to be present).

Karp shows that for $p=c/n$ and $c<1$, and any $\omega \to \infty$ however slowly, w.h.p. each strong component of $D(n,p)$ has at most $\omega$ vertices. For $c>1$, there is a unique strong component with roughly $\Theta^2 n$ vertices where $\Theta$ is the unique positive root of $1-\Theta = e^{-c \Theta}$; in this case, w.h.p. all other strong components contain at most $\omega$ vertices. It is not a coincidence that the number of vertices in the giant component of $G(n,p=c/n)$ is roughly $\Theta n$ vertices.

Boris Pittel and I recently proved that for $D(n, p=c/n), c>1$, the number of vertices in the largest strong component is asymptotically normal. In fact, we show that the pair of the numbers of vertices and arcs in the strong giant is jointly asymptotically 2-dim normal.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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