Sesión Estadística, Probabilidad y Ciencias de DatosEstimadores por extensiones armónicas para el problema de detección de comunidades semi-supervisado en modelos estocásticos de bloques
Nicolás Agote
Universidad de Buenos Aries y Université de Toulouse, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
En esta comunicación vamos a estudiar el problema de detección de comunidades en modelos estocásticos de bloques (SBM por sus siglas en inglés) en el caso semi-supervisado.
Los modelos estocásticos de bloques son generalizaciones de los grafos de Erdős-Renyi que tienen una estructura de comunidades, en que distintos subconjuntos de nodos (llamados comunidades) tienen un comportamiento parecido a nivel de sus conexiones; en el caso asortativo, de nuestro interés, los nodos de una misma comunidad tienen más probabilidades de conectarse entre sí que con el resto de los nodos.
El problema de detección de comunidades consiste en dar estimadores que encuentren la partición subyacente de uno de estos grafos (por ejemplo, partiendo de su matriz de adyacencia). Podemos encontrar en la literatura muchos trabajos que estudian el problema en el caso no-supervisado; ver [1] para un resumen. En el caso semi-supervisado, se tiene acceso también a la comunidad de algunos pocos nodos en el grafo que podemos usar para hacer la estimación. En este paradigma encontramos artículos que estudian el problema en el caso en que la cantidad de nodos revelados es lineal en el tamaño de nodos en el grafo, por ejemplo: minimizando una energía [2], métodos espectrales [3, 4] y usando autofunciones del $p$-Laplaciano [5].
En nuestro trabajo, usamos paseos al azar para determinar para cada nodo qué comunidad tiene los nodos revelados más cercanos a él, y de esta manera estimamos la partición inducida. Damos resultados de consistencia (precisión asintótica para nuestros estimadores) y garantías de eficiencia al calcularlos. Como contribuciones principales a la literatura, nuestros métodos admiten una cantidad sub-lineal de nodos revelados para realizar la estimación, y adicionalmente permiten implementaciones eficientes para calcular las comunidades de pequeños subconjuntos de nodos.
Trabajo en conjunto con: Inés Armendáriz (Universidad de Buenos Aires), Pablo Ferrari (Universidad de Buenos Aires) y Florencia Leonardi (Universidade de São Paulo)..
Referencias
[1] Abbe, E. Community detection and stochastic block models: Recent developments. Journal of Machine Learning Research 18, 177 (2018), 1–86.
[2] Avrachenkov, K., and Dreveton, M. Almost Exact Recovery in Label Spreading. In WAW 2019 - 16th Workshop on Algorithms and Models for the Web Graph (Brisbane, Australia, July 2019).
[3] Fraiman, N., and Nisenzon, M. Semi-supervised community detection via quasi- stationary distributions, 2024.
[4] Gaudio, J., and Joshi, N. Exact community recovery (under side information): Optimality of spectral algorithms, 2024.
[5] Calder, J., and Drenska, N. Consistency of semi-supervised learning, stochastic tug-of-war games, and the p-laplacian, 2024.