Review lecture in frameworks of the workshop CCEGN-2017

Friday, 19 May 2017
Facilty of Computer Sciences of Higher School of Economics, Кочновский проезд, дом 3, в аудитории 205

Navigable networks as Nash equilibria of navigation games

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, and to show that the spatiostructural organization of the human brain is nearly as needed for optimal routing of information between different parts of the brain.


András Gulyás, József J. Bíró, Attila Kőrösi, Gábor Rétvári, and Dmitri Krioukov, "Navigable networks as Nash equilibria of navigation games", Nature Communications 6:7651, 2015.