Smallworld

Small-world networks are a class of graphs in which most nodes are not direct neighbors, yet the path between most pairs of nodes is surprisingly short. The concept gained prominence after Watts and Strogatz proposed a model in 1998 showing that simple local connectivity combined with a few random long-range links can produce networks with high clustering and short average path lengths, characteristics observed in many real systems. The small-world property helps explain how information, influence, or infections can spread rapidly through largely local networks.

Two main characteristics define small-world networks: a high clustering coefficient relative to equivalent random graphs, and an average shortest path length comparable to that of random graphs with the same size and degree distribution. The Watts–Strogatz model starts with a regular lattice and rewires a fraction of edges at random; as this fraction increases, the network transitions from a regular, highly clustered structure to a more random one, passing through a regime with small-world properties.

Real-world examples include social networks, collaboration networks, neural and metabolic networks, and various technological networks such as the Internet and some power grids. The small-world framework helps explain rapid diffusion of information and contagions and informs strategies in epidemiology, marketing, and network design. It also raises considerations about robustness: small-world networks can be surprisingly resilient to random failures but may be sensitive to targeted disruptions if highly connected nodes are involved.

Notes in the field distinguish small-world networks from purely random or scale-free networks, though real systems often exhibit a combination of features. The concept is also used outside science to describe certain games and virtual environments named after the idea of a world with many tightly knit connections.

Small World is also the title of a popular board game in which players control fantasy races to conquer a map.