Does the joint distribution of the degrees of an Erdős–Rényi graph have a closed form?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ 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. $\endgroup$– Alex R.Aug 25, 2016 at 16:25
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
11
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$).
-
1$\begingroup$ @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. $\endgroup$ Sep 4, 2016 at 5:55
-
1$\begingroup$ 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... $\endgroup$ Sep 4, 2016 at 11:41
-
1$\begingroup$ 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? $\endgroup$ Sep 4, 2016 at 11:45
-
1$\begingroup$ @ToneyShields Then I suspect the issue is about knowing definitions -- what do you understand 'joint distribution' to mean? $\endgroup$ Sep 5, 2016 at 5:13
-
1$\begingroup$ @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. $\endgroup$ Sep 5, 2016 at 14:37