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.