Estimación empírica del tamaño de la componente gigante de grafos aleatorios hiperbólicos

Abstract

Entender la topología de redes sociales es un problema importante, pues permite comprender mejor las relaciones e interacciones entre elementos de redes del mundo real. En este contexto, el modelo de grafo aleatorio hiperbólico (HRG por sus siglas en inglés) ha ganado popularidad desde comienzos de la década pasada. Además de ser manejable teóricamente, este modelo captura las propiedades más importantes que se observan en redes del mundo real. Sin embargo, trabajar con HRGs es desafiante a nivel algorítmico debido a que muchos de los fenómenos asociados ocurren a escalas logarítmicas e incluso sub-logarítmicas, por lo que observarlos experimentalmente requiere generar instancias prohibitivamente grandes. Por otra parte, la componente gigante es un elemento que ha llamado la atención desde el surgimiento de la teoría de grafos aleatorios. En la teoría de redes, el tamaño de la componente gigante proporciona información sobre la conectividad y la robustez de la red, mientras que en la teoría de percolación describe cómo se comporta la red al agregar nodos o enlaces. Actualmente se desconoce el valor preciso (en función de los parámetros del modelo) de la fracción de vértices que pertenecen a la componente gigante de un HRG. Estimar empíricamente esta fracción es el principal propósito de este trabajo. Para lograr nuestro objetivo, adaptamos un algoritmo conocido de generación eficiente de HRGs a uno similar, pero de generación de una clase adecuada de subgrafos inducidos. Mediante programación dinámica y la clasificación de los vértices en celdas que particionan el espacio hiperbólico subyacente en el que está incrustado el HRG, obtenemos un algoritmo eficiente en la práctica y cuya complejidad de tiempo es lineal en el número esperado de aristas del subgrafo inducido. Lo anterior fue respaldado tanto por un análisis teórico como experimental. Para controlar el error de la estimación empírica del tamaño de la componente gigante a partir de subgrafos apropiadamente elegidos, extendemos cada uno de estos con una estructura denominada escalera. Explotando propiedades de estas extensiones, demostramos que, con probabilidad 1 − o(1), es factible estimar (salvo por un error de o(1)) la fracción de vértices pertenecientes a la componente gigante de un HRG cuyo número esperado de vértices es n, pero muestreando subgrafos inducidos con un número esperado de vértices polilogarítmico en n. Finalmente, bajo conjeturas plausibles, construimos un intervalo de confianza para la fracción de vértices pertenecientes a la componente gigante.