{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T19:44:40Z","timestamp":1743104680962,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540705741"},{"type":"electronic","value":"9783540705758"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-70575-8_12","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"133-144","source":"Crossref","is-referenced-by-count":18,"title":["Networks Become Navigable as Nodes Move and Forget"],"prefix":"10.1007","author":[{"given":"Augustin","family":"Chaintreau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emmanuelle","family":"Lebhar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C.: Object Location Using Path Separators. In: 25th ACM Symp. on Principles of Distributed Computing (PODC), pp. 188\u2013197 (2006)","DOI":"10.1145\/1146381.1146411"},{"key":"12_CR2","doi-asserted-by":"publisher","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. Review of modern physics\u00a074, 47\u201397 (2002)","journal-title":"Review of modern physics"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Aspnes, J., Diamadi, Z., Shah, G.: Fault-tolerant routing in peer-to-peer systems. In: 21st ACM Symp. on Principles of Distributed Computing (PODC), pp. 223\u2013232 (2002)","DOI":"10.1145\/571825.571862"},{"key":"12_CR4","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)"},{"issue":"3","key":"12_CR5","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1137\/0401033","volume":"1","author":"B. Bollob\u00e1s","year":"1988","unstructured":"Bollob\u00e1s, B., Chung, F.: The diameter of a cycle plus a random matching. SIAM J. Discrete Math.\u00a01(3), 328\u2013333 (1988)","journal-title":"SIAM J. Discrete Math."},{"key":"12_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-3124-8","volume-title":"Markov Chains, Gibbs Field, Monte Carlo Simulation and Queues","author":"P. Bremaud","year":"1999","unstructured":"Bremaud, P.: Markov Chains, Gibbs Field, Monte Carlo Simulation and Queues. Springer, Heidelberg (1999)"},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"Chaintreau, A., Fraigniaud, P., Lebhar, E.: Opportunistic spatial gossip over mobile social networks. In: 1st ACM SIGCOMM Workshop on Online Social Net (WOSN) (to appear, 2008)","DOI":"10.1145\/1397735.1397752"},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"Chaintreau, A., Fraigniaud, P., Lebhar, E.: Networks Become Navigable as Nodes Move and Forget. Technical Report, arXiv:0803.0248v1 (2008)","DOI":"10.1007\/978-3-540-70575-8_12"},{"issue":"6","key":"12_CR9","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1109\/TMC.2007.1060","volume":"6","author":"A. Chaintreau","year":"2007","unstructured":"Chaintreau, A., Hui, P., Crowcroft, J., Diot, C., Scott, J., Gass, R.: Impact of Human Mobility on Opportunistic Forwarding Algorithms. IEEE Trans. Mob. Comp.\u00a06(6), 606\u2013620 (2007)","journal-title":"IEEE Trans. Mob. Comp."},{"key":"12_CR10","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.) Designing Privacy Enhancing Technologies. LNCS, vol.\u00a02009, pp. 46\u201366. Springer, Heidelberg (2001)"},{"key":"12_CR11","unstructured":"Clauset, A., Moore, C.: How Do Networks Become Navigable? Technical Report, arXiv:0309.415v2 (2003)"},{"issue":"1","key":"12_CR12","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1145\/43921.43922","volume":"22","author":"A. Demers","year":"1988","unstructured":"Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D., Terry, D.: Epidemic Algorithms for Replicated Database Maintenance. Operating Systems Review\u00a022(1), 8\u201332 (1988)","journal-title":"Operating Systems Review"},{"issue":"5634","key":"12_CR13","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"},{"key":"12_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77096-1_20","volume-title":"Principles of Distributed Systems","author":"P. Duchon","year":"2007","unstructured":"Duchon, P., Eggeman, N., Hanusse, N.: Non-Searchability of Random Power Law Graphs. In: Tovar, E., Tsigas, P., Fouchal, H. (eds.) OPODIS 2007. LNCS, vol.\u00a04878. Springer, Heidelberg (2007)"},{"issue":"1","key":"12_CR15","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":"12_CR16","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":"12_CR17","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":"12_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1163","DOI":"10.1007\/11549468_127","volume-title":"Euro-Par 2005 Parallel Processing","author":"P. Fraigniaud","year":"2005","unstructured":"Fraigniaud, P., Gauron, P., Latapy, M.: Combining the Use of Clustering and Scale-Free Nature of User Exchanges into a Simple and Efficient P2P System. In: Cunha, J.C., Medeiros, P.D. (eds.) Euro-Par 2005. LNCS, vol.\u00a03648, pp. 1163\u20131172. Springer, Heidelberg (2005)"},{"key":"12_CR19","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Gavoille, C., Kosowski, A., Lebhar, E., Lotker, Z.: Universal Augmentation Schemes for Network Navigability: Overcoming the ${\\sqrt{n}}$-Barrier. In: 19th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pp. 1\u20139 (2007)","DOI":"10.1145\/1248377.1248379"},{"key":"12_CR20","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(loglog n) for Augmented Graph Navigability. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 376\u2013386. Springer, Heidelberg (2006)"},{"key":"12_CR21","doi-asserted-by":"crossref","unstructured":"Giakkoupis, G., Hadzilacos, V.: On the complexity of greedy routing in ring-based peer-to-peer networks. In: 26th ACM Symp. on Princ. of Dist. Comp. (PODC) (2007)","DOI":"10.1145\/1281100.1281117"},{"issue":"4","key":"12_CR22","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1109\/TNET.2002.801403","volume":"10","author":"M. Grossglauser","year":"2002","unstructured":"Grossglauser, M., Tse, D.: Mobility Increases the Capacity of Ad Hoc Wireless Networks. IEEE\/ACM Trans. on Net.\u00a010(4), 477\u2013486 (2002)","journal-title":"IEEE\/ACM Trans. on Net."},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"Jain, S., Fall, K., Patra, R.: Routing in a delay tolerant network. In: Proc. ACM SIGCOMM (2004)","DOI":"10.1145\/1015467.1015484"},{"key":"12_CR24","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Demers, A.: Spatial gossip and resource location protocols. In: 33rd ACM Symposium on Theory of Computing, pp. 163\u2013172 (2001)","DOI":"10.1145\/380752.380796"},{"key":"12_CR25","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J.: Protocols and impossibility results for gossip-based communication mechanisms. In: 43st IEEE Symp. on Foundations of Computer Science, pp. 471\u2013480 (2002)","DOI":"10.1109\/SFCS.2002.1181971"},{"key":"12_CR26","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: The small-world phenomenon: an algorithmic perspective. In: 32nd ACM Symp. on Theory of Computing (STOC), pp. 163\u2013170 (2000)","DOI":"10.1145\/335305.335325"},{"key":"12_CR27","unstructured":"Kleinberg, J.: Complex networks and decentralized search algorithm. In: International Congress of Mathematicians (ICM), Madrid (2006)"},{"key":"12_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/11944836","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)"},{"issue":"7","key":"12_CR29","doi-asserted-by":"publisher","first-page":"1019","DOI":"10.1002\/asi.20591","volume":"58","author":"D. Liben-Nowell","year":"2007","unstructured":"Liben-Nowell, D., Kleinberg, J.: The link prediction problem for social networks. Journal of the American society for information science and technology\u00a058(7), 1019\u20131031 (2007)","journal-title":"Journal of the American society for information science and technology"},{"key":"12_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":"12_CR31","doi-asserted-by":"crossref","unstructured":"Milgram, S.: The Small-World Problem. Psychology Today, pp. 60\u201367 (1967)","DOI":"10.1037\/e400002009-005"},{"key":"12_CR32","doi-asserted-by":"crossref","unstructured":"Sandberg, O.: Neighbor Selection and Hitting Probability in Small-World Graphs. Annals of Applied Probability (to appear, 2008)","DOI":"10.1214\/07-AAP499"},{"key":"12_CR33","unstructured":"Sandberg, O., Clarke, I.: The evolution of navigable small-world networks. Tech. Report 2007:14, Chalmers University of Technology (2007)"},{"issue":"3\/4","key":"12_CR34","doi-asserted-by":"publisher","first-page":"425","DOI":"10.2307\/2333389","volume":"42","author":"H. Simon","year":"1955","unstructured":"Simon, H.: On a class of skew distribution functions. Biometrika\u00a042(3\/4), 425\u2013440 (1955)","journal-title":"Biometrika"},{"key":"12_CR35","doi-asserted-by":"crossref","unstructured":"Slivkins, A.: Distance estimation and object location via rings of neighbors. In: 24th Annual ACM Symp. on Princ. of Dist. Comp. (PODC), pp. 41\u201350 (2005)","DOI":"10.1145\/1073814.1073823"},{"key":"12_CR36","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 Small-World Networks. Nature\u00a0393, 440\u2013442 (1998)","journal-title":"Nature"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70575-8_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T12:12:57Z","timestamp":1738325577000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-70575-8_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540705741","9783540705758"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70575-8_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}