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

L. A. Adamic, R. M. Lukose, A. R. Puniyani, and B. A. Huberman, Search in power-law networks, Physical Review E, vol.64, issue.4, p.135, 2001.
DOI : 10.1103/PhysRevE.64.046135

R. Albert and A. L. 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. Backstrom, P. Boldi, M. Rosa, J. Ugander, and S. Vigna, Four degrees of separation, Proceedings of the 3rd Annual ACM Web Science Conference on, WebSci '12, pp.33-42, 2012.
DOI : 10.1145/2380718.2380723

L. Barrì-ere, P. Fraigniaud, E. Kranakis, and D. Krizanc, Efficient routing in networks with long range contacts, Proceedings of the 15th International Symposium on Distributed Computing (DISC), pp.270-284, 2001.

B. Bollobás and O. Riordan, The Diameter of a Scale-Free Random Graph, Combinatorica, vol.24, issue.1, pp.5-34, 2004.
DOI : 10.1007/s00493-004-0002-2

F. R. Chung and L. Lu, The Average Distance in a Random Graph with Given Expected Degrees, Internet Mathematics, vol.1, issue.1, pp.91-113, 2003.
DOI : 10.1080/15427951.2004.10129081

D. Coppersmith, D. Gamarnik, and M. Sviridenko, The diameter of a long-range percolation graph, Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.329-337, 2002.
DOI : 10.1002/rsa.10042

M. Dietzfelbinger, J. Rowe, I. Wegener, and P. Woelfel, Tight Bounds for Blind Search on the Integers and the Reals, Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS), pp.241-252, 2008.
DOI : 10.1007/978-3-540-24854-5_74

M. Dietzfelbinger and P. Woelfel, Tight lower bounds for greedy routing in uniform small world rings, Proceedings of the 41st annual ACM symposium on Symposium on theory of computing, STOC '09, pp.591-600, 2009.
DOI : 10.1145/1536414.1536494

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

S. N. Dorogovtsev and J. F. Mendes, Evolution of networks: From biological networks to the Internet and WWW, 2003.

P. Duchon, N. Hanusse, E. Lebhar, and N. Schabanel, Could any graph be turned into a small-world?, Proceedings of the 19th International Symposium on Distributed Computing (DISC), pp.511-513, 2005.
URL : https://hal.archives-ouvertes.fr/hal-00307532

M. Flammini, L. Moscardelli, A. Navarra, and S. Pérennes, Asymptotically optimal solutions for small world graphs, Proceedings of the 19th International Symposium on Distributed Computing (DISC), pp.414-428, 2005.

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

P. Fraigniaud, C. Gavoille, and C. Paul, Eclecticism shrinks even small worlds, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing , PODC '04, pp.169-178, 2004.
DOI : 10.1145/1011767.1011793
URL : https://hal.archives-ouvertes.fr/hal-00307394

P. Fraigniaud and G. Giakkoupis, The effect of power-law degrees on the navigability of small worlds, Proceedings of the 28th ACM symposium on Principles of distributed computing, PODC '09, pp.240-249, 2009.
DOI : 10.1145/1582716.1582755

P. Fraigniaud and G. Giakkoupis, On the searchability of small-world networks with arbitrary underlying structure, Proceedings of the 42nd ACM symposium on Theory of computing, STOC '10, pp.389-398, 2010.
DOI : 10.1145/1806689.1806744

G. Giakkoupis and V. Hadzilacos, On the complexity of greedy routing in ring-based peer-to-peer networks, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, PODC '07, pp.99-108, 2007.
DOI : 10.1145/1281100.1281117

G. Giakkoupis and N. Schabanel, Optimal path search in small worlds, Proceedings of the 43rd annual ACM symposium on Theory of computing, STOC '11, pp.393-402, 2011.
DOI : 10.1145/1993636.1993689

B. Kim, C. Yoon, S. Han, and H. Jeong, Path finding strategies in scale-free networks, Physical Review E, vol.65, issue.2, p.103, 2002.
DOI : 10.1103/PhysRevE.65.027103

J. Kleinberg, Navigation in a small world, Nature, vol.406, issue.6798, p.845, 2000.
DOI : 10.1038/35022643

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, Small-world phenomena and the dynamics of information, Advances in Neural Information Processing Systems (NIPS) 14, pp.431-438, 2001.

J. Kleinberg, Complex networks and decentralized search algorithms, Proceedings of 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

S. Lattanzi, A. Panconesi, and D. Sivakumar, Milgramrouting in social networks, Proceedings of the 20th ACM International Conference on World Wide Web (WWW), pp.725-734, 2011.

E. Lebhar and N. Schabanel, Almost Optimal Decentralized Routing in Long-Range Contact Networks, Proceedings of the 31st International Colloquium on Automata , Languages, and Programming (ICALP), pp.894-905, 2004.
DOI : 10.1007/978-3-540-27836-8_75

D. Liben-nowell, J. Novak, R. Kumar, P. Raghavan, and A. Tomkins, Geographic routing in social networks, Proceedings of the National Academy of Sciences of the USA102(33), pp.623-11628, 2005.
DOI : 10.1073/pnas.0503018102

G. S. Manku, M. Naor, and U. Wieder, Know thy neighbor's neighbor, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing , STOC '04, pp.54-63, 2004.
DOI : 10.1145/1007352.1007368

C. Martel and V. Nguyen, Analyzing Kleinberg's (and other) small-world Models, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing , PODC '04, pp.179-188, 2004.
DOI : 10.1145/1011767.1011794

C. Martel and V. Nguyen, Analyzing and characterizing small-world graphs, Proceedings of the 16th ACM- SIAM Symposium on Discrete Algorithms (SODA), pp.311-320, 2005.

S. Milgram, The small world problem, Psychology Today, vol.67, issue.1, pp.60-67, 1967.
DOI : 10.1037/e400002009-005

M. E. Newman, The Structure and Function of Complex Networks, SIAM Review, vol.45, issue.2, pp.167-256, 2003.
DOI : 10.1137/S003614450342480

N. Sarshar, P. O. Boykin, and V. P. Roychowdhury, Percolation search in power law networks: making unstructured peer-to-peer networks scalable, Proceedings. Fourth International Conference on Peer-to-Peer Computing, 2004. Proceedings., pp.2-9, 2004.
DOI : 10.1109/PTP.2004.1334925

¨. O. Simsek and D. Jensen, Decentralized search in networks using homophily and degree disparity, Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI), pp.304-310, 2005.

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. J. Watts and S. H. Strogatz, Collective dynamics of 'small-world' networks, Nature, vol.393, issue.6684, pp.440-442, 1998.
DOI : 10.1038/30918