Reading the book Networks, by Mark Newman I found this exercise and I have some question about it:
"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.
a) Show that the mean degree of a vertex is $2c$.
b) 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} $$
c) Show that the clustering coefficient is $C = \frac{1}{2c+1}$, where C is definite as three number of triangles over the number of connected triples.
d)Show that when there is a giant component in the network its expected size $S$ as a fraction of network size satisfies $S=1-e^{-cS(2-S)}$.
My solution:
a) A random chosen vertex could form a triangle in ${n-1 \choose 2}$ ways each with probability $p$, for for which two links are added, and so $<k>=2{n-1 \choose 2}p=2c$.
Actually I'm making same approximation here, because I'm double counting some links. Is this approximation justified in the limit of large $n$?.
b) $p_k=0$ for $k$ odd because for each triangles we add two links (again this is not completely true). Setting $k=2d$ we have that $d$ is equal to the number of triangles and so we can write:
$$
p_k=p_{2d}={{n-1 \choose 2} \choose d}p^d(1-p)^{{n-1 \choose 2}-d}
$$
and this can be approximated with the Poisson distribution
$$
p_{2d} = e^{-<d>}\frac{<d>^{d}}{d!}
$$
and recalling that $d=k/2$ and so $<d>=c$ we arrive at the request solution.
d) Let $u=1-S$ the fraction of point that are not in the giant component. The probability that a vertex $i$ is not linked to the giant component $S$ via vertex $j$ is the sum of the probability of not be connected at all with vertex $j$ and the probability that is connected but the triangles that forms, say $ijk$ is not in $S$. The first probability is just $(1-p)^{n-2}$ and the second is $1-(1-pu^2)^{n-2}$ because both $j$ and $k$ should not be in $S$ e this happens with probability $u^2$. Thus the probability of not being in the giant component via any other vertex satisfy:
$$
u = \left [(1-p)^{n-2}+1-(1-pu^2)^{n-2}\right]^{n-1}
$$
Taking the log and expanding the logarithm in the limit of large $n$ at first term, we can write:
$$
\log{u} \approx (n-1)\left [(1-p)^{n-2}-(1-pu^2)^{n-2}\right] \approx (n-1)(n-2)p(u^2-1).
$$
Using the definition of $p=\frac{2c}{(n-1)(n-2)}$ and writing u = 1 -S we are at the formale in the exercise text.
c) Here is the problems. The number of triangles in the networks should be ${n\choose 3}p=\frac{nc}{3}$. The number of connected triples is the number of triangles (counted only one and not 3 times) plus the open connected triples. Because each vertex has a mean degree equal to $2c$ it means that it has $c$ triangles and if we make again the same approximation as before these triangles do not share links and so for each vertex we have $c$ open triples. And so:
$$
C = \frac{nc}{\frac{nc}{3}+nc}=\frac{3}{4}
$$
which is not the correct answer and more importantly it does not deepen on $c$, i.e. on the mean degree of the networks.
Where are my mistakes?
Thanks
Best Answer
Possibile solution
As before the number of triangles in the network is $\frac{nc}{3}$ and the mean number of triangles for each vertex fo mean degree $2c$ is again equal to $c$ (using the usual approximation). Now the number of possible triples starting from a typical vertex is roughly $(2c)^2$, and so the number of connected triples in the whole network is $\frac{n(2c)^2}{2}=2nc^2$ because each triples is counted twice. If we assume (but probably non correctly) that these triples are the open ones, we can conclude that the number of connected triples is $nc+2nc^2$ and thus we can conclude that: $$ C = \frac{3\frac{nc}{3}}{nc+2nc^2}=\frac{1}{1+2c} $$ as we wanted.