A “small world” is described as a network in which closely intra-connected groups are connected with each other through inter-group shortcuts. In Collective Dynamics of Small-World Networks Watts and Strogatz introduce a small-world model with short average path length and high clustering coefficient.
The W&S Model is built by rewiring a regular lattice to create long-range edges or shortcuts in the network. The model takes a single parameter “p” and interpolates between a regular lattice and a random network as “p” varies according to the following algorithm:
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).
2. Randomize: Now we randomly add long-range connections through the following procedure:
a. Visit each node.
b. At a given node, visit each link.
c. 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, likely to connect distant nodes 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 network’s diameter, even when very few such links are introduced.
To read the documentation about the program, click on the following link:
