Navigable Networks as Nash Equilibria of Navigation Games

Abstract

The common sense suggests that networks are not random mazes of purposeless connections, but that these connections are organised so that networks can perform their functions well. One function common to many networks is targeted transport or navigation. Using game theory, here we show that minimalistic networks designed to maximise the navigation efficiency at minimal cost share basic structural properties with real networks. These idealistic networks are Nash equilibria of a network construction game whose purpose is to find an optimal trade-off between the network cost and navigability. We show that these skeletons are present in the Internet, metabolic, English word, US airport, Hungarian road networks, and in a structural network of the human brain. The knowledge of these skeletons allows one to identify the minimal number of edges by altering which one can efficiently improve or paralyse navigation in the network.

40 pages, 17 figures

References in corpus (12)

• Emergent complex neural dynamics
• Hyperbolic Geometry of Complex Networks
• Navigability of Complex Networks
• Sustaining the Internet with Hyperbolic Mapping
• Origins of power-law degree distribution in the heterogeneity of human activity in social networks
• Scaling theory of transport in complex networks
• Traffic-driven Epidemic Spreading in Finite-size Scale-Free Networks
• Lognormal Infection Times of Online Information Spread
• Appell polynomials and their relatives
• Dispensability of Escherichia coli's latent pathways
• A greedy-navigator approach to navigable city plans
• Geometric properties of graph layouts optimized for greedy navigation

Cited by in corpus (23)

• Network Geometry
• Navigation of brain networks
• Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
• Geometric renormalization unravels self-similarity of the multiscale human connectome
• The hidden geometry of weighted complex networks
• Clustering implies geometry in networks
• Soft communities in similarity space
• The inherent community structure of hyperbolic networks
• A "Social Bitcoin" could sustain a democratic digital world
• Geometric explanation of the rich-club phenomenon in complex networks
• Collective navigation of complex networks: Participatory greedy routing
• Random hyperbolic graphs in $d+1$ dimensions
• Model-independent methods for embedding directed networks into Euclidean and hyperbolic spaces
• Optimisation of the coalescent hyperbolic embedding of complex networks
• Growing homophilic networks are natural navigable small worlds
• Random graphs and real networks with weak geometric coupling
• Navigability of Random Geometric Graphs in the Universe and Other Spacetimes
• Model-free hidden geometry of complex networks
• Strange Attractors in Complex Networks
• Geometric detection of hierarchical backbones in real networks
• Network architecture of energy landscapes in mesoscopic quantum systems
• Systematic comparison of graph embedding methods in practical tasks
• A Game Theoretic Model for the Formation of Navigable Small-World Networks --- the Tradeoff between Distance and Reciprocity