5

Does the joint distribution of the degrees of an Erdős–Rényi graph have a closed form?

Toney Shields
  • 882
  • I don't think it's going to have a closed form as its highly dependent on the graph structure: You'd have to incorporate some kind of inclusion-exclusion summing over vertices and edges. – Alex R. Aug 25 '16 at 16:25

1 Answers1

4

It's not clear whether you're taking the degree distribution to be labelled or not. In case of labelled vertices (i.e. where we don't need to worry about graph homomorphisms), the answer is probably not. Here's why:

Let $D=(d_1, d_2, \dots, d_n)$ be any viable degree distribution on $n$ labelled vertices with $\sum_{i=1}^{i=n}d_i=2m$. Let $\mathcal{H}_D$ be the set of all graphs which have degree distribution $D$.

Now suppose $\mathbf{G}$ is an Erdős–Rényi random graph on $n$ vertices with edge probability $p$. If $H \in \mathcal{H}_D$, then $$\mathbb{P}(\mathbf{G}=H)=p^m(1-p)^{{n\choose{2}}-m}$$ since all graphs in $\mathcal{H}_D$ have $m$ edges. Therefore, $$\mathbb{P}(\mathbf{G} \in \mathcal{H}_D)= \sum_{H \in \mathcal{H}_D} \mathbb{P}(\mathbf{G}=H)$$ $$\mathbb{P}(\mathbf{G} \in \mathcal{H}_D) = |\mathcal{H}_D|\times p^m(1-p)^{{n\choose{2}}-m}$$ As far as I know, there is no closed form for $|\mathcal{H}_D|$ -- although there might be one if we allow for self-edges (in which case the $n\choose 2$ will be replaced by $n^2$).

Lyuba B.
  • 541
  • Thanks, but I'm not seeing the relation between your answer and the joint distribution of dependent Binomial random variables (http://stats.stackexchange.com/questions/231688/joint-distribution-of-dependent-binomial-random-variables) – Toney Shields Aug 25 '16 at 18:12
  • 1
    @ToneyShields huh? In the labelled case, each $d_i$ (the number of edges of vertex $i$) is binomial. So, the joint distribution of $(d_1,d_2,\ldots,d_n)$ (which this answer is considering) is indeed a joint distribution of dependent Binomial random variables -- even the one you were asking about. – Juho Kokkala Sep 04 '16 at 05:55
  • @JuhoKokkala I'm sorry, I'm confused, I don't know what answer is correct, could you please explain it more? – Toney Shields Sep 04 '16 at 11:33
  • 1
    It's hard to explain since it is unclear what you are confused about. Based on this and the previous question, it sounds a bit like you are expecting "joint distribution of dependent Binomial random variables" would be something that you easily get by plugging things into "the formula for joint distribution of dependent Binomial random variables". But that kind of formula does not exist as how to get the joint probabilities depends on how the model is specified... – Juho Kokkala Sep 04 '16 at 11:41
  • 1
    Do you understand how to get, say, the joint distribution of degrees of an ER graph with $3$ vertices and $p=0.3$ by just manually considering all possible graphs? – Juho Kokkala Sep 04 '16 at 11:45
  • @JuhoKokkala No sir, I don't – Toney Shields Sep 05 '16 at 00:31
  • 1
    @ToneyShields Then I suspect the issue is about knowing definitions -- what do you understand 'joint distribution' to mean? – Juho Kokkala Sep 05 '16 at 05:13
  • @JuhoKokkala Suppose we have two random variables $X$ and $Y$ that can take the values, let's say, from $1$ to $4$. The joint distribution $f(X,Y)$ is the distribution that determins the probabilty of $X$ and $Y$ taking a set of values, for example: $f(X=1,Y=2)$ determins the probability of $X=1$ and $Y=2$. – Toney Shields Sep 05 '16 at 11:17
  • 1
    @ToneyShields Correct (so it seems I was wrong and the issue is not with the definition of joint distribution). But that probability is what this answer is considering - the probability that the vector of degrees is some $D=(d_1,\ldots,d_n)$. And in the $3$-vertex case, I don't know which part you have trouble with -- to find, say, $f(d_1=2,d_2=1,d_3=1)$ just go over all (if any) graphs that produce those degrees and sum the probabilities. – Juho Kokkala Sep 05 '16 at 14:37
  • @JuhoKokkala If I had to work on a particular graph, calculating the joint distribution will be easy, but I'm looking for the closed formula (if it exists) of that joint distribution for any random Erdős–Rényi graph (with $n$ vertices). – Toney Shields Sep 05 '16 at 15:13
  • Let us continue this discussion in chat. – Juho Kokkala Sep 05 '16 at 18:12