Diameter of a random directed graph.

Question

Random directed graph $G$ has $N$ vertices, out-degree of each vertice is $K$.

Question 1.
Can I calculate the probability of this graph is strongly connected as a function from $N$ and $K$?

Question 2.

If $G$ is strongly connected, can I calculate the estimated diameter of $G$ as a function from $N$ and $K$?

Answer 1

This is only answering the connectivity question, which works basically the same as in $\mathcal G_{n,p}$.

First consider $K = \log N + C$ for some yet-to-be determined $C$. In this case, the probability that some fixed vertex has in-degree $0$ (which would imply that the graph is not strongly connected) is $(1 - \frac{K}{N-1})^{N-1} \sim e^{-K} = \frac1N e^{-C}.$ So the expected number of vertices with in-degree $0$ is $e^{-C}$.

By a similar but more involved computation, we can show that if $X$ is the number of vertices with in-degree $0$, then $\mathbb E[X(X-1)\dotsb (X-j+1)] \sim \left(e^{-C}\right)^j$. (This counts the expected number of ordered $j$-tuples of distinct vertices with in-degree $0$.) This matches the $j^{\text{th}}$ moment of a Poisson random variable, so $X$ converges in distribution to $\operatorname{Poisson}(e^{-C})$, and $\Pr[X=0] \sim e^{-e^{-C}}$.

In particular, if $C \to \infty$ with $N$, then $\Pr[X=0] \to 1$ with $N$, while if $C \to \infty$, then $\Pr[X=0] \to 0$. So in the latter case, we already know that the graph is not strongly connected with high probability.

For constant $C$, then we can argue that strongly connected components larger than a single vertex (but smaller than $N/2$) are not likely to arise. (The idea is that having a small strongly connected component of $j$ vertices requires $N-j$ vertices not to have any edges to it, which is at least as hard as having $j$ isolated vertices, but further we need to place down some very unlikely edges between those $j$ vertices.) So in fact with high probability the graph is strongly connected if and only if $X=0$. By monotonicity, this holds as $C \to \infty$ as well.

So we conclude that as $N \to \infty$, $$\Pr[\text{connected}] \sim \exp(-\exp(-(K-\log N))).$$ In particular, the graph is connected with high probability when $K$ is much larger than $\log N$ and disconnected with high probability when $K$ is much smaller than $\log N$.

Answer 2

System won't let me write a comment, so I'll write an answer instead.

I think Erdos has a famous paper on the connectivity of random graphs, basically the connectivity changes hugely before and after a certain point. http://www.renyi.hu/~p_erdos/1960-10.pdf I think this is the paper that gives some quantitative results on the topic. But in your problem the graph is directed. I am not exactly sure about what happens in that case

Answer 3

Philips et al. [1] consider the same situation and state the following (based on other references therein):

If $K ≥ (1 + ε) \ln N$, $ε ≥ 0$, the graph is almost surely strongly connected.

They also calculate asymptotic values for the diameter in the case $K \geq c \ln N$ with $c > 4$.

[1] Philips, Thomas K.; Towsley, Donald F.; Wolf, Jack K., On the diameter of a class of random graphs, IEEE Trans. Inf. Theory 36, No. 2, 285-288 (1990). ZBL0699.05046.