{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:16:57Z","timestamp":1725491817379},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540755197"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-75520-3_2","type":"book-chapter","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T03:46:33Z","timestamp":1189741593000},"page":"2-11","source":"Crossref","is-referenced-by-count":8,"title":["Small Worlds as Navigable Augmented Networks: Model, Analysis, and Validation"],"prefix":"10.1007","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1145\/1146381.1146411","volume-title":"PODC","author":"I. Abraham","year":"2006","unstructured":"Abraham, I., Gavoille, C.: Object Location Using Path Separators. In: PODC. 25th ACM Symp. on Principles of Distributed Computing, pp. 188\u2013197. ACM Press, New York (2006)"},{"key":"2_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1007\/11561927_47","volume-title":"Distributed Computing","author":"I. Abraham","year":"2005","unstructured":"Abraham, I., Malkhi, D., Manku, G.: Brief Announcement: Papillon: Greedy Routing in Rings. In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol.\u00a03724, pp. 514\u2013515. Springer, Heidelberg (2005)"},{"issue":"3","key":"2_CR3","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1080\/15427951.2005.10129109","volume":"2","author":"R. Andersen","year":"2006","unstructured":"Andersen, R., Chung, F., Lu, L.: Modeling the small-world phenomenon with local network flow. Internet Mathematics\u00a02(3), 359\u2013385 (2006)","journal-title":"Internet Mathematics"},{"key":"2_CR4","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1145\/571825.571862","volume-title":"PODC","author":"J. Aspnes","year":"2002","unstructured":"Aspnes, J., Diamadi, Z., Shah, G.: Fault-tolerant routing in peer-to-peer systems. In: PODC. 21st ACM Symp. on Principles of Distributed Computing, pp. 223\u2013232. ACM Press, New York (2002)"},{"key":"2_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/3-540-45414-4_19","volume-title":"Distributed Computing","author":"L. Barri\u00e8re","year":"2001","unstructured":"Barri\u00e8re, L., Fraigniaud, P., Kranakis, E., Krizanc, D.: Efficient Routing in Networks with Long Range Contacts. In: Welch, J.L. (ed.) DISC 2001. LNCS, vol.\u00a02180, pp. 270\u2013284. Springer, Heidelberg (2001)"},{"key":"2_CR6","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/978-3-540-44485-5_4","volume":"650","author":"F. Chung","year":"2004","unstructured":"Chung, F., Lu, L.: The small world phenomenon in hybrid power law graphs. Lect. Notes Phys.\u00a0650, 89\u2013104 (2004)","journal-title":"Lect. Notes Phys."},{"issue":"1","key":"2_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/rsa.10042","volume":"21","author":"D. Coppersmith","year":"2002","unstructured":"Coppersmith, D., Gamarnik, D., Sviridenko, M.: The Diameter of a Long-Range Percolation Graph. Random Structures and Algorithms\u00a021(1), 1\u201313 (2002)","journal-title":"Random Structures and Algorithms"},{"key":"2_CR8","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"B. Courcelle","year":"1998","unstructured":"Courcelle, B., Makowsky, J., Rotics, U.: Linear-time solvable optimization problems on graphs of bounded cliquewidth. In: Hromkovi\u010d, J., S\u00fdkora, O. (eds.) Graph-Theoretic Concepts in Computer Science. LNCS, vol.\u00a01517, pp. 1\u201316. Springer, Heidelberg (1998)"},{"issue":"5634","key":"2_CR9","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(5634), 827\u2013829 (2003)","journal-title":"Science"},{"issue":"1","key":"2_CR10","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":"2_CR11","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1145\/1148109.1148145","volume-title":"SPAA","author":"P. Duchon","year":"2006","unstructured":"Duchon, P., Hanusse, N., Lebhar, E., Schabanel, N.: Towards small world emergence. In: SPAA. 18th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 225\u2013232. ACM Press, New York (2006)"},{"key":"2_CR12","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/316188.316229","volume-title":"ACM SIGCOMM Conference","author":"M. Faloutsos","year":"1999","unstructured":"Faloutsos, M., Faloutsos, P., Faloutsos, C.: On Power-law Relationships of the Internet Topology. In: ACM SIGCOMM Conference, pp. 251\u2013262. ACM Press, New York (1999)"},{"key":"2_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1007\/11561927_30","volume-title":"Distributed Computing","author":"M. Flammini","year":"2005","unstructured":"Flammini, M., Moscardelli, L., Navarra, A., Perennes, S.: Asymptotically optimal solutions for small world graphs. In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol.\u00a03724, pp. 414\u2013428. Springer, Heidelberg (2005)"},{"key":"2_CR14","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: a new perspective on the small-world phenomenon. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 791\u2013802. Springer, Heidelberg (2005)"},{"key":"2_CR15","volume-title":"SPAA","author":"P. Fraigniaud","year":"2007","unstructured":"Fraigniaud, P., Gavoille, C., Kosowski, A., Lebhar, E., Lotker, Z.: Universal Augmentation Schemes for Network Navigability: Overcoming the $\\sqrt{n}$ -Barrier. In: SPAA. 19th ACM Symp. on Parallelism in Algorithms and Architectures, ACM Press, New York (2007)"},{"key":"2_CR16","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1145\/1011767.1011793","volume-title":"PODC","author":"P. Fraigniaud","year":"2004","unstructured":"Fraigniaud, P., Gavoille, C., Paul, C.: Eclecticism shrinks even small worlds. In: PODC. 23rd ACM Symposium on Principles of Distributed Computing, pp. 169\u2013178. ACM Press, New York (2004)"},{"key":"2_CR17","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Gavoille, C., Paul, C.: Eclecticism shrinks even small worlds. Distributed Computing\u00a018(4) (2006)","DOI":"10.1007\/s00446-005-0137-4"},{"key":"2_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/11841036_35","volume-title":"Algorithms \u2013 ESA 2006","author":"P. Fraigniaud","year":"2006","unstructured":"Fraigniaud, P., Lebhar, E., Lotker, Z.: A doubling dimension threshold \u0398(loglogn) for augmented graph navigability. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 376\u2013386. Springer, Heidelberg (2006)"},{"key":"2_CR19","unstructured":"Fraigniaud, P., Lebhar, E., Lotker, Z.: Recovering the Long Range Links in Augmented Graphs. Technical Report 6197, INRIA Paris-Rocquencourt (May 2007)"},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Lebhar, E., Viennot, L.: The Inframetric Model for the Internet. Technical Report, INRIA Paris-Rocquencourt (July 2007)","DOI":"10.1109\/INFOCOM.2008.163"},{"key":"2_CR21","volume-title":"PODC","author":"G. Giakkoupis","year":"2007","unstructured":"Giakkoupis, G., Hadzilacos, V.: On the complexity of greedy routing in ring-based peer-to-peer networks. In: PODC. 26th ACM Symposium on Principles of Distributed Computing, ACM Press, New York (2007)"},{"issue":"5","key":"2_CR22","doi-asserted-by":"publisher","first-page":"1148","DOI":"10.1137\/S0097539704446281","volume":"35","author":"S. Har-Peled","year":"2006","unstructured":"Har-Peled, S., Mendel, M.: Fast Construction of Nets in Low Dimensional Metrics, and Their Applications. SIAM J. on Computing\u00a035(5), 1148\u20131184 (2006)","journal-title":"SIAM J. on Computing"},{"key":"2_CR23","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1145\/509907.509918","volume-title":"STOC","author":"D. Karger","year":"2002","unstructured":"Karger, D., Ruhl, M.: Finding nearest neighbors in growth-restricted metrics. In: STOC. 34th ACM Symp. on the Theory of Computing, pp. 63\u201366. ACM Press, New York (2002)"},{"issue":"2","key":"2_CR24","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0378-8733(78)90018-7","volume":"1","author":"P. Killworth","year":"1978","unstructured":"Killworth, P., Bernard, H.: Reverse Small-World Experiment. Social Networks\u00a01(2), 159\u2013192 (1978)","journal-title":"Social Networks"},{"key":"2_CR25","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1145\/335305.335325","volume-title":"STOC","author":"J. Kleinberg","year":"2000","unstructured":"Kleinberg, J.: The Small-World Phenomenon: An Algorithmic Perspective. In: STOC. 32nd ACM Symp. on Theory of Computing, pp. 163\u2013170. ACM Press, New York (2000)"},{"key":"2_CR26","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":"2_CR27","unstructured":"Kleinberg, J.: Small-World Phenomena and the Dynamics of Information. In: 15th Neural Information Processing Systems (NIPS) (2001)"},{"key":"2_CR28","unstructured":"Kleinberg, J.: Complex networks and decentralized search algorithm. Nevanlinna prize presentation at the International Congress of Mathematicians (ICM), Madrid\u00a0 (2006)"},{"key":"2_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_44","volume-title":"Algorithms \u2013 ESA 2006","author":"R. Kumar","year":"2006","unstructured":"Kumar, R., Liben-Nowell, D., Tomkins, A.: Navigating Low-Dimensional and Hierarchical Population Networks. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, Springer, Heidelberg (2006)"},{"key":"2_CR30","doi-asserted-by":"crossref","unstructured":"Liben-Nowell, D., Novak, J., Kumar, R., Raghavan, P., Tomkins, A.: Geographic routing in social networks. In: Proc. of the Natl. Academy of Sciences of the USA, vol.\u00a0102\/3, pp. 11623\u201311628 (2005)","DOI":"10.1073\/pnas.0503018102"},{"key":"2_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"894","DOI":"10.1007\/978-3-540-27836-8_75","volume-title":"Automata, Languages and Programming","author":"E. Lebhar","year":"2004","unstructured":"Lebhar, E., Schabanel, N.: Searching for Optimal paths in long-range contact networks. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 894\u2013905. Springer, Heidelberg (2004)"},{"key":"2_CR32","unstructured":"Manku, G., Bawa, M., Raghavan, P.: Symphony: distributed hashing in a small world. In: 4th USENIX Symp. on Internet Technologies and Systems, pp. 127\u2013140 (2003)"},{"key":"2_CR33","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1145\/1007352.1007368","volume-title":"STOC","author":"G. Manku","year":"2004","unstructured":"Manku, G., Naor, M., Wieder, U.: Know Thy Neighbor\u2019s Neighbor: The Power of Lookahead in Randomized P2P Networks. In: STOC. 36th ACM Symp. on Theory of Computing, pp. 54\u201363. ACM Press, New York (2004)"},{"key":"2_CR34","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1145\/1011767.1011794","volume-title":"PODC","author":"C. Martel","year":"2004","unstructured":"Martel, C., Nguyen, V.: Analyzing Kleinberg\u2019s (and other) Small-world Models. In: PODC. 23rd ACM Symp. on Principles of Distributed Computing, pp. 179\u2013188. ACM Press, New York (2004)"},{"key":"2_CR35","first-page":"311","volume-title":"SODA","author":"C. Martel","year":"2005","unstructured":"Martel, C., Nguyen, V.: Analyzing and characterizing small-world graphs. In: SODA. 16th ACM-SIAM Symp. on Discrete Algorithms, pp. 311\u2013320. ACM Press, New York (2005)"},{"key":"2_CR36","volume-title":"INFOCOM","author":"C. Martel","year":"2006","unstructured":"Martel, C., Nguyen, V.: Designing networks for low weight, small routing diameter and low congestion. In: INFOCOM. 25th Conference of the IEEE Communications Society, IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"2_CR37","doi-asserted-by":"crossref","unstructured":"Milgram, S.: The Small-World Problem. Psychology Today, 60\u201367 (1967)","DOI":"10.1037\/e400002009-005"},{"key":"2_CR38","unstructured":"Peleg, D.: Private communication. Workshop of COST Action 295 \u201dDYNAMO\u201d, Les M\u00e9nuires\u00a0 (January 2006)"},{"issue":"3","key":"2_CR39","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/s002240000118","volume":"32","author":"G. Plaxton","year":"1999","unstructured":"Plaxton, G., Rajaraman, R., Richa, A.: Accessing Nearby Copies of Replicated Objects in a Distributed Environment. Theory of Computing Systems\u00a032(3), 241\u2013280 (1999)","journal-title":"Theory of Computing Systems"},{"key":"2_CR40","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors II, Algorithmic Aspects of Tree-Width. Journal of Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"key":"2_CR41","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/1073814.1073823","volume-title":"PODC","author":"A. Slivkins","year":"2005","unstructured":"Slivkins, A.: Distance estimation and object location via rings of neighbors. In: PODC. 24th Annual ACM Symposium on Principles of Distributed Computing, pp. 41\u201350. ACM Press, New York (2005)"},{"key":"2_CR42","first-page":"594","volume-title":"INFOCOM","author":"E. Zegura","year":"1996","unstructured":"Zegura, E., Calvert, K., Bhattacharjee, S.: How to Model an Internetwork. In: INFOCOM. 14th Conference of the IEEE Computer and Communications Societies, pp. 594\u2013602. IEEE Computer Society Press, Los Alamitos (1996)"},{"key":"2_CR43","doi-asserted-by":"crossref","unstructured":"Zhang, B., Ng, T., Nandi, A., Riedi, R., Druschel, P., Wang, G.: Measurement based analysis, modeling, and synthesis of the internet delay space. In: 6th Internet Measurement Conference (IMC), pp. 85\u201398 (2006)","DOI":"10.1145\/1177080.1177091"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-75520-3_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,14]],"date-time":"2023-05-14T04:13:21Z","timestamp":1684037601000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-75520-3_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540755197"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-75520-3_2","relation":{},"subject":[]}}