Smallest small-world network

Abstract

Efficiency in passage times is an important issue in designing networks, such as transportation or computer networks. The small-world networks have structures that yield high efficiency, while keeping the network highly clustered. We show that among all networks with the small-world structure, the most efficient ones have a single ``center'', from which all shortcuts are connected to uniformly distributed nodes over the network. The networks with several centers and a connected subnetwork of shortcuts are shown to be ``almost'' as efficient. Genetic-algorithm simulations further support our results.

5 pages, 6 figures, REVTeX4

References in corpus (9)

• Emergence of scaling in random networks
• Error and attack tolerance of complex networks
• Efficient Behavior of Small-World Networks
• The structure of scientific collaboration networks
• The diameter of the world wide web
• Evolution of networks
• Mean-field solution of the small-world network model
• Small-worlds: How and why
• Exactly solvable analogy of small-world networks

Cited by in corpus (7)

• Heterogeneity in oscillator networks: Are smaller worlds easier to synchronize?
• Modeling Cascading Failures in the North American Power Grid
• Topology of the conceptual network of language
• Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices
• Evolving small-world networks with geographical attachment preference
• Optimization in Networks
• Fractality and degree correlations in scale-free networks