- Watts and Strogatz model
The
Watts and Strogatz model is a random graph generation model that produces graphs with small-world properties, including shortaverage path length s and high clustering. It was proposed byDuncan J. Watts andSteven Strogatz in their joint 1998 Nature paper.cite journal
author = Watts, D.J.
coauthors = Strogatz, S.H.
year = 1998
title = Collective dynamics of 'small-world' networks.
journal = Nature
volume = 393
issue = 6684
pages = 409–10
url = http://www.ncbi.nlm.nih.gov/sites/entrez?db=pubmed&uid=9623998&cmd=showdetailview&indexed=google
accessdate = 2008-02-25
doi = 10.1038/30918] The model also became known as the (Watts) "beta" model after Watts used eta to formulate it in his popular science book "".Rationale for the model
The formal study of
random graph s dates back to the work ofPaul Erdős andAlfréd Rényi cite journal
author = Erdos, P.
year = 1960
title = Publications Mathematicae 6, 290 (1959); P. Erdos, A. Renyi
journal = Publ. Math. Inst. Hung. Acad. Sci
volume = 5
pages = 17] . The graphs they considered, now known as the classical or Erdős–Rényi (ER) graphs, offer a simple and powerful model with many applications.Despite their simplicity and power, the ER graphs fail to explain two important properties observed in real-world networks:
# By assuming a constant and independent probability of two nodes being connected, they do not account for local clustering andtriadic closure s. This fact is formally expressed by the ER graphs having a lowclustering coefficient .
# They do not account for the formation of hubs. Formally, the degree distribution of ER graphs converges to aPoisson distribution , rather than apower law observed in most 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.Algorithm
Given the desired number of nodes N, the mean degree K (assumed to be an even integer), and a special parameter eta, satisfying 0 le eta le 1 and Ngg K gg ln(N)gg 1, the model constructs an undirected graph with N nodes and frac{NK}{2} edges in the following way:
# Construct a regular ring lattice, a graph with N nodes each connected to K neighbors, K/2 on each side. That is, if the nodes are labeled n_0 ... n_{N-1}, there is an edge n_i, n_j) if and only if quad |i - j| equiv k pmod N for some k| in left(1, frac{K}{2} ight)
# For every node n_i=n_0 ... n_{N-1} take every edge n_i, n_j) with i < j, and rewire it with probability eta. Rewiring is done by replacing n_i, n_j) with n_i, n_k) where k is chosen with uniform probability from all possible values that avoid loops (k e i) and link duplication (there is no edge n_i, n_{k'}) with k' = k at this point in the algorithm).Properties
The underlying lattice structure of the model produces a locally clustered network, and the random links dramatically reduce the
average path length s. The algorithm introduces about etafrac{NK}{2} non-lattice edges. Varying eta allows to interpolate between a regular lattice (eta=0) and a random graph (eta=1) approaching the Erdős–Rényi random graph G(n, p) with n=N and p = frac{NK}{2{N choose 2.The three properties of interest are the
average path length , theclustering coefficient , and thedegree distribution .Average path length
For a ring lattice the average path length is l(0)=N/2Kgg 1 and scales linearly with the system size. In the limiting case of eta ightarrow 1 the graph converges to a classical random graph with l(1)=frac{ln{N{ln{K. However, in the intermediate region 0<eta<1 the average path length falls very rapidly with increasing eta, quicklyapproaching 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 eta ightarrow 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 eta.
C^'(eta)equivfrac{3 imes mbox{number of triangles{mbox{number of connected triples:then we get C'(eta)sim C(0)left(1-eta ight)^3.
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 eta ightarrow 1 it isPoisson distribution , as with classical graphs. The degree distribution for 0<eta<1 can be written as,:P(k) = sum_{n=0}^{fleft(k,K ight)} C^n_{K/2} left(1-eta ight)^{n} eta^{K/2-n} frac{(eta K/2)^{k-K/2-n{left(k-K/2-n ight)!} e^{-eta K/2}
where k_i is the number of edges that the i^{th} node has or its degree. Here kgeq K/2, and f(k,K)=min(k-K/2,K/2). 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 graphs that are
homogeneous in degree. In contrast, real networks are oftenscale-free networks inhomogeneous in degree, having hubs and a scale-free degree distribution. Such networks are better described by thepreferential attachment family of models, such as the Barabási–Albert (BA) model.The model also implies a fixed number of nodes and thus cannot be used to model network growth.
ee also
*
Small-world networks
*Social networks References
Wikimedia Foundation. 2010.