Question

Show that in a regular lattice for small-world model, local clustering coefficient for any node is 3(c−2) 4(c−1) , where c is the average degree.

Answer 1

In order to calculate the clustering coefficient we need to calculate the number of triangles and connected triples after the addition of the shortcuts
Number of triangles:

1. The triangles of the original circle are not changed: (1/4)nc(c-1)
2. New triangles can be created
     1. n general nodes that have distance on the circle between (1/2)c+1 up to c are connected through 2-hop path,This             number increases linear with the size of the network
     2. If a shortcut connects them then we have a new triangle
     3. The probability they are connected through a shortcut is ((1/2)*n*c*p)/((1/2)*n*(n-1)) ~ c*p/n
     4. Hence, the number of triangles that are completed through the shortcuts is proportional to n*cp/n=cp
Number of connected triples:

1.All connected triples of the original circle are still there: (1/2)nc(c-1)
Every shortcut creates new connected triples
At each end of the shortcut edge there are c edges that can form a triple. Hence, the total number of triples created due to a single shortcut are: (1/2)ncp*2*c=nc2p
2. Pairs of shortcuts attached to a vertex can create connected triples as well ,If a vertex has m attached shortcuts there are (1/2)m(m-1) triples centered at this node
    The number of shortcuts a node received is Poisson distributed with mean cp ,Hence, the expected number of connected triples centered at a given vertex is (1/2)c^2p^2

Combining all above together the clustering coefficient for the small-world network model we consider is: