{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T18:16:11Z","timestamp":1780078571831,"version":"3.54.0"},"reference-count":37,"publisher":"Proceedings of the National Academy of Sciences","issue":"33","content-domain":{"domain":["www.pnas.org"],"crossmark-restriction":true},"short-container-title":["Proc. Natl. Acad. Sci. U.S.A."],"published-print":{"date-parts":[[2005,8,16]]},"abstract":"<jats:p>We live in a \u201csmall world,\u201d where two arbitrary people are likely connected by a short chain of intermediate friends. With scant information about a target individual, people can successively forward a message along such a chain. Experimental studies have verified this property in real social networks, and theoretical models have been advanced to explain it. However, existing theoretical models have not been shown to capture behavior in real-world social networks. Here, we introduce a richer model relating geography and social-network friendship, in which the probability of befriending a particular person is inversely proportional to the number of closer people. In a large social network, we show that one-third of the friendships are independent of geography and the remainder exhibit the proposed relationship. Further, we prove analytically that short chains can be discovered in every network exhibiting the relationship.<\/jats:p>","DOI":"10.1073\/pnas.0503018102","type":"journal-article","created":{"date-parts":[[2005,8,5]],"date-time":"2005-08-05T00:33:59Z","timestamp":1123202039000},"page":"11623-11628","update-policy":"https:\/\/doi.org\/10.1073\/pnas.cm10313","source":"Crossref","is-referenced-by-count":556,"title":["Geographic routing in social networks"],"prefix":"10.1073","volume":"102","author":[{"given":"David","family":"Liben-Nowell","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, Carleton College, 1 North College Street, Northfield, MN 55057; IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120; Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139; Yahoo! Research Labs, 701 First Avenue, Sunnyvale, CA 94089; and Verity, Inc., Sunnyvale, CA 94089"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jasmine","family":"Novak","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Carleton College, 1 North College Street, Northfield, MN 55057; IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120; Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139; Yahoo! Research Labs, 701 First Avenue, Sunnyvale, CA 94089; and Verity, Inc., Sunnyvale, CA 94089"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ravi","family":"Kumar","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Carleton College, 1 North College Street, Northfield, MN 55057; IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120; Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139; Yahoo! Research Labs, 701 First Avenue, Sunnyvale, CA 94089; and Verity, Inc., Sunnyvale, CA 94089"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prabhakar","family":"Raghavan","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Carleton College, 1 North College Street, Northfield, MN 55057; IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120; Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139; Yahoo! Research Labs, 701 First Avenue, Sunnyvale, CA 94089; and Verity, Inc., Sunnyvale, CA 94089"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew","family":"Tomkins","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Carleton College, 1 North College Street, Northfield, MN 55057; IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120; Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139; Yahoo! Research Labs, 701 First Avenue, Sunnyvale, CA 94089; and Verity, Inc., Sunnyvale, CA 94089"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"341","published-online":{"date-parts":[[2005,8,4]]},"reference":[{"key":"e_1_3_1_1_2","first-page":"61","volume":"1","year":"1967","unstructured":"Milgram, S. (1967) Psychol. Today 1, 61\u201367.","journal-title":"Psychol. Today"},{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.2307\/2786545"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1037\/h0029198"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(78)90018-7"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.046135"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.65.027103"},{"key":"e_1_3_1_7_2","doi-asserted-by":"crossref","unstructured":"Adamic L. A. Lukose R. M. & Huberman B. A. (2002) Local Search in Unstructured Networks (Wiley New York).","DOI":"10.1002\/3527602755.ch13"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1070120"},{"key":"e_1_3_1_9_2","unstructured":"Adamic L. A & Adar E. (2003) e-Print Archive http:\/\/www.arxiv.org\/abs\/cond-mat\/0310120."},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1038\/35022643"},{"key":"e_1_3_1_11_2","unstructured":"Kleinberg J. (2000) in Proceedings of the ACM Symposium on Theory of Computing ed. Yao F. (ACM Press New York) pp. 163\u2013170."},{"key":"e_1_3_1_12_2","first-page":"431","volume":"14","year":"2001","unstructured":"Kleinberg, J. (2001) Adv. Neural Infor. Process. 14, 431\u2013438.","journal-title":"Adv. Neural Infor. Process."},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1081058"},{"key":"e_1_3_1_14_2","unstructured":"Adamic L. A. & Huberman B. A. (2004) in Complex Networks eds. Ben-Naim E. Frauenfelder H. & Toroczkai Z. (Springer New York) No. 650 pp. 371\u2013398."},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.172501399"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1068\/b29118"},{"key":"e_1_3_1_17_2","unstructured":"Gastner M. T. & Newman M. E. J. (2004) e-Print Archive http:\/\/www.arxiv.org\/abs\/cond-mat\/0407680."},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.6028\/jres.106.017"},{"key":"e_1_3_1_19_2","unstructured":"United States Geological Survey (2000) 2000 Census (United States Geological Survey Reston VA)."},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_3_1_21_2","doi-asserted-by":"crossref","unstructured":"Wasserman S. & Faust K. (1994) Social Network Analysis (Cambridge Univ. Press Cambridge U.K.).","DOI":"10.1017\/CBO9780511815478"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-4371(99)00291-5"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129088"},{"key":"e_1_3_1_26_2","unstructured":"Cairncross F. (1997) The Death of Distance (Harvard Business School Press Boston)."},{"key":"e_1_3_1_27_2","unstructured":"Kiesler S. & Cummings J. N. (2002) in Distributed Work eds. Hinds P. & Kiesler S. (MIT Press Cambridge MA) pp. 57\u201382."},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224474"},{"key":"e_1_3_1_29_2","doi-asserted-by":"crossref","unstructured":"Barri\u00e9re L. Fraigniaud P. Kranakis E. & Krizanc D. (2001) in Proceedings of the International Conference on Distributed Computing ed. Welch J. (Springer London) pp. 270\u2013284.","DOI":"10.1007\/3-540-45414-4_19"},{"key":"e_1_3_1_30_2","unstructured":"Slivkins A. (2005) in Proceedings of the Symposium on Principles of Distributed Computing ed. Aspnes J. (ACM Press New York) pp. 41\u201350."},{"key":"e_1_3_1_31_2","unstructured":"Fraigniaud P Gavoille C & Paul C. (2004) in Proceedings of the Symposium on Principles of Distributed Computing ed. Kutten S. (ACM Press New York) pp. 169\u2013178."},{"key":"e_1_3_1_32_2","doi-asserted-by":"crossref","unstructured":"Fraigniaud P. (2005) A New Perspective on the Small-World Phenomenon: Greedy Routing in Tree-Decomposed Graphs Technical Report LRI-1397 (University Paris-Sud Paris).","DOI":"10.1007\/11561071_70"},{"key":"e_1_3_1_33_2","unstructured":"Martel C. & Nguyen V. (2004) in Proceedings of the Symposium on Principles of Distributed Computing ed. Kutten S. (ACM Press New York) pp. 179\u2013188."},{"key":"e_1_3_1_34_2","unstructured":"Nguyen V. & Martel C. (2005) in Proceedings of the Symposium on Discrete Algorithms ed. Buchsbaum A. (Society for Industrial and Applied Mathematics Philadelphia) pp. 311\u2013320."},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.60.7332"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.016122"},{"key":"e_1_3_1_37_2","doi-asserted-by":"crossref","unstructured":"Kumar R. Liben-Nowell D. Novak J. Raghavan P. & Tomkins A. (2005) Theoretical Analysis of Geographic Routing in Social Networks Technical Report MIT-LCS-TR-990 (MIT Press Cambridge MA).","DOI":"10.1073\/pnas.0503018102"}],"container-title":["Proceedings of the National Academy of Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pnas.org\/doi\/pdf\/10.1073\/pnas.0503018102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,28]],"date-time":"2024-01-28T15:37:14Z","timestamp":1706456234000},"score":1,"resource":{"primary":{"URL":"https:\/\/pnas.org\/doi\/full\/10.1073\/pnas.0503018102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,8,4]]},"references-count":37,"journal-issue":{"issue":"33","published-print":{"date-parts":[[2005,8,16]]}},"alternative-id":["10.1073\/pnas.0503018102"],"URL":"https:\/\/doi.org\/10.1073\/pnas.0503018102","relation":{},"ISSN":["0027-8424","1091-6490"],"issn-type":[{"value":"0027-8424","type":"print"},{"value":"1091-6490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,8,4]]},"assertion":[{"value":"2005-04-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2005-08-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}