{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T00:36:17Z","timestamp":1725842177258},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319267838"},{"type":"electronic","value":"9783319267845"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-26784-5_7","type":"book-chapter","created":{"date-parts":[[2015,12,9]],"date-time":"2015-12-09T10:07:47Z","timestamp":1449655667000},"page":"78-91","source":"Crossref","is-referenced-by-count":2,"title":["Navigability is a Robust Property"],"prefix":"10.1007","author":[{"given":"Dimitris","family":"Achlioptas","sequence":"first","affiliation":[]},{"given":"Paris","family":"Siminelakis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,12,9]]},"reference":[{"key":"7_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1007\/11561927_32","volume-title":"Distributed Computing","author":"I Abraham","year":"2005","unstructured":"Abraham, I., Gavoille, C., Malkhi, D.: Compact routing for graphs excluding a fixed minor. In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol. 3724, pp. 442\u2013456. Springer, Heidelberg (2005)"},{"key":"7_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/978-3-662-47666-6_37","volume-title":"Automata, Languages, and Programming","author":"D Achlioptas","year":"2015","unstructured":"Achlioptas, D., Siminelakis, P.: Symmetric graph properties have independent edges. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9135, pp. 467\u2013478. Springer, Heidelberg (2015)"},{"key":"7_CR3","volume-title":"The Probabilistic Method","author":"N Alon","year":"1992","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method. John Wiley, New York (1992)"},{"key":"7_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 Annual ACM Symposium on Principles of Distributed Computing, PODC 2002, pp. 223\u2013232 (2002)","DOI":"10.1145\/571860.571862"},{"key":"7_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/978-3-540-70575-8_12","volume-title":"Automata, Languages and Programming","author":"A Chaintreau","year":"2008","unstructured":"Chaintreau, A., Fraigniaud, P., Lebhar, E.: Networks become navigable as nodes move and forget. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 133\u2013144. Springer, Heidelberg (2008)"},{"key":"7_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/3-540-44702-4_4","volume-title":"Designing Privacy Enhancing Technologies","author":"I Clarke","year":"2001","unstructured":"Clarke, I., Sandberg, O., Wiley, B., Hong, T.W.: Freenet: a distributed anonymous information storage and retrieval system. In: Federrath, H. (ed.) Anonymity 2000. LNCS, vol. 2009, pp. 46\u201366. Springer, Heidelberg (2001)"},{"issue":"1","key":"7_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? Theor. Comput. Sci. 355(1), 96\u2013103 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"7_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1007\/11561071_70","volume-title":"Algorithms \u2013 ESA 2005","author":"P Fraigniaud","year":"2005","unstructured":"Fraigniaud, P.: Greedy routing in tree-decomposed graphs. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 791\u2013802. Springer, Heidelberg (2005)"},{"issue":"21\u201323","key":"7_CR9","doi-asserted-by":"publisher","first-page":"1970","DOI":"10.1016\/j.tcs.2008.12.061","volume":"410","author":"P Fraigniaud","year":"2009","unstructured":"Fraigniaud, P., Gavoille, C., Kosowski, A., Lebhar, E., Lotker, Z.: Universal augmentation schemes for network navigability. Theor. Comput. Sci. 410(21\u201323), 1970\u20131981 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"7_CR10","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 2010, pp. 389\u2013398 (2010)","DOI":"10.1145\/1806689.1806744"},{"issue":"1","key":"7_CR11","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1137\/06067626X","volume":"24","author":"P Fraigniaud","year":"2010","unstructured":"Fraigniaud, P., Lebhar, E., Lotker, Z.: A lower bound for network navigability. SIAM J. Discrete Math. 24(1), 72\u201381 (2010)","journal-title":"SIAM J. Discrete Math."},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: Complex networks and decentralized search algorithms. In: Proceedings of the International Congress of Mathematicians, ICM 2006, pp. 1019\u20131044 (2006)","DOI":"10.4171\/022-3\/50"},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.M.: The small-world phenomenon: an algorithmic perspective. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000, pp. 163\u2013170 (2000)","DOI":"10.1145\/335305.335325"},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.M.: Small-world phenomena and the dynamics of information. In: Proceedings of Advances in Neural Information Processing Systems 14, NIPS 2001, pp. 431\u2013438 (2001)","DOI":"10.7551\/mitpress\/1120.003.0060"},{"key":"7_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/978-3-540-92221-6_15","volume-title":"Principles of Distributed Systems","author":"E Lebhar","year":"2008","unstructured":"Lebhar, E., Schabanel, N.: Graph augmentation via metric embedding. In: Baker, T.P., Bui, A., Tixeuil, S. (eds.) OPODIS 2008. LNCS, vol. 5401, pp. 217\u2013225. Springer, Heidelberg (2008)"},{"issue":"33","key":"7_CR16","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. Sci. U.S.A. 102(33), 11623\u201311628 (2005)","journal-title":"Proc. Natl. Acad. Sci. U.S.A."},{"key":"7_CR17","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 Annual ACM Symposium on Theory of Computing, STOC 2004, pp. 54\u201363 (2004)","DOI":"10.1145\/1007352.1007368"},{"issue":"1","key":"7_CR18","first-page":"60","volume":"2","author":"S Milgram","year":"1967","unstructured":"Milgram, S.: The small world problem. Psychol. Today 2(1), 60\u201367 (1967)","journal-title":"Psychol. Today"},{"issue":"5","key":"7_CR19","doi-asserted-by":"publisher","first-page":"1771","DOI":"10.1214\/07-AAP499","volume":"18","author":"O Sandberg","year":"2008","unstructured":"Sandberg, O.: Neighbor selection and hitting probability in small-world graphs. Ann. Appl. Probab. 18(5), 1771\u20131793 (2008)","journal-title":"Ann. Appl. Probab."},{"issue":"4","key":"7_CR20","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/s00446-006-0015-8","volume":"19","author":"A Slivkins","year":"2007","unstructured":"Slivkins, A.: Distance estimation and object location via rings of neighbors. Distrib. Comput. 19(4), 313\u2013333 (2007)","journal-title":"Distrib. Comput."},{"key":"7_CR21","volume-title":"Six Degrees: The Science of a Connected Age","author":"DJ Watts","year":"2004","unstructured":"Watts, D.J.: Six Degrees: The Science of a Connected Age. WW Norton, New York (2004)"},{"key":"7_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/11576235_52","volume-title":"Parallel and Distributed Processing and Applications","author":"J Zeng","year":"2005","unstructured":"Zeng, J., Hsu, W.-J., Wang, J.: Near optimal routing in a small-world network with augmented local awareness. In: Pan, Y., Chen, D., Guo, M., Cao, J., Dongarra, J. (eds.) ISPA 2005. LNCS, vol. 3758, pp. 503\u2013513. Springer, Heidelberg (2005)"},{"issue":"4","key":"7_CR23","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1016\/j.comnet.2004.05.004","volume":"46","author":"H Zhang","year":"2004","unstructured":"Zhang, H., Goel, A., Govindan, R.: Using the small-world model to improve freenet performance. Comput. Netw. 46(4), 555\u2013574 (2004)","journal-title":"Comput. Netw."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Models for the Web Graph"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-26784-5_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,12]],"date-time":"2024-06-12T22:43:39Z","timestamp":1718232219000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-26784-5_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319267838","9783319267845"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-26784-5_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}