El modelo de bloques estocásticos es un modelo generativo de gráficos aleatorios . Este modelo tiende a producir gráficos que contienen comunidades , subconjuntos caracterizados por estar conectados entre sí con densidades de bordes particulares. Por ejemplo, los bordes pueden ser más comunes dentro de las comunidades que entre comunidades. El modelo de bloques estocásticos es importante en estadísticas , aprendizaje automático y ciencia de redes , donde sirve como un punto de referencia útil para la tarea de recuperar la estructura de la comunidad en datos de gráficos.
Definición
El modelo de bloque estocástico toma los siguientes parámetros:
- El número de vértices;
- una partición del conjunto de vértices en subconjuntos disjuntos , llamadas comunidades ;
- un simétrico matriz de probabilidades de borde.
El conjunto de aristas se muestrea al azar de la siguiente manera: dos vértices cualesquiera y están conectados por una arista con probabilidad . Un problema de ejemplo es: dado un gráfico con vértices, donde los bordes se muestrean como se describe, recuperan los grupos .
Casos especiales
Si la matriz de probabilidad es una constante, en el sentido de que para todos , entonces el resultado es el modelo Erdős-Rényi . Este caso es degenerado —la división en comunidades se vuelve irrelevante— pero ilustra una estrecha relación con el modelo Erdős-Rényi.
El modelo de partición plantado es el caso especial de que los valores de la matriz de probabilidad son una constante en la diagonal y otra constante fuera de la diagonal. Por lo tanto, dos vértices dentro de la misma comunidad comparten una ventaja con probabilidad, mientras que dos vértices en diferentes comunidades comparten una ventaja con probabilidad . A veces es este modelo restringido el que se denomina modelo de bloque estocástico. El caso dondese llama modelo assortativo , mientras que el casose llama desasortativo .
Volviendo al modelo de bloque estocástico general, un modelo se denomina fuertemente assortativo si cuando sea : todas las entradas diagonales dominan todas las entradas fuera de la diagonal. Un modelo se llama débilmente assortativo si cuando sea : cada entrada diagonal solo se requiere para dominar el resto de su propia fila y columna. [1] Existen formas desasortativas de esta terminología, al revertir todas las desigualdades. La recuperación algorítmica es a menudo más fácil contra modelos de bloques con condiciones clasificatorias o desasortativas de esta forma. [1]
Tareas estadísticas típicas
Gran parte de la literatura sobre detección de comunidades algorítmicas aborda tres tareas estadísticas: detección, recuperación parcial y recuperación exacta.
Detección
El objetivo de los algoritmos de detección es simplemente determinar, dado un gráfico de muestra, si el gráfico tiene una estructura de comunidad latente. Más precisamente, se podría generar un gráfico, con alguna probabilidad previa conocida, a partir de un modelo de bloque estocástico conocido y, de lo contrario, a partir de un modelo similar de Erdos-Renyi . La tarea algorítmica es identificar correctamente cuál de estos dos modelos subyacentes generó el gráfico. [2]
Recuperación parcial
En la recuperación parcial, el objetivo es determinar aproximadamente la partición latente en comunidades, en el sentido de encontrar una partición que esté correlacionada con la partición verdadera significativamente mejor que una suposición aleatoria. [3]
Recuperación exacta
En la recuperación exacta, el objetivo es recuperar exactamente la partición latente en comunidades. El tamaño de la comunidad y la matriz de probabilidad pueden ser conocidos [4] o desconocidos. [5]
Límites estadísticos inferiores y comportamiento de umbral
Los modelos de bloques estocásticos exhiben un fuerte efecto de umbral que recuerda a los umbrales de percolación . [6] [2] [7] Supongamos que permitimos el tamañodel gráfico para crecer, manteniendo el tamaño de la comunidad en proporciones fijas. Si la matriz de probabilidad permanece fija, tareas como la recuperación parcial y exacta se vuelven factibles para todos los ajustes de parámetros no degenerados. Sin embargo, si reducimos la matriz de probabilidad a una tasa adecuada como aumenta, observamos una transición de fase brusca: para ciertos ajustes de los parámetros, será posible lograr la recuperación con una probabilidad que tiende a 1, mientras que en el lado opuesto del umbral del parámetro, la probabilidad de recuperación tiende a 0 sin importar el algoritmo se utiliza.
Para la recuperación parcial, la escala adecuada es tomar para fijo , resultando en gráficos de grado promedio constante. En el caso de dos comunidades de igual tamaño, en el modelo de partición selectiva plantada con matriz de probabilidad
Para una recuperación exacta, la escala adecuada es tomar , lo que da como resultado gráficos de grado medio logarítmico. Aquí existe un umbral similar: para el modelo de partición plantado assortative con comunidades de igual tamaño, el umbral se encuentra en . De hecho, el umbral de recuperación exacto es conocido para el modelo de bloque estocástico completamente general. [4]
Algoritmos
En principio, la recuperación exacta se puede resolver en su rango factible utilizando la máxima probabilidad , pero esto equivale a resolver un problema de corte restringido o regularizado , como una bisección mínima que normalmente es NP-completa . Por lo tanto, ningún algoritmo eficiente conocido calculará correctamente la estimación de máxima verosimilitud en el peor de los casos.
Sin embargo, una amplia variedad de algoritmos funcionan bien en el caso promedio, y se han probado muchas garantías de rendimiento de alta probabilidad para los algoritmos tanto en la configuración de recuperación parcial como exacta. Los algoritmos exitosos incluyen agrupamiento espectral de los vértices, [8] [3] [4] [9] programación semidefinida , [1] [7] formas de propagación de creencias , [6] [10] y detección de comunidades [11] entre otros.
Variantes
Existen varias variantes del modelo. Un pequeño ajuste asigna los vértices a las comunidades de forma aleatoria, de acuerdo con una distribución categórica , en lugar de en una partición fija. [4] Las variantes más significativas incluyen el modelo de bloques geométricos, [12] el modelo de bloques censurados y el modelo de bloques de membresía mixta. [13]
Modelos de tema
Se ha reconocido que el modelo de bloques estocásticos es un modelo temático en redes bipartitas. [14] En una red de documentos y palabras, Stochastic Block Model puede identificar temas: grupo de palabras con un significado similar.
Referencias
- ^ a b c Amini, Arash A .; Levina, Elizaveta (junio de 2014). "Sobre relajaciones semidefinidas para el modelo de bloque". arXiv : 1406,5647 [ cs.LG ].
- ^ a b c Mossel, Elchanan; Neeman, Joe; Sly, Allan (febrero de 2012). "Modelos de bloques estocásticos y reconstrucción". arXiv : 1202.1499 [ math.PR ].
- ^ a b c Massoulie, Laurent (noviembre de 2013). "Los umbrales de detección de la comunidad y la propiedad débil de Ramanujan". arXiv : 1311.3085 [ cs.SI ].
- ^ a b c d Abbe, Emmanuel; Sandon, Colin (marzo de 2015). "Detección de comunidades en modelos generales de bloques estocásticos: límites fundamentales y algoritmos de recuperación eficientes". arXiv : 1503.00609 [ math.PR ].
- ^ Abbe, Emmanuel; Sandon, Colin (junio de 2015). "Recuperación de comunidades en el modelo general de bloques estocásticos sin conocer los parámetros". arXiv : 1506.03729 [ math.PR ].
- ^ a b Decelle, Aurelien; Krzakala, Florent; Moore, Cristopher; Zdeborová, Lenka (septiembre de 2011). "Análisis asintótico del modelo de bloques estocásticos para redes modulares y sus aplicaciones algorítmicas". Revisión E física . 84 (6): 066106. arXiv : 1109.3041 . Código Bibliográfico : 2011PhRvE..84f6106D . doi : 10.1103 / PhysRevE.84.066106 . PMID 22304154 .
- ^ a b Abbe, Emmanuel; Bandeira, Afonso S .; Hall, Georgina (mayo de 2014). "Recuperación exacta en el modelo de bloque estocástico". arXiv : 1405,3267 [ cs.SI ].
- ^ Krzakala, Florent; Moore, Cristopher; Mossel, Elchanan; Neeman, Joe; Astuto, Allan; Lenka, Lenka; Zhang, Pan (octubre de 2013). "Redención espectral en la agrupación de redes dispersas" . Actas de la Academia Nacional de Ciencias . 110 (52): 20935–20940. arXiv : 1306,5550 . Código Bibliográfico : 2013PNAS..11020935K . doi : 10.1073 / pnas.1312486110 . PMC 3876200 . PMID 24277835 .
- ^ Lei, Jing; Rinaldo, Alessandro (febrero de 2015). "Consistencia de la agrupación espectral en modelos de bloques estocásticos". The Annals of Statistics . 43 (1): 215–237. arXiv : 1312.2050 . doi : 10.1214 / 14-AOS1274 . ISSN 0090-5364 .
- ^ Mossel, Elchanan; Neeman, Joe; Sly, Allan (septiembre de 2013). "Propagación de creencias, reconstrucción robusta y recuperación óptima de modelos de bloques". Los anales de la probabilidad aplicada . 26 (4): 2211–2256. arXiv : 1309.1380 . Código bibliográfico : 2013arXiv1309.1380M . doi : 10.1214 / 15-AAP1145 .
- ^ Fathi, Reza (abril de 2019). "Detección de comunidad distribuida eficiente en el modelo de bloque estocástico". arXiv : 1904.07494 [ cs.DC ].
- ^ Galhotra, Sainyam; Mazumdar, Arya; Pal, Soumyabrata; Saha, Barna (febrero de 2018). "El modelo de bloques geométricos". AAAI . arXiv : 1709.05510 .
- ^ Airoldi, Edoardo ; Blei, David; Feinberg, Stephen; Xing, Eric (mayo de 2007). "Modelos de bloques estocásticos de membresía mixta" . Revista de investigación sobre aprendizaje automático . 9 : 1981–2014. arXiv : 0705.4485 . Código bibliográfico : 2007arXiv0705.4485A . PMC 3119541 . PMID 21701698 .
- ^ Martin Gerlach; Tiago Peixoto; Eduardo Altmann (2018). "Un enfoque de red para los modelos de temas" . Avances científicos . 4 (7): eaaq1360. arXiv : 1708.01677 . Código bibliográfico : 2018SciA .... 4.1360G . doi : 10.1126 / sciadv.aaq1360 . PMC 6051742 . PMID 30035215 .