Uncovering the hidden structure of small-world networks

Abstract

The small-world (SW) network model introduced by Watts and Strogatz has significantly influenced the study of complex systems, spurring the development of network science as an interdisciplinary field. The Newman-Watts model is widely applied to analyze SW networks by adding several randomly placed shortcuts to a regular lattice. We meticulously examine related previous works and conclude that the scaling of various pertinent quantities lacks convincing evidence. We demonstrate that the SW property primarily stems from the existence of clusters of nodes linked by shortcuts rather than just the mean number of shortcuts. Introducing the mean degree of clusters linked by shortcuts as a new key parameter resolves the scaling ambiguity, yielding a more precise characterization of the network. Our findings provide a new framework for analyzing SW networks, highlighting the significance of considering emergent structures in complex systems. We also develop a phase diagram of the crossover transition from the small to the large world, offering profound insights into the nature of complex networks and highlighting the power of emergence in shaping their behavior.