{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,25]],"date-time":"2026-10-25T22:38:01Z","timestamp":1792967881038,"version":"4.5.0"},"reference-count":9,"publisher":"National Academy of Sciences","issue":"35","content-domain":{"domain":["www.pnas.org"],"crossmark-restriction":true},"short-container-title":["Proc. Natl. Acad. Sci. U.S.A."],"published-print":{"date-parts":[[2008,9,2]]},"abstract":"<jats:p>Many large distributed systems can be characterized as networks where short paths exist between nearly every pair of nodes. These include social, biological, communication, and distribution networks, which often display power-law or small-world structure. A central challenge of distributed systems is directing messages to specific nodes through a sequence of decisions made by individual nodes without global knowledge of the network. We present a probabilistic analysis of this navigation problem that produces a surprisingly simple and effective method for directing messages. This method requires calculating only the product of the two measures widely used to summarize all local information. It outperforms prior approaches reported in the literature by a large margin, and it provides a formal model that may describe how humans make decisions in sociological studies intended to explore the social network as well as how they make decisions in more naturalistic settings.<\/jats:p>","DOI":"10.1073\/pnas.0800497105","type":"journal-article","created":{"date-parts":[[2008,8,25]],"date-time":"2008-08-25T21:09:32Z","timestamp":1219698572000},"page":"12758-12762","update-policy":"https:\/\/doi.org\/10.1073\/pnas.cm10313","source":"Crossref","is-referenced-by-count":89,"title":["Navigating networks by using homophily and degree"],"prefix":"10.1073","volume":"105","author":[{"given":"\u00d6zg\u00fcr","family":"\u015eim\u015fek","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Massachusetts, Amherst, MA 01003"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Jensen","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Massachusetts, Amherst, MA 01003"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"341","published-online":{"date-parts":[[2008,9,2]]},"reference":[{"key":"e_1_3_3_1_2","doi-asserted-by":"publisher","DOI":"10.2307\/2786545"},{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1081058"},{"key":"e_1_3_3_3_2","doi-asserted-by":"crossref","unstructured":"J Kleinberg The small-world phenomenon: An algorithmic perspective.  (ACM Press New York) pp. 163\u2013170 (2000).","DOI":"10.1145\/335305.335325"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1038\/35022643"},{"key":"e_1_3_3_5_2","first-page":"163","article-title":"Small-world phenomena and the dynamics of information","volume":"14","author":"Kleinberg J","year":"2001","unstructured":"J Kleinberg, Small-world phenomena and the dynamics of information. Adv Neural Info Processing Syst 14, 163\u2013170 (2001).","journal-title":"Adv Neural Info Processing Syst"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1070120"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.046135"},{"key":"e_1_3_3_8_2","volume-title":"Modern Information Retrieval","author":"Baeza-Yates R","year":"1999","unstructured":"R Baeza-Yates, B Ribeiro-Neto Modern Information Retrieval (Addison\u2014Wesley, Reading, MA, 1999)."},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(78)90018-7"}],"container-title":["Proceedings of the National Academy of Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pnas.org\/doi\/pdf\/10.1073\/pnas.0800497105","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,12]],"date-time":"2022-04-12T15:59:46Z","timestamp":1649779186000},"score":1,"resource":{"primary":{"URL":"https:\/\/pnas.org\/doi\/full\/10.1073\/pnas.0800497105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,9,2]]},"references-count":9,"journal-issue":{"issue":"35","published-print":{"date-parts":[[2008,9,2]]}},"alternative-id":["10.1073\/pnas.0800497105"],"URL":"https:\/\/doi.org\/10.1073\/pnas.0800497105","relation":{},"ISSN":["0027-8424","1091-6490"],"issn-type":[{"value":"0027-8424","type":"print"},{"value":"1091-6490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,9,2]]},"assertion":[{"value":"2008-01-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-09-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}