Abstract
We explore a new variant of Small-World Networks (SWNs), in which an additional parameter ($r$) sets the length scale over which shortcuts are uniformly distributed. When $r=0$ we have an ordered network, whereas $r=1$ corresponds to the original SWN model. These short-range SWNs have a similar degree distribution and scaling properties as the original SWN model. We observe the small-world phenomenon for $r \ll 1$ indicating that global shortcuts are not necessary for the small-world effect. For short-range SWNs, the average path length changes nonmonotonically with system size, whereas for the original SWN model it increases monotonically. We propose an expression for the average path length for short-range SWNs based on numerical simulations and analytical approximations.
Introduction
The classic Watts-Strogatz model of small-world networks (SWNs) revolutionized our understanding of complex systems by showing how a few "global" shortcuts can drastically reduce the average path length of a lattice. However, in many physical, biological, and social systems, shortcuts are not truly global. Connections are often constrained by spatial distance or community boundaries. This paper investigates whether the "global" nature of these links is a requirement for the small-world effect by introducing the Short-Ranged Small-World Network (SRSWN) model.
The SRSWN Model
The SRSWN model starts with a ring lattice of $L$ nodes. Shortcuts are added with a probability $p$, but their range is restricted: a shortcut from a node can only connect to another node within a Euclidean distance $rN$ (where $N=L/2$). The parameter $r \in [0, 1]$ controls the locality of the shortcuts. When $r=1$, the model recovers the standard global SWN; when $r \to 0$, the network remains a locally connected lattice.
Non-Monotonic Path Length Behavior
A striking discovery in this research is the non-monotonic relationship between the average path length ($\bar{l}$) and the system size ($L$). In standard models, increasing the number of nodes typically increases the distance between them. In SRSWNs, however, $ar{l}$ initially increases with $L$, reaches a maximum, and then decreases before eventually settling into a logarithmic growth phase.
This "shrinking" effect occurs because as $L$ grows, the absolute number of available shortcuts within the range $rL$ increases. At a certain threshold, the addition of these new shortcuts compensates for the increased network diameter, making the larger network more navigable than a smaller one.
Universal Scaling and the Small-World Effect
Despite the range constraints, the small-world effect persists even for $r \ll 1$. This implies that "local" shortcuts within a community are sufficient to create a highly connected global structure. The authors derived a universal scaling form for the mean path length, showing that the network's behavior can be described by a combination of scaling functions $K(y)$ and $f(y)$, where $y = rLp$ represents the total number of shortcuts within the allowed range.
For large systems, the mean path length is approximated by: $$\bar{\ell} \approx \frac{\log(2rLp)}{4p} + \frac{0.16}{rp}$$ This formula confirms that the network retains small-world properties as long as the shortcut density within the range is sufficiently high ($y \gg 1$).
Conclusion
This study demonstrates that global shortcuts are not a prerequisite for the small-world phenomenon. By introducing a finite range for shortcuts, the SRSWN model reveals unique structural dynamics, most notably the non-monotonic scaling of path length. While the current model assumes a uniform distribution of shortcuts within the range $r$, future work could explore more complex distributions or the impact of these finite-range links on dynamic processes like synchronization or disease spreading.
Summary updated