Overview
The Watts-Strogatz model begins with nodes connected to nearby neighbors on a ring and randomly rewires edges. This preserves local clustering while introducing shortcuts that reduce path lengths.
CoreSource checked
Watts-Strogatz Model
Generates small-world networks by rewiring a regular ring lattice with some probability.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Randomness & Sampling
- Difficulty
- Intermediate
- Family
- Random Graphs
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
Core Concepts
small-world graph generationrandom graphsrandom samplingrandomness sampling
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O((V + E) log V)
Worst
O(V^2 + E)
Space
O(V + E)
When to Use
- Use when clustering and short average paths are the intended graph properties.
- Use as a baseline between regular lattices and random graphs.
When Not to Use
- Avoid when hub-heavy degree distributions are the main requirement.
- Avoid when the graph should be generated from independent edge probabilities.
What It Does
- Builds a regular ring lattice
- Rewires edges with a chosen probability
- Produces a graph with clustering and shortcut paths
Use Cases
- Synthetic small-world network experiments
- Testing graph algorithms on clustered graphs
- Teaching the tradeoff between local structure and random shortcuts
Inputs
- Vertex count n and model parameters (edge probability p, attachment count m, or degree sequence)
- PRNG seed
Outputs
- Sampled graph adjacency list G = (V, E)
- Realized degree distribution and connectivity structure
Pseudocode
- 1.Create a ring lattice connecting each node to k nearest neighbors
- 2.For each eligible edge
- 3.With probability p, choose a new valid target
- 4.Replace the edge while avoiding duplicates and self-loops
- 5.Return the rewired graph
Canonical Example
- Input
- n = 10, each node connected to 2 neighbors on each side, rewiring p = 0.1
- Output
- a mostly local ring graph with a few random shortcuts
- Explanation
- Most local edges remain, while some rewired edges shorten paths across the graph.
Implementation Notes
- Require an even neighbor count for the initial ring lattice.
- Use deterministic seeding for reproducible graph experiments.
- Track clustering and path-length metrics to verify generated structure.
Common Pitfalls
- Rewiring self-loops or duplicate edges changes the model.
- Choosing k or rewiring probability without considering n can destroy the intended structure.
- Assuming all small-world networks follow this simple generative process.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow rewiring a ring lattice to add shortcuts while preserving local structure on a small small-world graph generation example.
Step 1 of 5: Create a ring lattice connecting each node to k nearest neighbors
randomness-sampling-mechanismNotes
The model is controlled by both local degree and rewiring probability.
Sources (1)
What each reference supports for this entry.
Collective Dynamics of Small-World Networks
PaperOriginal reference for Watts-Strogatz rewiring and small-world network generation.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toBarabasi-Albert Model
Randomness & Sampling · Core
Watts-Strogatz models clustering and shortcuts, while Barabasi-Albert models preferential attachment.
Compare with thisRelationships
View full relationship pageAlternative toErdos-Renyi Graph Generation
Watts-Strogatz starts from local structure, while Erdos-Renyi samples independent edges.
Alternative toBarabasi-Albert Model
Watts-Strogatz models clustering and shortcuts, while Barabasi-Albert models preferential attachment.
Related Algorithms
Tags
Randomness & SamplingRandomnessGraph