I. Abraham and C. Gavoille, Object location using path separators, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing , PODC '06, pp.188-197, 2006.
DOI : 10.1145/1146381.1146411
URL : https://hal.archives-ouvertes.fr/hal-00400425

R. Albert and A. Barabási, Statistical mechanics of complex networks, Reviews of Modern Physics, vol.74, issue.1, pp.47-97, 2002.
DOI : 10.1103/RevModPhys.74.47

J. Aspnes, Z. Diamadi, and G. Shah, Fault-tolerant routing in peer-to-peer systems, Proceedings of the twenty-first annual symposium on Principles of distributed computing , PODC '02, pp.223-232, 2002.
DOI : 10.1145/571825.571862

L. Barrì-ere, P. Fraigniaud, E. Kranakis, and D. Krizanc, Efficient Routing in Networks with Long Range Contacts, 15th International Symposium on Distributed Computing (DISC), pp.270-284, 2001.

B. Bollobás and F. Chung, The Diameter of a Cycle Plus a Random Matching, SIAM Journal on Discrete Mathematics, vol.1, issue.3, pp.328-333, 1988.
DOI : 10.1137/0401033

P. Bremaud, Markov Chains, Gibbs Field, Monte Carlo Simulation and Queues, 1999.

A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, J. Scott et al., Impact of Human Mobility on Opportunistic Forwarding Algorithms, IEEE Transactions on Mobile Computing, vol.6, issue.6, pp.606-620, 2007.
DOI : 10.1109/TMC.2007.1060

I. Clarke, O. Sandberg, B. Wiley, and T. W. Hong, Freenet: A Distributed Anonymous Information Storage and Retrieval System, Workshop on Design Issues in Anonymity and Unobservability, pp.46-66, 2001.
DOI : 10.1007/3-540-44702-4_4

A. Clauset and C. Moore, How Do Networks Become Navigable?, 2003.

A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson et al., Epidemic algorithms for replicated database maintenance, ACM SIGOPS Operating Systems Review, vol.22, issue.1, pp.8-32, 1988.
DOI : 10.1145/43921.43922

P. Dodds, R. Muhamad, and D. Watts, An Experimental Study of Search in Global Social Networks, Science, vol.301, issue.5634, pp.827-829, 2003.
DOI : 10.1126/science.1081058

P. Duchon, N. Eggeman, and N. Hanusse, Non-Searchability of Random Power-Law Graphs, 11th Int. Conference on Principles of Distributed Systems (OPODIS), 2007.
DOI : 10.1007/978-3-540-77096-1_20
URL : https://hal.archives-ouvertes.fr/hal-00307148

P. Duchon, N. Hanusse, E. Lebhar, and N. Schabanel, Could any graph be turned into a small-world?, Theoretical Computer Science, vol.355, issue.1, pp.96-103, 2006.
DOI : 10.1016/j.tcs.2005.12.008
URL : https://hal.archives-ouvertes.fr/hal-00307532

M. Flammini, L. Moscardelli, A. Navarra, and S. Perennes, Asymptotically optimal solutions for small world graphs, 19th International Symposium on Distributed Computing (DISC), pp.414-428, 2005.
DOI : 10.1007/11561927_30

P. Fraigniaud, Greedy Routing in Tree-Decomposed Graphs, 13th Annual European Symposium on Algorithms (ESA), pp.791-802, 2005.
DOI : 10.1007/11561071_70

P. Fraigniaud, P. Gauron, and M. Latapy, Combining the Use of Clustering and Scale-Free Nature of User Exchanges into a Simple and Efficient P2P System, 11th European Conference on Parallel Computing (EuroPar), pp.1163-1172, 2005.
DOI : 10.1007/11549468_127

P. Fraigniaud, C. Gavoille, A. Kosowski, E. Lebhar, and Z. Lotker, Universal augmentation schemes for network navigability, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures , SPAA '07, pp.1-9, 2007.
DOI : 10.1145/1248377.1248379
URL : https://hal.archives-ouvertes.fr/hal-00998529

P. Fraigniaud, E. Lebhar, and Z. Lotker, A doubling dimension threshold ?(log log n) for augmented graph navigability, 14th European Symposium on Algorithm (ESA), pp.376-386, 2006.

G. Giakkoupis and V. Hadzilacos, On the complexity of greedy routing in ringbased peer-to-peer networks, 26th ACM Symposium on Principles of Distributed Computing (PODC), 2007.

M. Grossglauser and D. Tse, Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Transactions on Networking, vol.10, issue.4, pp.477-486, 2002.
DOI : 10.1109/TNET.2002.801403

S. Jain, K. Fall, and R. Patra, Routing in a delay tolerant network, Proc. ACM SIGCOMM, 2004.

D. Kempe, J. Kleinberg, and A. Demers, Spatial gossip and resource location protocols, 33rd ACM Symposium on Theory of Computing, pp.163-172, 2001.
DOI : 10.1145/1039488.1039491
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.111.8038

D. Kempe and J. Kleinberg, Protocols and impossibility results for gossip-based communication mechanisms, The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pp.471-480, 2002.
DOI : 10.1109/SFCS.2002.1181971
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.996

J. Kleinberg, The small-world phenomenon, Proceedings of the thirty-second annual ACM symposium on Theory of computing , STOC '00, pp.163-170, 2000.
DOI : 10.1145/335305.335325

J. Kleinberg, Complex networks and decentralized search algorithms, Nevanlinna prize presentation at the International Congress of Mathematicians (ICM), 2006.
DOI : 10.4171/022-3/50
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.62.410

R. Kumar, D. Liben-nowell, and A. Tomkins, Navigating Low-Dimensional and Hierarchical Population Networks, 14th European Symposium on Algorithm (ESA), 2006.
DOI : 10.1007/11841036_44
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.330.4349

D. Liben-nowell and J. Kleinberg, The link prediction problem for social networks Journal of the American society for information science and technology, pp.1019-1031, 2007.

S. Milgram, The Small-World Problem, Psychology Today, pp.60-67, 1967.
DOI : 10.1037/e400002009-005

R. Motwani and P. Raghavan, Randomized algorithms, 1995.

O. Sandberg, Neighbor selection and hitting probability in small-world graphs, The Annals of Applied Probability, vol.18, issue.5
DOI : 10.1214/07-AAP499

O. Sandberg and I. Clarke, The evolution of navigable small-world networks, 2007.

H. Simon, ON A CLASS OF SKEW DISTRIBUTION FUNCTIONS, Biometrika, vol.42, issue.3-4, pp.425-440, 1955.
DOI : 10.1093/biomet/42.3-4.425

A. Slivkins, Distance estimation and object location via rings of neighbors, Proceedings of the twenty-fourth annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing , PODC '05, pp.41-50, 2005.
DOI : 10.1145/1073814.1073823

D. Watts and S. Strogatz, Collective Dynamics of Small-World Networks, Nature, vol.393, issue.6684, pp.440-442, 1998.
DOI : 10.1038/30918