El objetivo de este artículo es cerrar la brecha entre dos direcciones de investigación importantes: (1) la búsqueda del vecino más cercano, que es una herramienta computacional fundamental para el análisis de grandes datos; y (2) el análisis de redes complejas, que trata con grandes grafos reales pero que generalmente se estudia a través de análisis teóricos de grafos o análisis espectral. En este artículo, hemos estudiado el problema de búsqueda del vecino más cercano en una red compleja mediante el desarrollo de una noción adecuada de cercanía. También se estudian y experimentan la computación de una búsqueda eficiente del vecino más cercano entre los nodos de una red compleja utilizando el árbol métrico y el hashing sensible a la localidad (LSH). Para la evaluación de la búsqueda propuesta del vecino más cercano en una red compleja, la aplicamos a un problema de detección de comunidades en redes. Se realizan experimentos para verificar la utilidad de las medidas de cercanía para las redes complejas, el papel del árbol métrico y LSH para calcular la cercanía de nodos de manera rápida y aproximada, y la eficiencia de la detección de comunidades utilizando la búsqueda del vecino más cercano. Observamos que la búsqueda del vecino más cercano entre los nodos de la red es una herramienta muy eficiente para explorar mejor la estructura de comunidad de las redes reales. Varios esquemas de aproximación eficientes son muy útiles para redes grandes, que apenas degradan los resultados, mientras que ahorran mucho tiempo computacional, y el enfoque de detección de comunidades basado en el vecino más cercano es muy competitivo en términos de eficiencia y tiempo.