Graph Seminars 8/4/2025

Título: Grafos aleatorios y detección de comunidades

Expone: Nicolás Agote

Resumen

Esta charla va a tener dos grandes temas.
El primero van a ser los grafos aleatorios. ¿Qué son? ¿Por qué están buenos? ¿Qué nos interesa conocer, y conocemos, de ellos? ¿Dónde han sido relevantes? En particular, vamos a discutir modelos como los grafos de Erdös-Renyi, modelo estocástico de bloques (SBM), modelos de configuración y generalizaciones, y grafos geométricos como el grafo de kk-vecinos más cercanos y el εε-grafo.

El segundo va a ser el problema de detección de comunidades en modelos SBM en el caso semi-supervisado, en el que voy a contar sobre algunos resultados que conseguimos con Inés Armendáriz (UBA), Pablo Ferrari (UBA) y Florencia Leonardi (USP). Los modelos estocásticos de bloques cumplen que hay clases de nodos, o comunidades, que tienen un comportamiento parecido a nivel de sus conexiones comunidad a comunidad, y el objetivo de nuestro trabajo es encontrarlos la partición subyacente usando poca información previa. Nuestro enfoque consiste en, dados algunos pocos nodos "referentes" de comunidad conicida, usar paseos al azar en el grafo para determinar para cada nodo cuál comunidad tiene los "referentes" más cercanos a él, y de esta manera elegir la partición inducida. Nuestros resultados principales son de consistencia, es decir, precisión asintótica, y de garantías de eficiencia al calcular los estimadores.