The small-world problem (discussed in Chapter 8, Social Networks and Going Viral) asks how it is possible for distant people to be connected by short paths, even when everyone's connections are local (Travers & Milgram, 1967). Duncan Watts and Steven Strogatz (1998) developed a class of networks to explain this behavior. The networks begin as k-rings: nodes placed around a circle, with each node connected to its nearest k neighbors. Then, with probability p, each node's edges are moved to a randomly selected other node. These rewirings create shortcuts across the network. Even a small number of shortcuts greatly reduces the distances between nodes in the network, resolving the small-world problem.
The following code uses the NetworkX function watts_strogatz_graph() to generate Watts-Strogatz small-world networks with p=0, p=0.1, and...
