Exactly solvable analogy of small-world networks

Abstract

We present an exact description of a crossover between two different regimes of simple analogies of small-world networks. Each of the sites chosen with a probability $p$ from $n$ sites of an ordered system defined on a circle is connected to all other sites selected in such a way. Every link is of a unit length. Thus, while $p$ changes from 0 to 1, an averaged shortest distance between a pair of sites changes from $\bar{\ell }\sim n$ to $\bar{\ell }=1$. We find the distribution of the shortest distances $P(\ell )$ and obtain a scaling form of $\bar{\ell }(p,n)$. In spite of the simplicity of the models under consideration, the results appear to be surprisingly close to those obtained numerically for usual small-world networks.

4 pages with 3 postscript figures

References in corpus (6)

• Emergence of scaling in random networks
• The diameter of the world wide web
• Scaling and percolation in the small-world network model
• Diffusion, localization and dispersion relations on ``small-world'' lattices
• Spreading and shortest paths in systems with sparse long-range connections
• Erratum: Small-world networks: Evidence for a crossover picture

Cited by in corpus (37)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Evolution of networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Spatial Networks
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Heterogeneity in oscillator networks: Are smaller worlds easier to synchronize?
• Deterministic Scale-Free Networks
• Bipartite Graphs as Models of Complex Networks
• Scaling Behaviour of Developing and Decaying Networks
• Citation Networks in High Energy Physics
• Percolation and epidemics in a two-dimensional small world
• Small-worlds: How and why
• Models of the Small World: A Review
• A deterministic small-world network created by edge iterations
• How does Europe Make Its Mind Up? Connections, cliques, and compatibility between countries in the Eurovision Song Contest
• Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices
• Effect of congestion costs on shortest paths through complex networks
• Evolving Apollonian Networks with Small-world Scale-free topologies
• Interplay between function and structure in complex networks
• Evolving small-world networks with geographical attachment preference
• Smallest small-world network
• Quantum Gravity as an Information Network: Self-Organization of a 4D Universe
• Scale free networks by preferential depletion
• Simple models of small world networks with directed links
• Preferential attachment with information filtering - node degree probability distribution properties
• Effects of decision-making on the transport costs across complex networks
• Transitions in spatial networks
• Intermittent exploration on a scale-free network
• Correlation effects in a simple model of small-world network
• Random Walks in Local Dynamics of Network Losses
• The Network of Mexican Cities
• Temporal Correlations of Local Network Losses
• Markov chain approach to anomalous diffusion on Newman-Watts networks
• Braess like Paradox on Ladder Network
• Braess like Paradox in a Small World Network
• Explicit Solutions to the Continuous Time Albert-Barabási Scale-Free Model