In a seminal 1998 paper, Watts and Strogatz noted that the topology of many complex systems can be described as “small world”, a type of graph architecture that efficiently permits both local and distributed processing. Graphs with a regular, lattice-like structure have abundant short-range connections, but no long-range connections. Local interactions are thus efficient, but distributed processes involving distant nodes require the traversal of many intermediate connections. Conversely, completely randomly connected graphs are fairly efficient at transferring distant or long-range signals across a network, but they are poor at local, short-range information transfer.
