{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:09:19Z","timestamp":1763467759653},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540388753"},{"type":"electronic","value":"9783540388760"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11841036_44","type":"book-chapter","created":{"date-parts":[[2006,9,11]],"date-time":"2006-09-11T09:20:54Z","timestamp":1157966454000},"page":"480-491","source":"Crossref","is-referenced-by-count":14,"title":["Navigating Low-Dimensional and Hierarchical Population Networks"],"prefix":"10.1007","author":[{"given":"Ravi","family":"Kumar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Liben-Nowell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"Tomkins","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"44_CR1","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.socnet.2005.01.007","volume":"27","author":"L. Adamic","year":"2005","unstructured":"Adamic, L., Adar, E.: How to search a social network. Social Networks\u00a027(3), 187\u2013203 (2005)","journal-title":"Social Networks"},{"key":"44_CR2","volume-title":"Handbook of Graphs and Networks","author":"L. Adamic","year":"2002","unstructured":"Adamic, L., Lukose, R., Huberman, B.: Local search in unstructured networks. In: Handbook of Graphs and Networks. Wiley-VCH, Chichester (2002)"},{"key":"44_CR3","doi-asserted-by":"crossref","unstructured":"Adamic, L., Lukose, R., Puniyani, A., Huberman, B.: Search in power-law networks. Physical Review Letters E\u00a064(046135) (2001)","DOI":"10.1103\/PhysRevE.64.046135"},{"key":"44_CR4","doi-asserted-by":"crossref","unstructured":"Barri\u00e8re, L., Fraigniaud, P., Kranakis, E., Krizanc, D.: Efficient routing in networks with long range contacts. In: Proc.\u00a0Intl.\u00a0Conf.\u00a0on Distr.\u00a0Comp. (2001)","DOI":"10.1007\/3-540-45414-4_19"},{"issue":"1","key":"44_CR5","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/j.comgeo.2004.01.005","volume":"28","author":"E. Demaine","year":"2004","unstructured":"Demaine, E., Iacono, J., Langerman, S.: Proximate point searching. Computational Geometry: Theory and Applications\u00a028(1), 29\u201340 (2004)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"44_CR6","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1126\/science.1081058","volume":"301","author":"P. Dodds","year":"2003","unstructured":"Dodds, P., Muhamad, R., Watts, D.: An experimental study of search in global social networks. Science\u00a0301, 827\u2013829 (2003)","journal-title":"Science"},{"issue":"1","key":"44_CR7","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.tcs.2005.12.008","volume":"355","author":"P. Duchon","year":"2006","unstructured":"Duchon, P., Hanusse, N., Lebhar, E., Schabanel, N.: Could any graph be turned into a small world? Theoretical Computer Science\u00a0355(1), 96\u2013103 (2006)","journal-title":"Theoretical Computer Science"},{"key":"44_CR8","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P.: Greedy routing in tree-decomposed graphs. In: Proc. Eur. Symp. Alg. (2005)","DOI":"10.1007\/11561071_70"},{"key":"44_CR9","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Gavoille, C., Paul, C.: Eclecticism shrinks even small worlds. In: Proc.\u00a0Symp.\u00a0on Princ.\u00a0of Distr.\u00a0Comp. (2004)","DOI":"10.1145\/1011767.1011793"},{"key":"44_CR10","doi-asserted-by":"crossref","unstructured":"Iacono, J., Langerman, S.: Proximate planar point location. In: Proc. Symp. on Comp. Geom. (2003)","DOI":"10.1145\/777792.777826"},{"key":"44_CR11","unstructured":"Karp, B.: Geographic Routing for Wireless Networks. PhD thesis, Harvard (2000)"},{"key":"44_CR12","doi-asserted-by":"crossref","unstructured":"Karp, B., Kung, H.: GPSR: Greedy perimeter stateless routing for wireless networks. In: Proc. Intl. Conf. on Mobile Computing and Networking (2000)","DOI":"10.1145\/345910.345953"},{"key":"44_CR13","doi-asserted-by":"crossref","unstructured":"Kim, B., Yoon, C., Han, S., Jeong, H.: Path finding strategies in scale-free networks. Physical Review Letters E\u00a065(027103) (2002)","DOI":"10.1103\/PhysRevE.65.027103"},{"key":"44_CR14","unstructured":"Kim, Y., Govindan, R., Karp, B., Shenker, S.: Geographic routing made practical. In: Proc. Symp. on Networked Systems Design and Impl. (2005)"},{"key":"44_CR15","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1038\/35022643","volume":"406","author":"J. Kleinberg","year":"2000","unstructured":"Kleinberg, J.: Navigation in a small world. Nature\u00a0406, 845 (2000)","journal-title":"Nature"},{"key":"44_CR16","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: The small-world phenomenon: An algorithmic perspective. In: Proc. Symp. Theory of Comp. (2000)","DOI":"10.1145\/335305.335325"},{"key":"44_CR17","unstructured":"Kleinberg, J.: Small-world phenomena and the dynamics of information. In: Advances in Neural Information Processing (2001)"},{"key":"44_CR18","unstructured":"Kleinberg, J.: Complex networks and decentralized search algorithms. In: Proc.\u00a0International Congress of Mathematicians (2006)"},{"key":"44_CR19","doi-asserted-by":"crossref","unstructured":"Kumar, R., Liben-Nowell, D., Novak, J., Raghavan, P., Tomkins, A.: Theoretical analysis of geographic routing in social networks. TR MIT-CSAIL-TR-2005-040","DOI":"10.1073\/pnas.0503018102"},{"key":"44_CR20","doi-asserted-by":"crossref","unstructured":"Lebhar, E., Schabanel, N.: Close to optimal decentralized routing in long-range contact networks. In: Proc. Intl. Colloq. on Automata, Lang. and Prog. (2004)","DOI":"10.1007\/978-3-540-27836-8_75"},{"issue":"33","key":"44_CR21","doi-asserted-by":"publisher","first-page":"11623","DOI":"10.1073\/pnas.0503018102","volume":"102","author":"D. Liben-Nowell","year":"2005","unstructured":"Liben-Nowell, D., Novak, J., Kumar, R., Raghavan, P., Tomkins, A.: Geographic routing in social networks. Proc. Natl. Acad. Sciences\u00a0102(33), 11623\u201311628 (2005)","journal-title":"Proc. Natl. Acad. Sciences"},{"key":"44_CR22","doi-asserted-by":"crossref","unstructured":"Manku, G., Naor, M., Wieder, U.: Know thy neighbor\u2019s neighbor: the power of lookahead in randomized P2P networks. In: Proc. Symp. Theory of Comp. (2004)","DOI":"10.1145\/1007352.1007368"},{"key":"44_CR23","doi-asserted-by":"crossref","unstructured":"Martel, C., Nguyen, V.: Analyzing Kleinberg\u2019s (and other) small-world models. In: Proc. Symp. on Princ. of Distr. Comp. (2004)","DOI":"10.1145\/1011767.1011794"},{"key":"44_CR24","first-page":"61","volume":"1","author":"S. Milgram","year":"1967","unstructured":"Milgram, S.: The small world problem. Psychology Today\u00a01, 61\u201367 (1967)","journal-title":"Psychology Today"},{"key":"44_CR25","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge Univ. Press, Cambridge (1995)"},{"key":"44_CR26","unstructured":"Nguyen, V., Martel, C.: Analyzing and characterizing small-world graphs. In: Proc. Symp. on Disc. Alg. (2005)"},{"key":"44_CR27","unstructured":"\u015eim\u015fek, O., Jensen, D.: A probabilistic framework for decentralized search in networks. In: Proc. Intl. Joint Conf. on AI (2005)"},{"key":"44_CR28","doi-asserted-by":"crossref","unstructured":"Slivkins, A.: Distance estimation and object location via rings of neighbors. In: Proc.\u00a0Symp.\u00a0on Princ.\u00a0of Distr.\u00a0Comp. (2005)","DOI":"10.1145\/1073814.1073823"},{"key":"44_CR29","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511815478","volume-title":"Social Network Analysis","author":"S. Wasserman","year":"1994","unstructured":"Wasserman, S., Faust, K.: Social Network Analysis. Cambridge Univ. Press, Cambridge (1994)"},{"key":"44_CR30","doi-asserted-by":"publisher","first-page":"1302","DOI":"10.1126\/science.1070120","volume":"296","author":"D. Watts","year":"2002","unstructured":"Watts, D., Dodds, P., Newman, M.: Identity and search in social networks. Science\u00a0296, 1302\u20131305 (2002)","journal-title":"Science"},{"key":"44_CR31","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"D. Watts","year":"1998","unstructured":"Watts, D., Strogatz, S.: Collective dynamics of \u2018small-world\u2019 networks. Nature\u00a0393, 440\u2013442 (1998)","journal-title":"Nature"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11841036_44.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T14:40:32Z","timestamp":1605624032000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11841036_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540388753","9783540388760"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/11841036_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}