Spreading and shortest paths in systems with sparse long-range connections

Abstract

Spreading according to simple rules (e.g. of fire or diseases), and shortest-path distances are studied on d-dimensional systems with a small density p per site of long-range connections (``Small-World'' lattices). The volume V(t) covered by the spreading quantity on an infinite system is exactly calculated in all dimensions. We find that V(t) grows initially as t^d/d for t<< t^* = (2p Γ_d (d-1)!)^{-1/d} and later exponentially for $t>>t^{\ast }$, generalizing a previous result in one dimension. Using the properties of V(t), the average shortest-path distance \ell(r) can be calculated as a function of Euclidean distance r. It is found that \ell(r) = r for r<r_c=(2p Γ_d (d-1)!)^{-1/d} log(2p Γ_d L^d), and \ell(r) = r_c for r>r_c. The characteristic length r_c, which governs the behavior of shortest-path lengths, diverges with system size for all p>0. Therefore the mean separation s \sim p^{-1/d} between shortcut-ends is not a relevant internal length-scale for shortest-path lengths. We notice however that the globally averaged shortest-path length, divided by L, is a function of L/s only.

4 pages, 1 eps fig. Uses psfig

References in corpus (5)

• Renormalization group analysis of the small-world network model
• Scaling and percolation in the small-world network model
• Evolutionary dynamics in the Bak-Sneppen model on small-world networks
• Comment on ``Small-world networks: Evidence for a crossover picture''
• Infinite characteristic length on small-world systems

Cited by in corpus (40)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Evolution of networks
• Epidemics and percolation in small-world networks
• Dynamics of rumor propagation on small-world networks
• Social games in a social network
• COVID-19 lockdown induces disease-mitigating structural changes in mobility networks
• Mean-field solution of the small-world network model
• Critical behavior of propagation on small-world networks
• Maximal planar networks with large clustering coefficient and power-law degree distribution
• Efficiency of informational transfer in regular and complex networks
• Exact solution of site and bond percolation on small-world networks
• Citation Networks in High Energy Physics
• Models of the Small World: A Review
• Small-World Networks: Links with long-tailed distributions
• Exactly solvable analogy of small-world networks
• Chaos in Small-World Networks
• Relaxation Properties of Small-World Networks
• Random spread on the family of small-world networks
• Shortest paths on systems with power-law distributed long-range connections
• Small-World Rouse Networks as models of cross-linked polymers
• Exact results and scaling properties of small-world networks
• Stability of a neural network model with small-world connections
• Scaling of random spreading in small world networks
• Evolving small-world networks with geographical attachment preference
• Localization-Delocalization Transition of Electron States in a Disordered Quantum Small World Network
• Small-world behavior in a system of mobile elements
• Complex Network Properties of Chinese Natural Science Basic Research
• Epidemic Variability in Hierarchical Geographical Networks with Human Activity Patterns
• An Epidemic Model on Small-World Networks and Ring Vaccination
• Turbulence in small-world networks
• Random spreading phenomena in annealed small world networks
• Small-World Networks in Geophysics
• Superdiffusion in a class of networks with marginal long-range connections
• Cellular Automata Networks
• Scaling behavior of the contact process in networks with long-range connections
• Optimal disorder for segregation in annealed small worlds
• Unusual percolation in simple small-world networks
• Fractals in Small-World Networks With Time Delay
• Controlling the spreading in small-world networks