title: Navigable networks as Nash equilibria of navigation games.
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.
authors.affiliation: 1] High Speed Networks Laboratory, Department of Telecommunications and Media Informatics, Budapest University of Technology and Economics, 2 Magyar tudósok str., Budapest 1117, Hungary [2] MTA-BME Information Systems Research Group, Budapest University of Technology and Economics, 2 Magyar tudósok str., Budapest 1117, Hungary.
authors.forename: András
authors.initials: A
authors.lastname: Gulyás
authors.affiliation: 1] High Speed Networks Laboratory, Department of Telecommunications and Media Informatics, Budapest University of Technology and Economics, 2 Magyar tudósok str., Budapest 1117, Hungary [2] MTA-BME Future Internet Research Group, Budapest University of Technology and Economics, 2 Magyar tudósok str., Budapest 1117, Hungary.
authors.forename: József J
authors.initials: JJ
authors.lastname: Bíró
authors.affiliation: MTA-BME Information Systems Research Group, Budapest University of Technology and Economics, 2 Magyar tudósok str., Budapest 1117, Hungary.
authors.forename: Attila
authors.initials: A
authors.lastname: Kőrösi
authors.affiliation: 1] High Speed Networks Laboratory, Department of Telecommunications and Media Informatics, Budapest University of Technology and Economics, 2 Magyar tudósok str., Budapest 1117, Hungary [2] MTA-BME Future Internet Research Group, Budapest University of Technology and Economics, 2 Magyar tudósok str., Budapest 1117, Hungary.
authors.forename: Gábor
authors.initials: G
authors.lastname: Rétvári
authors.affiliation: Northeastern University, Department of Physics, Department of Mathematics, Department of Electrical&Computer Engineering, 360 Huntington Ave, 111 Dana Research Center, Boston, Massachusetts 02115, USA.
authors.forename: Dmitri
authors.identifier: 0000000194788182
authors.initials: D
authors.lastname: Krioukov
mesh_terms: D001921:Brain; D003195:Computer Communication Networks; D005716:Game Theory; D006801:Humans; D020407:Internet; D007802:Language; D060066:Protein Interaction Maps; D014186:Transportation