Distribution of degree in random graph

Question

Let $\mathcal G(n, m)$ be a graph on $n$ vertices and $m$ edges chosen uniformly from the set of all possible such graphs. I would like to determine the distribution of the degree $d_i$ of some node $i$.

That is, I am trying to determine $$P\left[ d_i = k \right], \,\, k\in \mathbb N_0.$$ I haven't been able to write down a general formula but a few observations I've made:

• if $m=1$ then there must be either two nodes of degree $1$ or one node of degree $2$ (those are the possible ways of distributing the total degree $2m$ across the graph). There are $\sum_{k=1}^nk = n(n-1)/2$ graphs of the former category with two nodes of degree $1$, and there are $n$ graphs of the latter category with one node of degree $2$. If we write $T = n + n(n-1)/2$ for the total number of possible graphs, then we have

$$P\left[ d_i = 1 \right] = \frac{2}{n} \cdot \frac{n(n-1)}{2T} = \frac{2(n-1)}{2n + n(n-1)}$$ and $$P\left[ d_i = 2 \right] = \frac{1}{n} \cdot \frac{n}{T} = \frac{1}{T}$$

• The problem seems to get much more complicated for $m>1$
• There could be a simpler algebraic way of doing this via the adjacency matrix.

I would appreciate any help!

Answer 1

I am assuming you have at most one copy of every possible edge.

Without loops, this would be a hypergeometric distribution:

• we make $m$ draws without replacement from the set of all possible edges;
• $n-1$ of the possible edges are "successful" edges, and contribute $1$ to the degree of node $i$;
• we are interested in the probability that we draw $k$ successful edges.

We'd have $$\Pr[d_i = k] = \frac{\binom{n-1}{k} \binom{N-n-1}{m-k}}{\binom Nm}$$ where $N = \binom n2$ is the total number of possible edges.

Allowing a loop that contributes $2$ to the degree of node $i$ complicates things, because that edge is a "doubly successful" edge that doesn't fit into the hypergeometric framework. The best way to compute the probability is by casework: do we have the loop edge or not? This gives us $$ \Pr[d_i = k] = \frac{\binom{n-1}{k-2} \binom{N-n}{m-k+1} + \binom{n-1}k \binom{N-n}{m-k}}{\binom Nm} $$ where $N$ is still the total number of possible edges, except now $N = \binom n2 + n = \binom{n+1}{2}$.

Here, $\binom{n-1}{k-2} \binom{N-n}{m-k+1}$ counts the number of ways to choose a loop and $k-2$ other edges incident to node $i$, and $m-k+1$ edges not incident to $i$. The second term $\binom{n-1}k \binom{N-n}{m-k}$ counts the number of ways to choose $k$ edges incident to node $i$ that are not the loop, and $m-k$ edges not incident to $i$.