{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T17:19:45Z","timestamp":1772903985832,"version":"3.50.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,10,22]],"date-time":"2018-10-22T00:00:00Z","timestamp":1540166400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Basic Research Program of China","doi-asserted-by":"crossref","award":["2014CB340400"],"award-info":[{"award-number":["2014CB340400"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Internet Technol."],"published-print":{"date-parts":[[2018,11,30]]},"abstract":"<jats:p>\n            Kleinberg proposed a family of small-world networks to explain the navigability of large-scale real-world social networks. However, the underlying mechanism that drives real networks to be navigable is not yet well understood. In this article, we present a game theoretic model for the formation of navigable small-world networks. We model the network formation as a game called the\n            <jats:italic>Distance-Reciprocity Balanced (DRB)<\/jats:italic>\n            game in which people seek for both high reciprocity and long-distance relationships. We show that the game has only two Nash equilibria: One is the navigable small-world network, and the other is the random network in which each node connects with each other node with equal probability, and any other network state can reach the navigable small world via a sequence of best-response moves of nodes. We further show that the navigable small-world equilibrium is very stable\u2014(a) no collusion of any size would benefit from deviating from it; and (b) after an arbitrary deviations of a large random set of nodes, the network would return to the navigable small world as soon as every node takes one best-response step. In contrast, for the random network, a small group collusion or random perturbations is guaranteed to bring the network out of the random-network equilibrium and move to the navigable network as soon as every node takes one best-response step. Moreover, we show that navigable small-world equilibrium has much better social welfare than the random network, and we provide the price-of-anarchy and price-of-stability results of the game. Our empirical evaluation further demonstrates that the system always converges to the navigable network even when limited or no information about other players\u2019 strategies is available, and the DRB game simulated on real-world networks leads to navigability characteristic that is very close to that of the real networks, even though the real-world networks have non-uniform population distributions different from Kleinberg\u2019s small-world model. Our theoretical and empirical analyses provide important new insight on the connection between distance, reciprocity, and navigability in social networks.\n          <\/jats:p>","DOI":"10.1145\/3183325","type":"journal-article","created":{"date-parts":[[2018,10,22]],"date-time":"2018-10-22T12:08:16Z","timestamp":1540210096000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Game Theoretic Model for the Formation of Navigable Small-World Networks\u2014The Tradeoff between Distance and Reciprocity"],"prefix":"10.1145","volume":"18","author":[{"given":"Zhi","family":"Yang","sequence":"first","affiliation":[{"name":"Peking University, Beijing, P.R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Chen","sequence":"additional","affiliation":[{"name":"Microsoft Research, Haidian District Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,10,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Lada Adamic and Eytan Adar. 2005. How to search a social network. Social Netw. 27 (2005).  Lada Adamic and Eytan Adar. 2005. How to search a social network. Social Netw. 27 (2005).","DOI":"10.1016\/j.socnet.2005.01.007"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/02\/P02002"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys1130"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_12"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2013.828336"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020579"},{"key":"e_1_2_1_7_1","unstructured":"Aaron Clauset and Cristopher Moore. 2003. How do networks become navigable. In Arxiv Preprint arXiv:0309.415v2.  Aaron Clauset and Cristopher Moore. 2003. How do networks become navigable. In Arxiv Preprint arXiv:0309.415v2."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4135\/9781452220567"},{"key":"e_1_2_1_9_1","unstructured":"Jacob Goldenberg and Moshe Levy. 2009. Distance is not dead: Social interaction and geographical distance in the internet era. In Arxiv preprint arXiv:0906.3202.  Jacob Goldenberg and Moshe Levy. 2009. Distance is not dead: Social interaction and geographical distance in the internet era. In Arxiv preprint arXiv:0906.3202."},{"key":"e_1_2_1_10_1","unstructured":"Marta C. Gonzlez Csar A. Hidalgo and Albert-Lszl Barabsi. 2008. Understanding individual human mobility patterns. Nature (2008).  Marta C. Gonzlez Csar A. Hidalgo and Albert-Lszl Barabsi. 2008. Understanding individual human mobility patterns. Nature (2008)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.2307\/2092623"},{"key":"e_1_2_1_12_1","unstructured":"Mark Granovetter. 1974. Getting a Job: A Study of Contacts and Careers. Harvard University Press.  Mark Granovetter. 1974. Getting a Job: A Study of Contacts and Careers. Harvard University Press."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Mark S. Granovetter. 1973. The strength of weak ties. Amer. J. Sociol. (1973) 1360--1380.  Mark S. Granovetter. 1973. The strength of weak ties. Amer. J. Sociol. (1973) 1360--1380.","DOI":"10.1086\/225469"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms8651"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2381056.2381069"},{"key":"e_1_2_1_16_1","unstructured":"Yanqing Hu Yougui Wang Daqing Li Shlomo Havlin and Zengru Di. 2011. Possible origin of efficient navigation in small worlds. Phys. Rev. Lett. (2011).  Yanqing Hu Yougui Wang Daqing Li Shlomo Havlin and Zengru Di. 2011. Possible origin of efficient navigation in small worlds. Phys. Rev. Lett. (2011)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11067-012-9180-4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Matthew O. Jackson. 2004. A survey of models of network formation: Stability and Efficiency. In Group Formation in Economics: Networks Clubs and Coalitions. Cambridge University Press Cambridge UK 11--57.  Matthew O. Jackson. 2004. A survey of models of network formation: Stability and Efficiency. In Group Formation in Economics: Networks Clubs and Coalitions. Cambridge University Press Cambridge UK 11--57.","DOI":"10.1017\/CBO9780511614385.002"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1348549.1348556"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879190"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335325"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the International Congress of Mathematicians (ICM\u201906)","author":"Kleinberg Jon","year":"2006"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Gautier Krings Francesco Calabrese Carlo Ratti and Vincent D. Blondel. 2009. Urban gravity: A model for intercity telecommunication flows. J. Stat. Mech.-Theor. Exp. (2009).  Gautier Krings Francesco Calabrese Carlo Ratti and Vincent D. Blondel. 2009. Urban gravity: A model for intercity telecommunication flows. J. Stat. Mech.-Theor. Exp. (2009).","DOI":"10.1088\/1742-5468\/2009\/07\/L07003"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.82.036106"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.035101"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Renaud Lambiotte et al. 2008. Geographical dispersal of mobile communication networks. Physica A 387 (2008).  Renaud Lambiotte et al. 2008. Geographical dispersal of mobile communication networks. Physica A 387 (2008).","DOI":"10.1016\/j.physa.2008.05.014"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0503018102"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.63.021117"},{"key":"e_1_2_1_29_1","first-page":"60","article-title":"The small world problem","volume":"2","author":"Milgram Stanley","year":"1967","journal-title":"Psychol. Today"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1833515.1833893"},{"key":"e_1_2_1_32_1","unstructured":"Oskar Sandberg and Ian Clarke. 2006. The evolution of navigable small-world networks. In Arxiv Preprint arXiv:cs\/0607025.  Oskar Sandberg and Ian Clarke. 2006. The evolution of navigable small-world networks. In Arxiv Preprint arXiv:cs\/0607025."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1177\/0146167295218002"},{"key":"e_1_2_1_34_1","volume-title":"Algorithmic Game Theory","author":"Tardos \u00c9va"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of \u2018small-world\u2019 networks. Nature 393 6684 (1998) 440--442.  Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of \u2018small-world\u2019 networks. Nature 393 6684 (1998) 440--442.","DOI":"10.1038\/30918"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2068816.2068841"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Kai Zhao Mirco Musolesi Pan Hui Weixiong Rao and Sasu Tarkoma. 2015. Explaining the power-law distribution of human mobility through transportation modality decomposition. Sci. Rep. (2015).  Kai Zhao Mirco Musolesi Pan Hui Weixiong Rao and Sasu Tarkoma. 2015. Explaining the power-law distribution of human mobility through transportation modality decomposition. Sci. Rep. (2015).","DOI":"10.1038\/srep09136"}],"container-title":["ACM Transactions on Internet Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3183325","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3183325","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:13Z","timestamp":1750210753000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3183325"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,22]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,11,30]]}},"alternative-id":["10.1145\/3183325"],"URL":"https:\/\/doi.org\/10.1145\/3183325","relation":{},"ISSN":["1533-5399","1557-6051"],"issn-type":[{"value":"1533-5399","type":"print"},{"value":"1557-6051","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,22]]},"assertion":[{"value":"2017-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}