# Clustering coefficient in a random graph model with transitivity

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 $$=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^{-}\frac{^{d}}{d!}$$ and recalling that $$d=k/2$$ and so $$=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

## 1 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.