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?


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.


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.