Modeling and Algorithmic Advances for Random Dot Product Graphs

El Área de Matemática del PEDECIBA invita a la defensa de tesis de Doctorado en Matemática del estudiante

Bernardo Marenco Pence

titulada "Modeling and Algorithmic Advances for Random Dot Product Graphs "

Tutor: Dra. Paola Bermolen y Dr. Gonzalo Mateos

Tribunal: Florencia Leonardi (USP, Brasil), Joaquín Fontbona (Universidad de Chile y
Centro de Modelado Matemático, Chile), Vince Lyzinsky (University of Maryland, USA),
Mauricio Velasco (CMAT, UdelaR), Santiago Segarra (Rice University, USA)

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.