0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Are you saying the out-degree of each vertex is $K$? $\endgroup$ – quasi Apr 27 '17 at 23:43
  • $\begingroup$ Yes, it is out-degree $\endgroup$ – kotomord Apr 28 '17 at 7:47
  • 1
    $\begingroup$ 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. $\endgroup$ – Smylic Apr 28 '17 at 11:23
1
+50
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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