Small-world network

A small-world network is a graph topology in which most nodes are not neighbors of one another, yet the average shortest path between any two nodes is small. This property — high local clustering combined with short global path lengths — was first formalized by Watts and Strogatz in 1998 as an interpolation between regular lattices and random graphs.

Small-world topology appears in neural networks, social networks, and power grids, suggesting that efficient information transmission and local redundancy are jointly optimized by selection pressures across vastly different systems. The small-world property is closely related to navigability, the ability to find short paths using only local information.