Navigable networks as Nash equilibria of navigation games

András Gulyás (), József J. Bíró, Attila Kőrösi, Gábor Rétvári and Dmitri Krioukov ()
Additional contact information
András Gulyás: High Speed Networks Laboratory, Budapest University of Technology and Economics
József J. Bíró: High Speed Networks Laboratory, Budapest University of Technology and Economics
Attila Kőrösi: MTA-BME Information Systems Research Group, Budapest University of Technology and Economics
Gábor Rétvári: High Speed Networks Laboratory, Budapest University of Technology and Economics
Dmitri Krioukov: Northeastern University

Nature Communications, 2015, vol. 6, issue 1, 1-10

Abstract: 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.

Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.nature.com/articles/ncomms8651 Abstract (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nat:natcom:v:6:y:2015:i:1:d:10.1038_ncomms8651

Ordering information: This journal article can be ordered from
https://www.nature.com/ncomms/

DOI: 10.1038/ncomms8651

Access Statistics for this article

Nature Communications is currently edited by Nathalie Le Bot, Enda Bergin and Fiona Gillespie

More articles in Nature Communications from Nature
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().