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.

arXiv comment40 pages, 17 figures

References in corpus (31)

• The structure and function of complex networks
• Epidemic spreading in scale-free networks
• Power laws, Pareto distributions and Zipf's law
• Identification of influential spreaders in complex networks
• Emergent complex neural dynamics
• Hyperbolic Geometry of Complex Networks
• Identity and Search in Social Networks
• Dynamics of Rumor Spreading in Complex Networks
• Scale-Free Networks are Ultrasmall
• Velocity and hierarchical spread of epidemic outbreaks in scale-free networks
• Popularity versus Similarity in Growing Networks
• Navigability of Complex Networks
• Sustaining the Internet with Hyperbolic Mapping
• Class of correlated random networks with hidden variables
• Networks in Cognitive Science
• The dynamical strength of social ties in information spreading
• 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
• Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces
• Designing optimal transport networks
• Small world-Fractal Transition in Complex Networks: Renormalization Group Approach
• Network Mapping by Replaying Hyperbolic Growth
• Extended navigability of small world networks: exact results and new insights
• Lognormal Infection Times of Online Information Spread
• Exploring Maps with Greedy Navigators
• Appell polynomials and their relatives
• Dispensability of Escherichia coli's latent pathways
• Duality between equilibrium and growing networks
• 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