Emergence of hierarchy in cost-driven growth of spatial networks

DOI10.1073/PNAS.1222441110MaRDI QIDQ5171007zbMATH OpenOpenAlexWikidataFDO

Authors Rémi Louf, Pablo Jensen, Marc Barthélémy

Publication date 25 July 2014

Published in Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.3282

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30) Stochastic network models in operations research (90B15) Network design and communication in computer systems (68M10) Internet topics (68M11) Transport processes in time-dependent statistical mechanics (82C70) Spatial models in economics (91B72)

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.

Recommendations

• On the origins of hierarchy in complex networks
• GROWING HIERARCHICAL SCALE-FREE NETWORKS BY MEANS OF NONHIERARCHICAL PROCESSES
• On the formation of structure in growing networks
• Morphogenesis of spatial networks
• The effects of spatial constraints on the evolution of weighted complex networks
• The evolution of a spatial stochastic network
• Emergent structures in large networks
• Network evolution and the emergence of structure
• Emergence of Scaling in Random Networks

Cites work

• Connected spatial networks over random points and a route-length statistic
• Hub network design with single and multiple allocation: A computational study
• Modeling the growth of transportation networks: A comprehensive review
• The ecology of rotators

Cited in

(6)

• Optimization of spatial complex networks
• Spatial Gibbs random graphs
• Spatial networks evolving to reduce length
• On the origins of hierarchy in complex networks
• Developmental time windows for spatial growth generate multiple-cluster small-world networks
• \textsc{MassExodus}: modeling evolving networks in harsh environments

This page was built for publication: Emergence of hierarchy in cost-driven growth of spatial networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5171007)