{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T20:48:19Z","timestamp":1777668499961,"version":"3.51.4"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2014,4,22]],"date-time":"2014-04-22T00:00:00Z","timestamp":1398124800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2014,8]]},"DOI":"10.1007\/s00446-014-0210-y","type":"journal-article","created":{"date-parts":[[2014,4,21]],"date-time":"2014-04-21T18:55:17Z","timestamp":1398106517000},"page":"231-253","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Greedy routing in small-world networks with power-law degrees"],"prefix":"10.1007","volume":"27","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George","family":"Giakkoupis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,4,22]]},"reference":[{"key":"210_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C.: Object location using path separators. In: Proceedings of the 25th ACM Symposium on Principles of Distributed Computing (PODC), pp. 188\u2013197 (2006)","DOI":"10.1145\/1146381.1146411"},{"key":"210_CR2","doi-asserted-by":"crossref","first-page":"46135","DOI":"10.1103\/PhysRevE.64.046135","volume":"64","author":"LA Adamic","year":"2001","unstructured":"Adamic, L.A., Lukose, R.M., Puniyani, A.R., Huberman, B.A.: Search in power-law networks. Phys. Rev. E 64, 46135 (2001)","journal-title":"Phys. Rev. E"},{"issue":"1","key":"210_CR3","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","volume":"74","author":"R Albert","year":"2002","unstructured":"Albert, R., Barab\u00e1si, A.L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74(1), 47\u201397 (2002)","journal-title":"Rev. Mod. Phys."},{"key":"210_CR4","doi-asserted-by":"crossref","unstructured":"Aspnes, J., Diamadi, Z., Shah, G.: Fault-tolerant routing in peer-to-peer systems. In: Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC), pp. 223\u2013232 (2002)","DOI":"10.1145\/571825.571862"},{"key":"210_CR5","doi-asserted-by":"crossref","unstructured":"Backstrom, L., Boldi, P., Rosa, M., Ugander, J., Vigna, S.: Four degrees of separation. In: Proceedings of the 3rd ACM Web Science Conference (WebSci), pp. 33\u201342 (2012)","DOI":"10.1145\/2380718.2380723"},{"key":"210_CR6","doi-asserted-by":"crossref","unstructured":"Barri\u00e8re, L., Fraigniaud, P., Kranakis, E., Krizanc, D.: Efficient routing in networks with long range contacts. In: Proceedings of the 15th International Symposium on Distributed Computing (DISC), pp. 270\u2013284 (2001)","DOI":"10.1007\/3-540-45414-4_19"},{"issue":"1","key":"210_CR7","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/s00493-004-0002-2","volume":"24","author":"B Bollob\u00e1s","year":"2004","unstructured":"Bollob\u00e1s, B., Riordan, O.: The diameter of a scale-free random graph. Combinatorica 24(1), 5\u201334 (2004)","journal-title":"Combinatorica"},{"issue":"1","key":"210_CR8","first-page":"91","volume":"1","author":"FRK Chung","year":"2003","unstructured":"Chung, F.R.K., Lu, L.: The average distance in a random graph with given expected degrees. Intern Math 1(1), 91\u2013113 (2003)","journal-title":"Intern Math"},{"key":"210_CR9","doi-asserted-by":"crossref","unstructured":"Coppersmith, D., Gamarnik, D., Sviridenko, M.: The diameter of a long range percolation graph. In: Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 329\u2013337 (2002)","DOI":"10.1002\/rsa.10042"},{"key":"210_CR10","unstructured":"Dietzfelbinger, M., Rowe, J., Wegener, I., Woelfel, P.: Tight bounds for blind search on the integers. In: Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 241\u2013252 (2008)"},{"key":"210_CR11","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Woelfel, P.: Tight lower bounds for greedy routing in uniform small world rings. In: Proceedings of the 41st ACM Symposium on Theory of Computing (STOC), pp. 591\u2013600 (2009)","DOI":"10.1145\/1536414.1536494"},{"issue":"5634","key":"210_CR12","doi-asserted-by":"crossref","first-page":"827","DOI":"10.1126\/science.1081058","volume":"301","author":"PS Dodds","year":"2003","unstructured":"Dodds, P.S., Muhamad, R., Watts, D.J.: An experimental study of search in global social networks. Science 301(5634), 827\u2013829 (2003)","journal-title":"Science"},{"key":"210_CR13","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198515906.001.0001","volume-title":"Evolution of networks: from biological networks to the Internet and WWW","author":"SN Dorogovtsev","year":"2003","unstructured":"Dorogovtsev, S.N., Mendes, J.F.F.: Evolution of networks: from biological networks to the Internet and WWW. Oxford University Press, Oxford (2003)"},{"key":"210_CR14","doi-asserted-by":"crossref","unstructured":"Duchon, P., Hanusse, N., Lebhar, E., Schabanel, N.: Could any graph be turned into a small-world? In: Proceedings of the 19th International Symposium on Distributed Computing (DISC), pp. 511\u2013513 (2005)","DOI":"10.1007\/11561927_46"},{"key":"210_CR15","doi-asserted-by":"crossref","unstructured":"Flammini, M., Moscardelli, L., Navarra, A., P\u00e9rennes, S.: Asymptotically optimal solutions for small world graphs. In: Proceedings of the 19th International Symposium on Distributed Computing (DISC), pp. 414\u2013428 (2005)","DOI":"10.1007\/11561927_30"},{"key":"210_CR16","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P.: Greedy routing in tree-decomposed graphs. In: Proceedings of the 13th European Symposium on Algorithms (ESA), pp. 791\u2013802 (2005)","DOI":"10.1007\/11561071_70"},{"key":"210_CR17","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Gavoille, C., Paul, C.: Eclecticism shrinks even small worlds. In: Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 169\u2013178 (2004)","DOI":"10.1145\/1011767.1011793"},{"key":"210_CR18","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Giakkoupis, G.: The effect of power-law degrees on the navigability of small worlds. In: Proceedings of the 28th ACM Symposium on Principles of Distributed Computing (PODC), pp. 240\u2013249 (2009)","DOI":"10.1145\/1582716.1582755"},{"key":"210_CR19","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Giakkoupis, G.: On the searchability of small-world networks with arbitrary underlying structure. In: Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pp. 389\u2013398 (2010)","DOI":"10.1145\/1806689.1806744"},{"key":"210_CR20","doi-asserted-by":"crossref","unstructured":"Giakkoupis, G., Hadzilacos, V.: On the complexity of greedy routing in ring-based peer-to-peer networks. In: Proceedings of the 26th ACM Symposium on Principles of Distributed Computing (PODC), pp. 99\u2013108 (2007)","DOI":"10.1145\/1281100.1281117"},{"key":"210_CR21","doi-asserted-by":"crossref","unstructured":"Giakkoupis, G., Schabanel, N.: Optimal path search in small worlds: dimension matters. In: Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pp. 393\u2013402 (2011)","DOI":"10.1145\/1993636.1993689"},{"key":"210_CR22","doi-asserted-by":"crossref","first-page":"027103","DOI":"10.1103\/PhysRevE.65.027103","volume":"65","author":"B Kim","year":"2002","unstructured":"Kim, B., Yoon, C., Han, S., Jeong, H.: Path finding strategies in scale-free networks. Phys. Rev. E 65, 027103 (2002)","journal-title":"Phys. Rev. E"},{"key":"210_CR23","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1038\/35022643","volume":"406","author":"J Kleinberg","year":"2000","unstructured":"Kleinberg, J.: Navigation in a small world. Nature 406, 845 (2000)","journal-title":"Nature"},{"key":"210_CR24","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: The small-world phenomenon: An algorithmic perspective. In: Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC), pp. 163\u2013170 (2000)","DOI":"10.1145\/335305.335325"},{"key":"210_CR25","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: Small-world phenomena and the dynamics of information. In: Advances Neural Information Processing Systems (NIPS) 14, pp. 431\u2013438 (2001)","DOI":"10.7551\/mitpress\/1120.003.0060"},{"key":"210_CR26","unstructured":"Kleinberg, J.: Complex networks and decentralized search algorithms. In: Proceedings of the International Congress of Mathematicians (ICM) (2006)"},{"key":"210_CR27","doi-asserted-by":"crossref","unstructured":"Lattanzi, S., Panconesi, A., Sivakumar, D.: Milgram-routing in social networks. In: Proceedings of the 20th ACM International Conference on World Wide Web (WWW), pp. 725\u2013734 (2011)","DOI":"10.1145\/1963405.1963507"},{"key":"210_CR28","doi-asserted-by":"crossref","unstructured":"Lebhar, E., Schabanel, N.: Almost optimal decentralized routing in long-range contact networks. In: Proceedings of the 31st International Colloquium on Automata, Languages, and Programming (ICALP), pp. 894\u2013905 (2004)","DOI":"10.1007\/978-3-540-27836-8_75"},{"issue":"33","key":"210_CR29","doi-asserted-by":"crossref","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. Sci. USA 102(33), 11623\u201311628 (2005)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"210_CR30","doi-asserted-by":"crossref","unstructured":"Manku, G.S., Naor, M., Wieder, U.: Know thy neighbor\u2019s neighbor: the power of lookahead in randomized P2P networks. In: Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), pp. 54\u201363 (2004)","DOI":"10.1145\/1007352.1007368"},{"key":"210_CR31","doi-asserted-by":"crossref","unstructured":"Martel, C., Nguyen, V.: Analyzing Kleinberg\u2019s (and other) small-world models. In: Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 179\u2013188 (2004)","DOI":"10.1145\/1011767.1011794"},{"key":"210_CR32","unstructured":"Martel, C., Nguyen, V.: Analyzing and characterizing small-world graphs. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 311\u2013320 (2005)"},{"issue":"1","key":"210_CR33","first-page":"60","volume":"67","author":"S Milgram","year":"1967","unstructured":"Milgram, S.: The small world problem. Psychol. Today 67(1), 60\u201367 (1967)","journal-title":"Psychol. Today"},{"issue":"2","key":"210_CR34","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1137\/S003614450342480","volume":"45","author":"MEJ Newman","year":"2003","unstructured":"Newman, M.E.J.: The structure and function of complex networks. SIAM Rev. 45(2), 167\u2013256 (2003)","journal-title":"SIAM Rev."},{"key":"210_CR35","doi-asserted-by":"crossref","unstructured":"Sarshar, N., Boykin, P.O., Roychowdhury, V.P.: Percolation search in power law networks: Making unstructured peer-to-peer networks scalable. In: Proceedings of the 4th IEEE International Conference on Peer-to-Peer, Computing (P2P), pp. 2\u20139 (2004)","DOI":"10.1109\/PTP.2004.1334925"},{"key":"210_CR36","unstructured":"Simsek, \u00d6., Jensen, D.: Decentralized search in networks using homophily and degree disparity. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI), pp. 304\u2013310 (2005)"},{"key":"210_CR37","doi-asserted-by":"crossref","unstructured":"Slivkins, A.: Distance estimation and object location via rings of neighbors. In: Proceedings of the 24th ACM Symposium on Principles of Distributed Computing (PODC), pp. 41\u201350 (2005)","DOI":"10.1145\/1073814.1073823"},{"key":"210_CR38","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts, D.J., Strogatz, S.H.: Collective dynamics of \u2018small-world\u2019 networks. Nature 393, 440\u2013442 (1998)","journal-title":"Nature"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-014-0210-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-014-0210-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-014-0210-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T13:52:04Z","timestamp":1746193924000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-014-0210-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,4,22]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["210"],"URL":"https:\/\/doi.org\/10.1007\/s00446-014-0210-y","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,4,22]]}}}