Nous nous intéressons à la complexité de recherche d'un noeud donné dans un graphe sans-échelle, en utilisant uniquement des informations locales. Pour les modèles généralisant les modèles de Barabási-Albert et de Cooper-Frieze, nous prouvons une borne inférieure de Omega(n^{1/2}) sur le nombre de sommets à visiter pour trouver le n-ième sommet inséré dans un modèle de connaissance locale faible.