1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.