**The small-world model of Watts and Strogatz**

In order to model the real-world
networks, we need to find a way of generating graphs which have both the
clustering and small-world properties. As we know, random graphs show the
small-world effect, possessing average vertex-to-vertex distances which increase
only logarithmically with the total number N of vertices, but they do not show
clustering—the property that two neighbors of a vertex will often also be
neighbors of one another.

The

**Watts-Strogatz model**is a random graph generation model that produces graphs with small-world properties, including short average path lengths and high clustering. It was proposed by Duncan J. Watts and Steven Strogatz in their joint 1998 Nature paper. The model also became known as the (Watts)*beta*model after Watts used*B*to formulate it in his popular science book*Six Degrees*.
Though

*Erdős–Rényi (ER)*graphs, offer a simple and powerful model with many applications. However the**ER**graphs do not have two important properties observed in many real-world networks:
1. They do not generate local clustering
and triadic closures. Instead because they have a constant, random, and
independent probability of two nodes being connected, ER graphs have a
low clustering coefficient.

2. They do not account for the formation of hubs.
Formally, the degree distribution of ER graphs converges to
a Poisson distribution, rather than a power law observed in many
real-world, scale-free networks.

###
The Watts and Strogatz model was designed as the simplest possible model that addresses the first of the two limitations. It accounts for clustering while retaining the short average path lengths of the ER model. It does so by interpolating between an ER graph and a regular ring lattice. Consequently, the model is able to at least partially explain the "small-world" phenomena in a variety of networks, such as the power grid, neural network of C. elegans, and a network of movie actors.

**Algorithm:**
Given the desired
number of nodes N, the mean degree K (assumed to be an even integer), and a special
parameter, satisfying and

**Algorithm:**

- Construct a regular ring lattice, a graph with N nodes each connected to K neighbors, K/2 on each side.
- For every node take every edge (ni,nj) with i<j, and rewire it with probability.Rewiring is done by replacing (ni,nj) with (ni,nk) where K is chosen with uniform probability from all possible values that avoid loops (k!=i) and link duplication (there is no edge (ni,nk') with K'=K at this point in the algorithm).

**Average path length:**

For a ring lattice the
average path length is l(0)=

*N*/2*K*>> 1 and scales linearly with the system size. In the limiting case of*B*-->1 the graph converges to a classical random graph with l(1)=ln N/ln K. However, in the intermediate region 0<*B*<1 the average path length falls very rapidly with increasing*B*, quickly approaching its limiting value.**Clustering coefficient:**

For the ring lattice
the clustering coefficient is C(0) = 3/4 which
is independent of the system size. In the limiting case of

*B*-->1 the clustering coefficient attains the value for classical random graphs, C(1) =*K/N*and is thus inversely proportional to the system size. In the intermediate region the clustering coefficient remains quite close to its value for the regular lattice, and only falls at relatively high*B*. This results in a region where the average path length falls rapidly, but the clustering coefficient does not, explaining the "small-world" phenomenon.**Degree distribution:**

The degree distribution in the case
of the ring lattice is just a Dirac delta function centered at

*K*. In the limiting case of*B-->1*it is Poisson distribution, as with classical graphs. The degree distribution for 0*<B<1*can be written as,
where

*f(k,K) = min(k-K/2,K/2)*and the shape of the degree distribution is similar to that of a random graph and has a pronounced peak at*k = K**and decays exponentially for large |**k-K*|. The topology of the network is relatively homogeneous, and all nodes have more or less the same degree.**Limitations:**

The major limitation of the model
is that it produces an unrealistic degree distribution. In contrast,
real networks are often scale-free networks inhomogeneous in degree,
having hubs and a scale-free degree distribution. Such networks are better
described in that respect by the preferential attachment family of
models, such as the Barabási–Albert (BA) model.

Hello, I was wondering if you know how to construct the same closed-ring lattice you show above using R. Specifically, with wsrg in the statnet package? Thanks

ReplyDelete