3
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ This is a tricky random graph model to work with, I think; it's a lot easier to answer this question in the Erdos-Renyi model $G(n, p)$ (you just get a binomial distribution) and I think the answer should be asymptotically similar as things get large (setting $p = \frac{m}{ {n \choose 2} }$). $\endgroup$ Commented Oct 14, 2020 at 18:58
  • 1
    $\begingroup$ You'd still get a mixture of two binomial distributions in the $G(n,p)$-equivalent model, because of the loops. $\endgroup$ Commented Oct 14, 2020 at 19:17

1 Answer 1

Reset to default
3
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.