# Expected degree of a vertex in a random network

In the paper "Finding and evaluating community structure in networks" by M. E. J. Newman and M. Girvan section 5a, when they construct random communities as a network, they state:

Edges were placed independently at random between vertex pairs with probability $p_{in}$ for an edge to fall between vertices in the same community and $p_{out}$ to fall between vertices in different communities. The values of $p_{in}$ and $p_{out}$ were chosen to make the expected degree of each vertex equal to 16

From https://math.stackexchange.com/a/388230/290950 I know that the expected number of edges in a random network are $C(n,2)p$, thus the expected degree must be $\frac{C(n,2)p}{n}$, and solving this for $p$ is not a problem. But is it then true that the I can state that $p = p_{in} + p_{out}$ for any $p_{out} < p_{in} < p$? And why?

I cant seem to get the argument correct.

If a vertex is inside a community of size $m$, the vertex has an expected number of $(m-1)p_{in}$ edges to other vertices in the same community. The expected number of "non-community" edges is $(n-m)p_{out}$. Thus, if the entire network has size $n$, then the expected degree is $$(m-1)p_{in}+(n-m)p_{out}.$$ Are all community sizes equal? In that case this gives the expected degree of the entire network.
In Fig 7, they seem to calculate some value for different values of $p_{out}$, so given $p_{out}$, you can calculate $p_{in}$, so that the expected degree still is 16.
• It is not clear from the paper, but since I am going to confirm another paper using this technique I am in total control of this. Your arguments makes sense. Although this still leaves me with one equation with two unknowns. $16 = (m-1)p_{in}+(n-m)p_{out}$. I could fix $p_{in}$ and then compute $p_{out}$ :-) – YnkDK Nov 17 '15 at 13:41