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$.
Best Answer
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...