Navigable networks as Nash equilibria of navigation games

By András Gulyás, József Bíró, Attila Korösi, Gábor Rétvári, Dmitri V. Krioukov. 2014

73 citations recorded by the source corpus.

Common sense suggests that networks are not random mazes of purposeless connections, but that these connections are organized so that networks can perform their functions well. One function common to many networks is targeted transport or navigation. Here, using game theory, we show that minimalistic networks designed to maximize 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. Connections in networks are organized to fulfil a function, and a common one is targeted transport or navigation. Here the authors use game theory to show how networks designed to maximize navigation efficiency at minimal cost share basic structural properties, which are also found in real cases.

Subfields: Ecology, Evolution, Behavior and Systematics, Statistical and Nonlinear Physics, Graph Learning, Game & Decision Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistical and Nonlinear Physics

In Graph Learning

Citations in the corpus

Small-World Brain Networks Revisited (2016, background): “There is much important recent work on topological properties like degree distribution and hubness [48], modularity [49–55], core/periphery organisation [56–58], controllability [59–61] and navigability [62] that are not simply related to small-worldness.”
Communication dynamics in complex brain networks (2017, background): “For example, greedy-routing strategies can be efficient for certain network topologies 50 and require less information than routing communication 173 .”
Growing Homophilic Networks Are Natural Navigable Small Worlds (2015, unknown): “Later, hyperbolicity of hidden metric space was proposed as a possible reason of forming such navigable structures in real-life networks[14, 15, 17].”