Watts And Strogatz Model

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.

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 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,Milgram, S. The small world problem. Psychol. Today 2, 60–67 (1967).Kochen, M. (ed.) The Small World (Ablex, Norwood, NJ, 1989). popularly known as the "Six Degrees of Separation."Guare, J. Six Degrees of Separation: A Play (Vintage Books, New York, 1990).

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 fewerTravers, J. and Milgram, S.,1969. Sociometry 32, 425Karinthy, F., 1929. Chain-Links in ''Everything is Different'', Budapest. 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-actorsBarabási, A.-L., and R. Albert, 1999, Science 286, 509..

OUR "NOT-SO-RANDOM" WORLD

In 1960 two Hungarian mathematicians, Pál Erdős and Alfréd Rényi , explored the theory of Random Graph sErdős, P., and A. Rényi, 1960, Publ. Math. Inst. Hung. Acad. Sci. 5, 17.. 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 Coefficient s.

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 latticeWatts, D. J., and S. H. Strogatz, 1998, Nature (London) 393,
440.. 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.

REWIRING A REGULAR NETWORK &MDASH; 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 algorithmBarabási, A.-L., and R. Albert, 2002, Rev. Mod. Phys. 74, 47..

.]]

# ''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

N\gg K \gg ln(N)\gg 1

.
# ''Randomize :'' Now we randomly add long-range connections through the following procedure.
## Visit each node.
## At a given node, visit each link.
## 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

prac{NK}{2}

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.

PROPERTIES OF THE WS MODEL

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

.]]

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 in nature.

:Average path length
:For the ring lattice in Fig. the average path length,

l(0)=N/2K\gg 1

and hence the average path length scales linearly with the sysytem size. In the limiting case of

p
ightarrow 1

the WS Model converges to a random graph for which

l(1)=rac{\ln{N}}{\ln{K}}

. However, as seen in Fig.[2 in the intermediate region

0 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

p
ightarrow 1

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. {Link without Title} and only falls at relatively high rewiring probability

p

.

:If we use the Barrat and WeigtBarrat, A., and M. Weigt, 2000, Eur. Phys. J. B 13, 547. 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,

C^'(p)\equivrac{3	imes \mbox{number of triangles}}{\mbox{number of connected triples}}

:then we get

C'(p)\sim C(0)\left(1-p
ight)^3

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

. The orange dots represent the degree distribution for a random network with the same parameters.]]

: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,

:

P(k)=\sum_{n=0}^{f\left(k,K
ight)}C^n_{K/2}\left(1-p
ight)^{n}p^{K/2-n}rac{(pK/2)^{k-K/2-n}}{\left(k-K/2-n
ight)!}e^{-pK/2}

{ Border

"1" cellpadding="5" cellspacing="0" align="center"

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

	CATEGORIES ABOUT WATTS AND STROGATZ MODEL

	networks

	social networks

	graph theory

Information About

Watts And Strogatz Model