The fundamental insight of the small-world structure, proposed by Watts and Strogatz, is that networks can possess both high clustering coefficients and low path lengths, making them simultaneously efficient on both local and global scales (Watts and Strogatz, 1998). Watts and Strogatz discovered that a regular lattice retained high clustering coefficients but drastically reduced average path lengths if a few edges of the lattice were randomly “re-wired”, creating short-cuts to distant portions of the network. This structure has been found in numerous real-world networks (including neural and MRI networks (Eguiluz et al., 2005; Humphries et al., 2006; Watts and Strogatz, 1998)), and comparisons between the “small-worldness” of networks can be made by normalizing observed small-world measures to those found in regular and random graphs with similar numbers of nodes and edges.
