Navigable Networks as Nash Equilibria of Navigation Games

A. Gulyas, J. Biro, A. Korosi, G. Retvari, and D. Krioukov
Nature Communications
v.6, p.7651, 2015
July 3, 2015

Abstract

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.

Related publications