networkx.generators.random_graphs.connected_watts_strogatz_graph¶

connected_watts_strogatz_graph
(n, k, p, tries=100, seed=None)[source]¶ Returns a connected Watts–Strogatz smallworld graph.
Attempts to generate a connected graph by repeated generation of Watts–Strogatz smallworld graphs. An exception is raised if the maximum number of tries is exceeded.
 Parameters
n (int) – The number of nodes
k (int) – Each node is joined with its
k
nearest neighbors in a ring topology.p (float) – The probability of rewiring each edge
tries (int) – Number of attempts to generate a connected graph.
seed (integer, random_state, or None (default)) – Indicator of random number generation state. See Randomness.
Notes
First create a ring over \(n\) nodes 1. 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\). The entire process is repeated until a connected graph results.
References
 1
Duncan J. Watts and Steven H. Strogatz, Collective dynamics of smallworld networks, Nature, 393, pp. 440–442, 1998.