Figure 2.

Three basic network types in the model of Watts and Strogatz. The leftmost graph is a ring of 16 vertices (N = 16), where each vertex is connected to four neighbours (k = 4). This is an ordered graph which has a high clustering coefficient C and a long pathlength L. By choosing an edge at random, and reconnecting it to a randomly chosen vertex, graphs with increasingly random structure can be generated for increasing rewiring probability p. In the case of p = 1, the graph becomes completely random, and has a low clustering coefficient and a short pathlength. For small values of p so-called small-world networks arise, which combine the high clustering coefficient of ordered networks with the short pathlength of random networks.