Modeling and Algorithmic Advances for Random Dot Product Graphs

Resumen: Las redes son una forma natural de representar sistemas complejos, desde interacciones sociales hasta conexiones biológicas y tecnológicas. Un potente modelo estadístico para estos datos es el Random Dot Product Graph (RDPG), donde cada nodo está asociado a un vector oculto y la probabilidad de una arista depende de la similitud de estos vectores. Esta tesis estudia cómo recuperar estas representaciones ocultas a partir de redes observadas, una tarea conocida como embedding de grafos.
Demostramos que, bajo el modelo RDPG, el problema de embedding puede considerarse un problema de optimización y proporcionamos resultados teóricos sobre su estructura, lo que explica la eficacia de algoritmos simples como el descenso de gradiente en este contexto. También ampliamos el modelo RDPG para gestionar grafos con pesos, lo que permite capturar patrones más ricos manteniendo garantías estadísticas. Finalmente, mostramos cómo estas herramientas pueden aplicarse a la detección en línea de cambios estructurales en redes dinámicas, de forma eficiente e interpretable.
En conjunto, la tesis combina ideas de estadística, optimización y teoría de grafos para avanzar en el aprendizaje de representaciones de grafos basadas en RDPGs.