Reconstrucción de grafos hiperbólicos aleatorios

Abstract

En esta tesis se aborda el problema de la reconstrucción de grafos hiperbólicos aleatorios. El problema de reconstrucción, a grandes rasgos, consiste en determinar el conjunto de aristas de un grafo a partir de las etiquetas de sus vértices y del acceso a un oráculo que retorna el largo de un camino más corto en el grafo entre dos vértices, dadas sus etiquetas. El objetivo del problema es realizar la reconstrucción haciendo la menor cantidad posible de consultas al oráculo. El interés de investigar la reconstrucción de grafos hiperbólicos aleatorios (HRGs, por su sigla en inglés) radica en que estos son buenos modelos de redes complejas del mundo, tales como las redes sociales. En la literatura existen escasos trabajos que abordan el problema de reconstrucción de grafos aleatorios. No encontramos ninguno que abordara el problema para grafos cuya distribución de grados siga una ley de potencia ni (explícitamente) para grafos con geometría subyacente. Este trabajo es un primer paso para cerrar estas brechas de conocimiento. En el modelo de HRGs, los vértices están asociados a puntos del plano hiperbólico que se representa por R^2 usando coordenadas polares. Se sabe que si la coordenada radial de un vértice disminuye, entonces su grado aumenta, por lo tanto, a menor radio, mayor es el grado del vértice asociado. Entre los resultados de este estudio destacan el desarrollo de estrategias y algoritmos para encontrar estimaciones de los radios de los vértices de un HRG que tienen al menos cierto grado y con una cantidad cuasilineal de consultas al oráculo de distancia. Para lograrlo se establecieron y demostraron relaciones de utilidad, entre la coordenada radial de un vértice y el tamaño de su vecindad (restringida) y entre la distancia angular de dos vértices que corresponde a la diferencia entre sus coordenadas angulares y el tamaño de la intersección de sus vecindades. También se esboza una estrategia de cómo se pueden realizar estimaciones de la coordenada angular de los vértices de un HRG que poseen al menos cierto grado y con una cantidad cuasilineal de consultas al oráculo de distancia. Además, se realizó la estimación de la medida de la intersección de dos bolas centradas en puntos con coordenada radial similar. Otra contribución de este trabajo fue brindar una cota inferior (superlineal) al problema de la reconstrucción de HRGs, pero en un contexto no adversarial.