In-degree and out-degree distributions of a directed graph

Question

For an undirected random graph with n nodes and probability p that any node u connects to any node v (apart from node u, i.e. no self-loops), the degree distribution is the binomial:

$$p_k = {n-1 \choose k} p^k (1-p)^{n-k-1}$$

However, what if the graph is random but directed? Are the in-degree and out-degree distributions the same as the above? Intuitively it feels like this is the case, but how do I show it?

Answer 1

As long as edges are independently generated, we still get a binomial distribution for the in-degree and out-degree.

Specifically, there's two ways we can try to generate a random directed graph:

• For each ordered pair $(u,v)$ with $u \ne v$, add a directed edge from $u$ to $v$ with probability $p$. Then the in-degree and out-degree of a vertex have the same binomial distribution for essentially the same reason. Say we're considering the in-degree of a vertex $v$. Then there are $n-1$ potential directed edges $(u,v)$ that could contribute: one for each possible $u$. Each of them exists independently with probability $p$, and their total number is the in-degree. That's exactly what the binomial distribution is for: the probability of in-degree $k$ is $$\binom{n-1}{k} p^k (1-p)^{n-1-k}.$$
• For each unordered pair $\{u,v\}$, with $u \ne v$, add an edge between $u$ and $v$ with probability $q$, and direct it in one of the two possible directions with probability $\frac12$. This avoids having edges going in both directions between $u$ and $v$, which may or may not be something you want. Anyway, in this setup, the in-degree and out-degree are binomial: the probability of in-degree $k$ is $$\binom{n-1}{k}(\tfrac q2)^k (1 - \tfrac q2)^{n-1-k}.$$

The formula $\binom{n-1}{k} p^k (1-p)^{n-1-k}$ for random graphs does not come out of nowhere: we have $\binom{n-1}{k}$ ways to pick $k$ potential edges out of a vertex, $p^k$ probability that all of them are present, and $(1-p)^{n-1-k}$ probability that all the others are absent. As long as we can do the same in the directed case (which we can), the same formula holds.