watts_strogatz_graph(n, k, p, seed=None)[source]¶
Returns a Watts–Strogatz small-world graph.
- n (int) – The number of nodes
- k (int) – Each node is joined with its
knearest neighbors in a ring topology.
- p (float) – The probability of rewiring each edge
- seed (integer, random_state, or None (default)) – Indicator of random number generation state. See Randomness.
First create a ring over \(n\) nodes . Then each node in the ring is joined to its \(k\) nearest neighbors (or \(k - 1\) neighbors if \(k\) is odd). Then shortcuts are created by replacing some edges as follows: for each edge \((u, v)\) in the underlying “\(n\)-ring with \(k\) nearest neighbors” with probability \(p\) replace it with a new edge \((u, w)\) with uniformly random choice of existing node \(w\).
In contrast with
newman_watts_strogatz_graph(), the random rewiring does not increase the number of edges. The rewired graph is not guaranteed to be connected as in
 Duncan J. Watts and Steven H. Strogatz, Collective dynamics of small-world networks, Nature, 393, pp. 440–442, 1998.