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.

  • $\begingroup$ 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}$ :-) $\endgroup$ – YnkDK Nov 17 '15 at 13:41
  • $\begingroup$ Yes, see edit, it seems as if that is exactly what the authors did. $\endgroup$ – ckoe Nov 17 '15 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.