# Diameter of a random directed graph.

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$?

• Are you saying the out-degree of each vertex is $K$? – quasi Apr 27 '17 at 23:43
• Yes, it is out-degree – kotomord Apr 28 '17 at 7:47
• If $K \le \frac{N}2 - 1$ there is non-zero probability that graph is not strongly connected and therefore has infinite diameter. Thus expected value of diameter is $+\infty$ in this case. – Smylic Apr 28 '17 at 11:23

## 2 Answers

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

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

• Why can't you comment? You have $50$+ reputation. – Eric Lee May 7 '17 at 14:58
• Ha, at the time I wrote this I didn't... I'm a quite new user – Oliver May 7 '17 at 20:33
• Oh, alright :D. – Eric Lee May 7 '17 at 23:42