Given an undirected Graph with $n$ nodes. I want to create edges between two nodes with a probability $p$ so that every node has on average 2 edges. How do I calculate $p$?
I know that to calculate the average number of edges given $p$ I can calculate the sum over all $k$ of the binomial distribution. Is it possible to solve the binomial distribution for $p$ analytically? Or do I have to solve it numerically?!
$$\text{Pr}(X=k)={n\choose k}p^k(1-p)^{n-k}$$
Best Answer
I assume by "every node has on average 2 edges" means the expected degree of any vertex is $2$. Notice that the degree of a vertex $v$ is $\text{deg}(v)=\sum_{w \neq v} 1\{\{v,w\} \in G\}$, so $E[\text{deg}(v)] = \sum_{w \neq v} P(\{v,w\} \in G) = (n-1)p$. Indicator variables are extremely helpful for calculating expectations in random graphs!