Watts and Strogatz, and others, often describe “small world” properties with two metrics: the average clustering coefficient and average path length of a graph. The clustering coefficient measures how well connected the neighbors of a node are to one another. The average path length measures the average minimum number of steps needed to go between any two nodes. Lattices, optimized for local processes, have high average clustering coefficients but long average path lengths. Conversely, random graphs, which have no preference for short-range connections, have low average clustering coefficients and short average path lengths, making them well suited for communication between distant nodes. One of Watts & Strogatz's key insights was that by randomly rewiring a relatively small number of connections in a lattice graph (i.e., introducing a few long-range connections), a graph could retain its high average clustering coefficient, but dramatically reduce its average path length, thereby enabling efficient short- and long-range processes. It is this hybrid graph topology (i.e., high clustering coefficients and short path lengths) that matches the observed “small world” networks in many complex systems [47].
