Emergence of hierarchy in cost driven growth of spatial networks

Abstract

One of the most important features of spatial networks such as transportation networks, power grids, Internet, neural networks, is the existence of a cost associated with the length of links. Such a cost has a profound influence on the global structure of these networks which usually display a hierarchical spatial organization. The link between local constraints and large-scale structure is however not elucidated and we introduce here a generic model for the growth of spatial networks based on the general concept of cost benefit analysis. This model depends essentially on one single scale and produces a family of networks which range from the star-graph to the minimum spanning tree and which are characterised by a continuously varying exponent. We show that spatial hierarchy emerges naturally, with structures composed of various hubs controlling geographically separated service areas, and appears as a large-scale consequence of local cost-benefit considerations. Our model thus provides the first building blocks for a better understanding of the evolution of spatial networks and their properties. We also find that, surprisingly, the average detour is minimal in the intermediate regime, as a result of a large diversity in link lengths. Finally, we estimate the important parameters for various world railway networks and find that --remarkably-- they all fall in this intermediate regime, suggesting that spatial hierarchy is a crucial feature for these systems and probably possesses an important evolutionary advantage.

11 pages, 11 figures, 1 table

References in corpus (4)

• Extracting the hierarchical organization of complex systems
• Modeling urban street patterns
• Shape and efficiency in spatial distribution networks
• Connected Spatial Networks over Random Points and a Route-Length Statistic

Cited by in corpus (25)

• Social physics
• The evolutionary origins of hierarchy
• Emergence of core-peripheries in networks
• Scaling in transportation networks
• Phase transitions in Pareto optimal complex networks
• Urban retail dynamics: insights from percolation theory and spatial interaction modelling
• Architecture of the Florida Power Grid as a Complex Network
• Urban transportation networks and optimal transport-based infrastructures: similarity and economy of scale
• Scaling in the recovery of urban transportation systems from special events
• Pareto optimality in multilayer network growth
• Quantitative analyses of the plant cytoskeleton reveal underlying organizational principles
• Balancing building and maintenance costs in growing transport networks
• Transitions in spatial networks
• Model for the growth of the World Airline Network
• Comparing spatial networks: A 'one size fits all' efficiency-driven approach
• Deconstructing laws of accessibility and facility distribution in cities
• Quantifying relation between mobility patterns and socioeconomic status of dockless sharing-bike users
• A link model approach to identify congestion hotspots
• Imbalance of pairwise efficiency in urban street network
• Continuous Average Straightness in Spatial Graphs
• Individual-level evolutions manifest population-level scaling in complex supply networks
• An interdisciplinary bibliometric analysis of models for land-use and transport interactions
• Extracting Spatiotemporal Demand for Public Transit from Mobility Data
• Biological and Shortest-Path Routing Procedures for Transportation Network Design
• Complementarity of generative models for road networks