Hysteretic percolation from locally optimal individual decisions
arXiv:1709.07257 · doi:10.1103/PhysRevLett.120.248302
Abstract
The emergence of large-scale connectivity underlies the proper functioning of many networked systems, ranging from social networks and technological infrastructure to global trade networks. Percolation theory characterizes network formation following stochastic local rules, while optimization models of network formation assume a single controlling authority or one global objective function. In socio-economic networks, however, network formation is often driven by individual, locally optimal decisions. How such decisions impact connectivity is only poorly understood to date. Here, we study how large-scale connectivity emerges from decisions made by rational agents that individually minimize costs for satisfying their demand. We establish that the solution of the resulting nonlinear optimization model is exactly given by the final state of a local percolation process. This allows us to systematically analyze how locally optimal decisions on the micro-level define the structure of networks on the macroscopic scale.
arXiv comment6 pages, 5 figures and an additional 23 pages, 10 figures appendix/supplement. See also ancillary files for data
References in corpus (21)
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Error and attack tolerance of complex networks
- Epidemic spreading in scale-free networks
- Catastrophic cascade of failures in interdependent networks
- The scaling laws of human travel
- Forecast and Control of Epidemics in a Globalized World
- Damage and fluctuations induce loops in optimal transport networks
- Impact of Single Links in Competitive Percolation -- How complex networks grow under competition
- Self-organized adaptation of a simple neural circuit enables complex robot behaviour
- Optimal design of spatial distribution networks
- Explosive Percolation: Novel critical and supercritical phenomena
- Structure, Scaling and Phase Transition in the Optimal Transport Network
- Global Optimization, Local Adaptation, and the Role of Growth in Distribution Networks
- Critical links and nonlocal rerouting in complex supply networks
- Emergence of core-peripheries in networks
- Designing the Dynamics of Spiking Neural Networks
- Dual theory of transmission line outages
- Crackling Noise in Fractional Percolation -- Randomly distributed discontinuous jumps in explosive percolation
- Designing Complex Networks
- Discrete Scale Invariance in Supercritical Percolation
Cited by in corpus (9)
- Explosive Phenomena in Complex Networks
- Anomalous supply shortages from dynamic pricing in on-demand mobility
- Discontinuous transition to loop formation in optimal supply networks
- Shortest-path percolation on random networks
- The winner takes it all -- How to win network globalization
- Spontaneous symmetry breaking in ride-sharing adoption dynamics
- Emergence of biconnected clusters in explosive percolation
- Demand-driven design of bicycle infrastructure networks for improved urban bikeability
- Formation of trade networks by economies of scale and product differentiation