Geographical networks evolving with optimal policy

Abstract

In this article, we propose a growing network model based on an optimal policy involving both topological and geographical measures. In this model, at each time step, a new node, having randomly assigned coordinates in a $1\times 1$ square, is added and connected to a previously existing node $i$, which minimizes the quantity $r_i^2/k_i^{\alpha }$, where $r_i$ is the geographical distance, $k_i$ the degree, and $\alpha$ a free parameter. The degree distribution obeys a power-law form when $\alpha =1$, and an exponential form when $\alpha =0$. When $\alpha$ is in the interval $(0,1)$, the network exhibits a stretched exponential distribution. We prove that the average topological distance increases in a logarithmic scale of the network size, indicating the existence of the small-world property. Furthermore, we obtain the geographical edge-length distribution, the total geographical length of all edges, and the average geographical distance of the whole network. Interestingly, we found that the total edge-length will sharply increase when $\alpha$ exceeds the critical value ${\alpha }_c=1$, and the average geographical distance has an upper bound independent of the network size. All the results are obtained analytically with some reasonable approximations, which are well verified by simulations.

8 pages, 6 figures

References in corpus (37)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• The architecture of complex weighted networks
• The large-scale organization of metabolic networks
• Evolution of networks
• Classes of behavior of small-world networks
• Mean-field theory for scale-free random networks
• The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
• Dynamical and correlation properties of the Internet
• Structural Vulnerability of the North American Power Grid
• Connectivity of Growing Random Networks
• Organization of Growing Random Networks
• Stretched exponential distributions in Nature and Economy: ``Fat tails'' with characteristic scales
• Modeling the Internet's Large-Scale Topology
• Efficient routing on complex networks
• Small-world properties of the Indian Railway network
• Is the Boston subway a small-world network ?
• The spatial structure of networks
• Statistical analysis of 22 public transport networks in Poland
• Layered Complex Networks
• The Simultaneous Evolution of Author and Paper Networks
• Maximal planar networks with large clustering coefficient and power-law degree distribution
• Crossover from Scale-Free to Spatial Networks
• Trainspotting: Extraction and Analysis of Traffic and Topologies of Transportation Networks
• Optimal Paths in Disordered Complex Networks
• Modulated Scale-free Network in the Euclidean Space
• High dimensional random Apollonian networks
• Connectivity Distribution of Spatial Networks
• Phase transitions in a network with range dependent connection probability
• Geographical effects on cascading breakdowns of scale-free networks
• Evolving small-world networks with geographical attachment preference
• Weighted Scale-free Networks in Euclidean Space Using Local Selection Rule
• Clustering properties of a generalised critical Euclidean network
• Epidemic spreading in lattice-embedded scale-free networks
• Geographical effects on epidemic spreading in scale-free networks
• Scale-free network on a vertical plane

Cited by in corpus (10)

• Link prediction in complex networks: a local na\"ıve Bayes model
• Preferential attachment in growing spatial networks
• Generating Synthetic Systems of Interdependent Critical Infrastructure Networks
• Scaling of critical connectivity of mobile ad hoc communication networks
• Evolutionary Construction of Geographical Networks with Nearly Optimal Robustness and Efficient Routing Properties
• Geographical networks stochastically constructed by a self-similar tiling according to population
• Dynamics on Spatial Networks and the Effect of Distance Coarse Graining
• Degree heterogeneity in spatial networks with total cost constraint
• Morphogenesis of complex networks: a reaction diffusion framework for spatial graphs
• Measuring multiple evolution mechanisms of complex networks