Evolutionary Construction of Geographical Networks with Nearly Optimal Robustness and Efficient Routing Properties

Abstract

Robust and efficient design of networks on a realistic geographical space is one of the important issues for the realization of dependable communication systems. In this paper, based on a percolation theory and a geometric graph property, we investigate such a design from the following viewpoints: 1) network evolution according to a spatially heterogeneous population, 2) trimodal low degrees for the tolerant connectivity against both failures and attacks, and 3) decentralized routing within short paths. Furthermore, we point out the weakened tolerance by geographical constraints on local cycles, and propose a practical strategy by adding a small fraction of shortcut links between randomly chosen nodes in order to improve the robustness to a similar level to that of the optimal bimodal networks with a larger degree $O(\sqrt{N})$ for the network size $N$. These properties will be useful for constructing future ad-hoc networks in wide-area communications.

14 pages, 10 figures, 1 table

References in corpus (7)

• Efficient routing on complex networks
• The spatial structure of networks
• Self-similar disk packings as model spatial scale-free networks
• Communication Bottlenecks in Scale-Free Networks
• Geographical networks evolving with optimal policy
• Improvement of the robustness on geographical networks by adding shortcuts
• Growing networks under geographical constraints

Cited by in corpus (7)

• Geographical networks stochastically constructed by a self-similar tiling according to population
• Growing Self-organized Design of Efficient and Robust Complex Networks
• Spatially self-organized resilient networks by a distributed cooperative mechanism
• Self-organized network design by link survivals and shortcuts
• An approximative calculation of the fractal structure in self-similar tilings
• Combinatorial and approximative analyses in a spatially random division process
• Recoverable DTN Routing based on a Relay of Cyclic Message-Ferries on a MSQ Network