Hysteretic percolation from locally optimal individual decisions

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.

6 pages, 5 figures and an additional 23 pages, 10 figures appendix/supplement. See also ancillary files for data

References in corpus (11)

• The scaling laws of human travel
• Self-organized adaptation of a simple neural circuit enables complex robot behaviour
• Impact of Single Links in Competitive Percolation -- How complex networks grow under competition
• Optimal design of spatial distribution networks
• Explosive Percolation: Novel critical and supercritical phenomena
• 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
• Dual theory of transmission line outages
• 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