Cfrgtkky

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 $nchoose 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 ${nchoose 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

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{3frac{nc}{3}}{nc+2nc^2}=frac{1}{1+2c}
$$
as we wanted.