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, 2001.
DOI : 10.1103/PhysRevE.64.046135

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

A. Barabási and R. Albert, Emergence of Scaling in Random Networks, Science, vol.286, p.509, 1999.

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

M. Dietzfelbinger, J. Rowe, I. Wegener, and P. Woefel, 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

M. Peter-sheridan-dodds, . Roby, J. Duncan, and . 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.

L. Scott and . Feld, Why Your Friends Have More Friends Than You Do, The American Journal of Sociology, vol.96, issue.6, pp.1464-1477, 1991.

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

P. Fraigniaud and G. Giakkoupis, Greedy routing in small-world networks with power-law degrees, Distributed Computing, vol.393, issue.2
DOI : 10.1007/s00446-014-0210-y

URL : https://hal.archives-ouvertes.fr/hal-01097141

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.27103, 2002.
DOI : 10.1103/PhysRevE.65.027103

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, Navigation in a small world, Nature, vol.406, issue.6798, p.845, 2000.
DOI : 10.1038/35022643

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, International Congress of Mathematicians (ICM), pp.1019-1044, 2006.
DOI : 10.4171/022-3/50

S. Lattanzi, A. Panconesi, and D. Sivakumar, Milgram-routing in social networks, Proceedings of the 20th international conference on World wide web, WWW '11, pp.725-734, 2011.
DOI : 10.1145/1963405.1963507

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 th USA, pp.11623-11628, 2005.
DOI : 10.1073/pnas.0503018102

G. Singh-manku, M. Naor, and U. Wieder, Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks, Proceedings of the 36nd ACM Symposium on Theory of Computing (STOC), pp.54-63, 2004.

G. Singh and M. , Routing networks for distributed hash tables, Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (PODC), pp.133-142, 2003.

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 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.311-320, 2005.

S. Milgram, The small world problem, Psychology Today, vol.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, International Joint Conferences on Artificial Intelligence (IJCAI), pp.304-310, 2005.

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