We can make a simple random graph model of a network with clustering or transitivity as follows. We take $n$ vertices and go through each distinct trio of three vertices, of which there are $n \choose 3 $, and with independent probability $p$ we connect the members of the trio together using three edges to form a triangle, where $p=c/ {n-1 \choose 2}$ with $c$ a constant.
Show that the degree distribution is
$$p_k = \begin{cases} e^{-c}c^{k/2}/(k/2)! &\mbox{if } k \text{ is even} \\ 0 & \mbox{if } k \text{ is odd} \end{cases} $$ (Networks, An Introduction M.E.J Newman- exercise 12.5)

Degree distribution in this question clearly follows Poison distribution. Using binomial distribution $$ p_k={n-1 \choose k} [c/ {n-1 \choose 2}]^k [1-c/ {n-1 \choose 2}]^{n-k-1} $$ But I couldn't prove the equation. Any help is appreciated.

  • $\begingroup$ Please make only substantial edits, bumping for irrelevant edits is considered noise. $\endgroup$ – Daniel Fischer Jun 28 '18 at 8:39

Your Answer

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

Browse other questions tagged or ask your own question.