Small-world networks: Evidence for a crossover picture

Abstract

Watts and Strogatz [Nature 393, 440 (1998)] have recently introduced a model for disordered networks and reported that, even for very small values of the disorder $p$ in the links, the network behaves as a small-world. Here, we test the hypothesis that the appearance of small-world behavior is not a phase-transition but a crossover phenomenon which depends both on the network size $n$ and on the degree of disorder $p$. We propose that the average distance $\ell$ between any two vertices of the network is a scaling function of $n/n^{\ast }$. The crossover size $n^{\ast }$ above which the network behaves as a small-world is shown to scale as $n^{\ast }(p\ll 1)\sim p^{-\tau }$ with $\tau \approx 2/3$.

5 pages, 5 postscript figures (1 in color), Latex/Revtex/multicols/epsf. Accepted for publication in Physical Review Letters

References in corpus (2)

• Autocatalytic Sets and the Growth of Complexity in an Evolutionary Model
• Time scale separation and heterogeneous off-equilibrium dynamics in spin models over random graphs

Cited by in corpus (101)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Error and attack tolerance of complex networks
• Efficient Behavior of Small-World Networks
• The diameter of the world wide web
• The large-scale organization of metabolic networks
• Evolution of networks
• Classes of behavior of small-world networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Mean-field theory for scale-free random networks
• Epidemic dynamics and endemic states in complex networks
• Synchronization in small-world systems
• Renormalization group analysis of the small-world network model
• The Web of Human Sexual Contacts
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Scaling and percolation in the small-world network model
• Organization of Growing Random Networks
• Small-world properties of the Indian Railway network
• Dynamics of rumor propagation on small-world networks
• Fast Response and Temporal Coding on Coherent Oscillations in Small-World Networks
• Spectra of "Real-World" Graphs: Beyond the Semi-Circle Law
• Evolution of reference networks with aging
• Mean-field solution of the small-world network model
• Critical behavior of propagation on small-world networks
• Emergence of a small world from local interactions: Modeling acquaintance networks
• Robust Patterns in Food Web Structure
• Incomplete ordering of the voter model on small-world networks
• Scaling Behaviour of Developing and Decaying Networks
• Optimal Paths in Disordered Complex Networks
• Exact solution of site and bond percolation on small-world networks
• Citation Networks in High Energy Physics
• Designing optimal transport networks
• Ising model in small-world networks
• Percolation and epidemics in a two-dimensional small world
• Photon localization and Dicke superradiance in atomic gases
• Nonequilibrium Phase Transitions in Directed Small-World Networks
• XY model in small-world networks
• Spreading and shortest paths in systems with sparse long-range connections
• Growth and structure of Slovenia's scientific collaboration network
• Small-World Networks: Links with long-tailed distributions
• Analytical solution of a model for complex food webs
• Chaos in Small-World Networks
• Small-world networks and the conformation space of a lattice polymer chain
• Exactly solvable analogy of small-world networks
• Weighted Scale-Free Networks with Stochastic Weight Assignments
• From brain to earth and climate systems: Small-world interaction networks or not?
• Relaxation Properties of Small-World Networks
• Optimal Path and Minimal Spanning Trees in Random Weighted Networks
• Two distinct transitions in spatially embedded multiplex networks
• Random spread on the family of small-world networks
• Naming Games in Two-Dimensional and Small-World-Connected Random Geometric Networks
• Beware of the Small-World neuroscientist!
• Physical realizability of small-world networks
• Dynamic critical behavior of the XY model in small-world networks
• Shortest paths on systems with power-law distributed long-range connections
• Synchronization of Kauffman networks
• First-order transition in small-world networks
• Farey Graphs as Models for Complex Networks
• Exact results and scaling properties of small-world networks
• Giant Clusters in Random Ad Hoc Networks
• On reducing Terrorism Power: A Hint from Physics
• Satellite-based photonic quantum networks are small-world
• Evolving small-world networks with geographical attachment preference
• Localization-Delocalization Transition of Electron States in a Disordered Quantum Small World Network
• Comparing intermittency and network measurements of words and their dependency on authorship
• Exactly solvable scale-free network model
• Extreme Fluctuations in Small-Worlds with Relaxational Dynamics
• Critical behavior of the contact process on small-world networks
• Small-world behavior in a system of mobile elements
• Self-avoiding walks and connective constants in small-world networks
• Local-world evolving networks with tunable clustering
• Von Neumann entropy and localization-delocalization transition of electron states in quantum small-world networks
• How much random a random network is : a random matrix analysis
• Non-Markov stochastic dynamics of real epidemic process of respiratory infections
• A geometric growth model interpolating between regular and small-world networks
• Evolution of the Chinese Guarantee Network under Financial Crisis and Stimulus Program
• From regular to growing small-world networks
• Small-World Networks in Geophysics
• Critical properties of a dissipative sandpile model on small world networks
• Electron in a tangled chain: multifractality at the small-world critical point
• Cooperative effects and photon localization in atomic gases: The two-dimensional case
• Transitions in spatial networks
• Small world effects in evolution
• Zero-temperature Glauber dynamics on small-world networks
• Optimal disorder for segregation in annealed small worlds
• An Analysis of the Transition Zone Between the Various Scaling Regimes in the Small-World Model
• A dynamical characterization of the small world phase
• On the decentralized navigation of multiple packages on transportation networks
• Network Size Estimation in Small-World Networks under Byzantine Faults
• Self-organized network design by link survivals and shortcuts
• Conformation-networks of two-dimensional lattice homopolymers
• Quantum magnetism on small-world networks
• The Network of Mexican Cities
• Infinite characteristic length on small-world systems
• Disordered configurations of the Glauber model in two-dimensional networks
• Switch between critical percolation modes in city traffic dynamics
• Bankruptcy as an exit mechanism for systems with a variable number of components
• A Random Matrix Approach to Language Acquisition
• Fractals in Small-World Networks With Time Delay
• Network Subgraphs of the heterogeneous Chinese credit system
• A Threshold For Clusters in Real-World Random Networks