Watts and Strogatz model

From Wikipedia, the free encyclopedia

[edit] Highlights

• A Small World is a world where closely intra-connected groups are connected with each other through inter-group shortcuts.
• Real networks are too well clustered to be described by the ER model.
• The Watts and Strogatz (WS) model introduces a small world structure with short average path length and high clustering coefficient.
• The WS model is built by rewiring a regular lattice to create long-range edges or shortcuts in the network.
• The WS model fails to explain the existence of hubs in networks and does not incorporate growth of a network.

[edit] The small world

In 1969 Jeffrey Travers of Harvard University and Stanley Milgram of the City University of New York, reported a study on social networks better known as Milgram's experiment(In fact, the experiment referenced by this link is not the same experiment of mails by Stanley Milgram, this it is "Milgram's experiment"). They attempted to measure the average path length of the social network. The short path length measured implied, albeit inconclusively, that our world is a small world.

The term "Small World", commonly used to describe networks, is derived from the sociological Small World Phenomenon,^[1][2] popularly known as the "Six Degrees of Separation."^[3]

A network is said to be a small world network if any two arbitrary nodes are connected by a small number of intermediate links (i.e. The network has an average path length much smaller than the number of nodes in the network).

Many real world networks have a very short average path length even if the networks themselves are be relatively large. Any two persons in the world can be connected through four or five acquaintances, sometimes fewer^[4][5]. Any two computers on the Internet can be connected through a small number of routers. We are always a few clicks away from any website that we might want. Movie actors can be connected through an average of 4.54 co-actors^[6].

[edit] Our "not-so-random" world

In 1960 two Hungarian mathematicians, Pál Erdős and Alfréd Rényi, explored the theory of random graphs^[7]. This network, also known as the Erdos-Renyi model (ER model), has a small world structure and, in fact, had a shorter average path length than most real networks. However, this model fails to account for the clustering seen in many real networks, which often have relatively large clustering coefficients.

In an attempt to build a network with a large clustering coefficient which retains the small world property or a short average path length, Duncan J. Watts and Steven H. Strogatz of Cornell University, proposed a model built by randomly rewiring a regular lattice^[8]. This Watts and Strogatz (WS) model, displays the high clustering coefficient common to regular lattices as well as the small world property seen in the ER model.

[edit] Rewiring a regular network — the Watts and Strogatz model

The Watts and Strogatz (WS) model interpolates between a regular lattice and a random network. The model takes a single parameter p and produces a network according to the following algorithm^[9].

Fig.[1]. The Watts and Strogatz model interpolates between a regular lattice and a random network as p varies. For p = 0 the lattice retains it structure. As p increases the lattice becomes increasingly disordered until at p = 1 we have a random network.^[8]

1. Start with order : We start with a regular ring lattice in which there are N nodes each connected with K of its neighbors (K / 2 on each side). In order to have a sparse but well connected network at all times, we will consider .
2. Randomize : Now we randomly add long-range connections through the following procedure.
   1. Visit each node.
   2. At a given node, visit each link.
   3. Rewire this connection by moving it to another randomly selected node (uniform probability while avoiding self-connection and link duplication) with probability p.

This process introduces non-lattice edges which are likely to connect nodes that were distant in the original lattice. By varying p we can interpolate between a regular lattice (p = 0) and a random network (p = 1).

The underlying lattice structure of the WS model produces a locally clustered network, and the long-range links introduced by the randomization procedure dramatically reduce the diameter of the network, even when very few such links are introduced.

[edit] Properties of the WS model

Fig.[2]. Average path length l and clustering coefficient C for the Watts and Strogatz model. The plotted values are given as fractions of the initial values (l(0) and C(0)). We see the rapid decrease in l for small values of p while C retains a high value, which only decreases for relatively large p to that for a random network. Note the logarithmic scale, this low l high C state persists for several orders of magnitude of p.^[8]

The two most important properties of the WS Model are short average path length and high clustering coefficient. Its degree distribution is similar to that of a random network but not exactly [Poisson distribution|Poisson]] in nature.

Average path length

For the ring lattice in Fig.[1] the average path length, and hence the average path length scales linearly with the sysytem size. In the limiting case of the WS Model converges to a random graph for which . However, as seen in Fig.[2] in the intermediate region 0 < p < 1 the average path length falls very rapidly to its value for random networks at quite small rewiring probabilities p.

Clustering coefficient

For the ring lattice the clustering coefficient, C(0) = 3 / 4 which is independent of the system size. In the limiting case of the clustering coefficient attains the value for random networks, 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, as seen in Fig.[2] and only falls at relatively high rewiring probability p.

If we use the Barrat and Weigt^[10] measure for clustering C'(p) defined as the fraction between the average number of edges between the neighbors of a node and the average number of possible edges between these neighbors or alternatively,

then we get

Fig.[3]. The degree distribution for the Watts and Strogatz model for different values of p from a numerical simulation. This graph has N = 1000 and K = 6. We see that < k > = K. The orange dots represent the degree distribution for a random network with the same parameters.^[10]

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 p = 1 the degree distribution is Poisson as it should be for a random network. The degree distribution for 0 > p > 1 can be written as^[10],

where k_i is the number of edges that the i^th node has or its degree. Here , 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.

We see that in the Watts and Strogatz model, for a large range of p, we have both a high clustering coefficient and a short average path length, just as we see in many real world networks.

[edit] Real networks with the small world property

The Watts and Strogatz model reproduces the clustering seen in real world network while preserving the small world property, something which the ER random networks fail to do. In Table[1] we show some real examples of small world networks and compare their path lengths and clustering coefficients to those of equivalent ER random networks.

All four show a longer average path length than random and show a higher clustering coefficient that random. The WS model is a better match than the ER model for these real networks.

[edit] Looking beyond

Despite producing a network that is both small-world and clustered, the Watts and Strogatz Model fails to be a good model for real networks. The WS Model is quite homogenous in degree, most nodes have about the same degree. Real networks such as the world wide web and metabolic networks are inhomogenous. There exist a significant number of nodes of very high degree called hubs. The WS model starts off with a fixed number of nodes thus cannot incorporate growth of the network. This lack is a serious disadvantage in modeling real networks, some of which grow quite rapidly.

Later models, notably the BA model^[11], were created to address these issues.

[edit] See also

• Small-world networks
• Social networks

[edit] References

1. ^ Milgram, S. The small world problem. Psychol. Today 2, 60–67 (1967).
2. ^ Kochen, M. (ed.) The Small World (Ablex, Norwood, NJ, 1989).
3. ^ Guare, J. Six Degrees of Separation: A Play (Vintage Books, New York, 1990).
4. ^ Travers, J. and Milgram, S.,1969. Sociometry 32, 425
5. ^ Karinthy, F., 1929. Chain-Links in Everything is Different, Budapest
6. ^ Barabási, A.-L., and R. Albert, 1999, Science 286, 509.
7. ^ Erdős, P., and A. Rényi, 1960, Publ. Math. Inst. Hung. Acad. Sci. 5, 17.
8. ^ ^{a b c d} Watts, D. J., and S. H. Strogatz, 1998, Nature (London) 393, 440.
9. ^ Barabási, A.-L., and R. Albert, 2002, Rev. Mod. Phys. 74, 47.
10. ^ ^{a b c} Barrat, A., and M. Weigt, 2000, Eur. Phys. J. B 13, 547.
11. ^ Barabási, A.-L., and R. Albert, 1999, Science 286, 509.