Emergence of hierarchy in cost-driven growth of spatial networks
- 14 May 2013
- journal article
- research article
- Published by National Academy of Sciences in Proceedings of the National Academy of Sciences
- Vol. 110 (22) , 8824-8829
Abstract
One of the most important features of spatial networks—such as transportation networks, power grids, the Internet, and 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 not elucidated, however, 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 a single scale and produces a family of networks that range from the star graph to the minimum spanning tree and are characterized 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 basic 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.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Spatial networksPhysics Reports, 2011
- Connected Spatial Networks over Random Points and a Route-Length StatisticStatistical Science, 2010
- Topological evolution of surface transportation networksComputers, Environment and Urban Systems, 2009
- Modeling Urban Street PatternsPhysical Review Letters, 2008
- Extracting the hierarchical organization of complex systemsProceedings of the National Academy of Sciences, 2007
- Shape and efficiency in spatial distribution networksJournal of Statistical Mechanics: Theory and Experiment, 2006
- A geographer's analysis of hub-and-spoke networksJournal of Transport Geography, 1998
- Bootstrapping the Gini Coefficient of InequalityEcology, 1987
- An Iterative Model for Generating Transportation Networks*Geographical Analysis, 1971
- Demographic Gravitation: Evidence and ApplicationsSociometry, 1948