Small-worlds: How and why
arXiv:cond-mat/0002076 · doi:10.1103/PhysRevE.63.021117
Abstract
We investigate small-world networks from the point of view of their origin. While the characteristics of small-world networks are now fairly well understood, there is as yet no work on what drives the emergence of such a network architecture. In situations such as neural or transportation networks, where a physical distance between the nodes of the network exists, we study whether the small-world topology arises as a consequence of a tradeoff between maximal connectivity and minimal wiring. Using simulated annealing, we study the properties of a randomly rewired network as the relative tradeoff between wiring and connectivity is varied. When the network seeks to minimize wiring, a regular graph results. At the other extreme, when connectivity is maximized, a near random network is obtained. In the intermediate regime, a small-world network is formed. However, unlike the model of Watts and Strogatz (Nature {\bf 393}, 440 (1998)), we find an alternate route to small-world behaviour through the formation of hubs, small clusters where one vertex is connected to a large number of neighbours.
20 pages, latex, 9 figures
References in corpus (3)
Cited by in corpus (36)
- Evolution of networks
- Spatial Networks
- Emergence of a small world from local interactions: Modeling acquaintance networks
- Public transport networks: empirical analysis and modeling
- Scale-free Networks from Optimal Design
- Efficiency of informational transfer in regular and complex networks
- Correlated random networks
- Shape and efficiency in spatial distribution networks
- Network Harness: Metropolis Public Transport
- Optimal Traffic Networks
- Network Structures from Selection Principles
- Topology of Fracture Networks
- Physical realizability of small-world networks
- Phase transitions in Pareto optimal complex networks
- Modular networks emerge from multiconstraint optimization
- Smallest small-world network
- Topological features of proteins from amino acid residue networks
- Coordinated and Uncoordinated Optimization of Networks
- Emergence of clustering: Role of inhibition
- Modular networks with hierarchical organization: The dynamical implications of complex structure
- Patterns in randomly evolving networks: Idiotypic networks
- An Epidemic Model on Small-World Networks and Ring Vaccination
- Optimal Synchronization in Space
- Evolving network - simulation study. From regular lattice to scale free network
- Limits and trade-offs of topological network robustness
- Small Worlds in Space: Synchronization, Spatial and Relational Modularity
- Universal vulnerability in strong modular networks with various degree distributions between inequality and equality
- Heterogeneous network with distance dependent connectivity
- Correlation effects in a simple model of small-world network
- Preferential compactness of networks
- Unusual percolation in simple small-world networks
- Local search on protein residue networks
- A Game Theoretic Model for the Formation of Navigable Small-World Networks --- the Tradeoff between Distance and Reciprocity
- Maximizing graph probability under conditionally exponential models
- Evolve Networks Towards Better Performance: a Compromise between Mutation and Selection
- Characterizing Self-Developing Biological Neural Networks: A First Step Towards their Application To Computing Systems