Watts–Strogatz model - Wikipedia

Abstraction: Random graph model generating small-world network properties via rewiring

Key points:

• Proposed by Duncan Watts and Steven Strogatz in Nature 1998; addresses high clustering + short path lengths simultaneously
• Algorithm: start with regular ring lattice, rewire each edge with probability β; β=0 is lattice, β=1 approaches Erdos-Renyi
• Produces short average path lengths (like ER random graphs) AND high clustering coefficient (unlike ER graphs)
• Major limitation: generates homogeneous degree distribution, not the power-law (scale-free) distribution seen in real networks
• Erdos-Renyi graphs lack both clustering and hubs; Barabasi-Albert adds hubs but lacks clustering; Watts-Strogatz fills the clustering gap
• Cannot model network growth since node count is fixed

Connections: Duncan Watts · Steven Strogatz · Small World Networks · Graph Models · Network Science

Source: http://en.wikipedia.org/wiki/Watts_and_Strogatz_Model