Modelo de bloque estocástico

El modelo de bloques estocástico es un modelo generativo para gráficos aleatorios . Este modelo tiende a producir gráficos que contienen comunidades , subconjuntos de nodos 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. Su formulación matemática fue introducida por primera vez en 1983 en el campo del análisis de redes sociales por Paul W. Holland et al. ^[1] El modelo de bloques estocásticos es importante en estadística , aprendizaje automático y ciencia de redes , donde sirve como punto de referencia útil para la tarea de recuperar la estructura comunitaria en datos gráficos.

Definición

El modelo de bloques estocástico toma los siguientes parámetros:

• El número de vértices; ${\displaystyle n}$
• una partición del conjunto de vértices en subconjuntos disjuntos , llamados comunidades ; ${\displaystyle \{1,\ldots ,n\}}$ ${\displaystyle C_{1},\ldots ,C_{r}}$
• una matriz simétrica de probabilidades de borde. ${\displaystyle r\times r}$ ${\displaystyle P}$

Luego, el conjunto de aristas se muestrea aleatoriamente 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, recupere los grupos . ${\displaystyle u\in C_{i}}$ ${\displaystyle v\in C_{j}}$ ${\displaystyle P_{ij}}$ ${\displaystyle n}$ ${\displaystyle C_{1},\ldots ,C_{r}}$

Casos especiales

Un ejemplo del caso selectivo del modelo de bloques estocástico.

Si la matriz de probabilidad es una constante, en el sentido de que para todos , entonces el resultado es el modelo de 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. ${\displaystyle P_{ij}=p}$ ${\displaystyle i,j}$ ${\displaystyle G(n,p)}$

El modelo de partición plantada es el caso especial en el que los valores de la matriz de probabilidad son una constante en la diagonal y otra constante fuera de la diagonal. Así, dos vértices dentro de la misma comunidad comparten una arista con probabilidad , mientras que dos vértices en diferentes comunidades comparten una arista con probabilidad . A veces es este modelo restringido el que se denomina modelo de bloques estocástico. El caso en el que se denomina modelo assortativo , mientras que el caso se denomina modelo desasortativo . ${\displaystyle P}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p>q}$ ${\displaystyle p<q}$

Volviendo al modelo de bloques estocástico general, un modelo se llama fuertemente selectivo si siempre : todas las entradas diagonales dominan a todas las entradas fuera de la diagonal. Un modelo se llama débilmente selectivo si siempre : solo se requiere que cada entrada diagonal domine el resto de su propia fila y columna. ^{[2] Existen formas} desasortativas de esta terminología, al revertir todas las desigualdades. Para algunos algoritmos, la recuperación puede ser más fácil para modelos de bloques con condiciones de clasificación o desasortación de esta forma. ^[2] ${\displaystyle P_{ii}>P_{jk}}$ ${\displaystyle j\neq k}$ ${\displaystyle P_{ii}>P_{ij}}$ ${\displaystyle i\neq j}$

Tareas estadísticas típicas

Gran parte de la literatura sobre detección algorítmica de comunidades 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 muestreado, si el gráfico tiene una estructura comunitaria latente. Más precisamente, se podría generar un gráfico, con alguna probabilidad previa conocida, a partir de un modelo de bloques estocástico conocido y, en caso 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. ^[3]

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 se correlacione con la partición verdadera significativamente mejor que una suposición aleatoria. ^[4]

Recuperación exacta

En la recuperación exacta, el objetivo es recuperar exactamente la división latente en comunidades. Los tamaños de las comunidades y la matriz de probabilidad pueden ser conocidos ^[5] o desconocidos. ^[6]

Límites inferiores estadísticos y comportamiento de umbral.

Los modelos de bloques estocásticos exhiben un fuerte efecto de umbral que recuerda a los umbrales de percolación . ^{[7] [3] [8]} Supongamos que permitimos que el tamaño del gráfico crezca, manteniendo los tamaños 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 todas las configuraciones de parámetros no degenerados. Sin embargo, si reducimos la matriz de probabilidad a un ritmo adecuado a medida que 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 de la umbral del parámetro, la probabilidad de recuperación tiende a 0 sin importar qué algoritmo se utilice. ${\displaystyle n}$ ${\displaystyle n}$

Para la recuperación parcial, la escala adecuada es tomarla como fija , lo que da como resultado gráficas de grado promedio constante. En el caso de dos comunidades de igual tamaño, en el modelo de partición plantada selectiva con matriz de probabilidad ${\displaystyle P_{ij}={\tilde {P}}_{ij}/n}$ ${\displaystyle {\tilde {P}}}$

$${\displaystyle P=\left({\begin{array}{cc}{\tilde {p}}/n&{\tilde {q}}/n\\{\tilde {q}}/n&{\tilde {p}}/n\end{array}}\right),}$$

^[4]estimador^[3] ${\displaystyle 1-o(1)}$ ${\displaystyle ({\tilde {p}}-{\tilde {q}})^{2}>2({\tilde {p}}+{\tilde {q}})}$ ${\displaystyle 1-o(1)}$ ${\displaystyle ({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})}$

Para una recuperación exacta, se debe tomar la escala adecuada , lo que da como resultado gráficos de grado promedio logarítmico. Aquí existe un umbral similar: para el modelo de partición plantada variada con comunidades del mismo tamaño, el umbral se encuentra en . De hecho, el umbral de recuperación exacto se conoce para el modelo de bloques estocástico totalmente general. ^[5] ${\displaystyle P_{ij}={\tilde {P}}_{ij}\log n/n}$ ${\displaystyle r}$ ${\displaystyle {\sqrt {\tilde {p}}}-{\sqrt {\tilde {q}}}={\sqrt {r}}}$

Algoritmos

En principio, la recuperación exacta se puede resolver en su rango factible utilizando la máxima verosimilitud , pero esto equivale a resolver un problema de corte restringido o regularizado , como la bisección mínima, que normalmente es NP-completo . 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 demostrado muchas garantías de rendimiento de alta probabilidad para algoritmos tanto en la configuración de recuperación parcial como en la exacta. Los algoritmos exitosos incluyen agrupamiento espectral de los vértices, ^{[9] [4] [5] [10]} programación semidefinida , ^{[2] [8]} formas de propagación de creencias , ^{[7] [11]} y detección comunitaria ^[12] , entre otros.

Variantes

Existen varias variantes del modelo. Un pequeño ajuste asigna vértices a las comunidades de forma aleatoria, según una distribución categórica , en lugar de una partición fija. ^[5] Las variantes más significativas incluyen el modelo de bloques estocástico con corrección de grado, ^[13] el modelo de bloques estocástico jerárquico, ^[14] el modelo de bloques geométrico, ^[15] el modelo de bloques censurados y el modelo de bloques de membresía mixta. ^[dieciséis]

Modelos temáticos

Se ha reconocido que el modelo de bloques estocásticos es un modelo temático en redes bipartitas. ^[17] En una red de documentos y palabras, el modelo de bloques estocástico puede identificar temas: grupo de palabras con un significado similar.

Extensiones a gráficos firmados

Los gráficos firmados permiten relaciones tanto favorables como adversas y sirven como una opción de modelo común para diversas aplicaciones de análisis de datos, por ejemplo, agrupación de correlaciones. El modelo de bloques estocásticos se puede extender trivialmente a gráficos con signo asignando pesos de borde tanto positivos como negativos o, de manera equivalente, usando una diferencia de matrices de adyacencia de dos modelos de bloques estocásticos. ^[18]

DARPA/MIT/AWS Graph Challenge: transmisión de partición de bloque estocástico

GraphChallenge ^[19] fomenta enfoques comunitarios para desarrollar nuevas soluciones para analizar gráficos y datos dispersos derivados de redes sociales, transmisiones de sensores y datos científicos para permitir que se descubran relaciones entre eventos a medida que se desarrollan en el campo. La transmisión de particiones de bloques estocásticos es uno de los desafíos desde 2017. ^[20] La agrupación espectral ha demostrado un rendimiento sobresaliente en comparación con el algoritmo base original e incluso mejorado ^[21] , igualando su calidad de agrupaciones y siendo varios órdenes de magnitud más rápido. ^{[22] [23]}

Ver también

• modelado de bloques
• Algoritmo de Girvan-Newman  : algoritmo de detección de comunidades
• Benchmark Lancichinetti–Fortunato–Radicchi  – Algoritmo Pages displaying short descriptions with no spacespara generar redes de benchmark con comunidades

Referencias

1. Holanda, Paul W; Laskey, Kathryn Blackmond; Leinhardt, Samuel (1983). "Modelos de bloques estocásticos: primeros pasos". Redes sociales . 5 (2): 109-137. doi :10.1016/0378-8733(83)90021-7. ISSN  0378-8733. S2CID  34098453. Archivado desde el original el 4 de febrero de 2023 . Consultado el 16 de junio de 2021 .
2. Amini, Arash A.; Levina, Elizaveta (junio de 2014). "Sobre relajaciones semidefinidas para el modelo de bloques". arXiv : 1406.5647 [cs.LG].
3. Mossel, Elchanan; Neeman, Joe; Astuto, Allan (febrero de 2012). "Reconstrucción y modelos de bloques estocásticos". arXiv : 1202.1499 [matemáticas.PR].
4. Massoulie, Laurent (noviembre de 2013). "Umbrales de detección de la comunidad y la débil propiedad de Ramanujan". arXiv : 1311.3085 [cs.SI].
5. Abbe, Emmanuel; Sandon, Colin (marzo de 2015). "Detección comunitaria en modelos de bloques estocásticos generales: límites fundamentales y algoritmos de recuperación eficientes". arXiv : 1503.00609 [matemáticas.PR].
6. Abbe, Emmanuel; Sandon, Colin (junio de 2015). "Recuperar comunidades en el modelo de bloques estocástico general sin conocer los parámetros". arXiv : 1506.03729 [matemáticas.PR].
7. Decelle, Aurelien; Krzakala, Florent; Moore, Cristopher; Zdeborová, Lenka (septiembre de 2011). "Análisis asintótico del modelo de bloques estocástico para redes modulares y sus aplicaciones algorítmicas". Revisión física E. 84 (6): 066106. arXiv : 1109.3041 . Código bibliográfico : 2011PhRvE..84f6106D. doi : 10.1103/PhysRevE.84.066106. PMID  22304154. S2CID  15788070.
8. Abbe, Emmanuel; Bandeira, Alfonso S.; Hall, Georgina (mayo de 2014). "Recuperación exacta en el modelo de bloques estocástico". arXiv : 1405.3267 [cs.SI].
9. Krzakala, Florent; Moore, Cristopher; Mossel, Eljanán; Neeman, Joe; Astuto, Allan; Lenka, Lenka; Zhang, Pan (octubre de 2013). "Redención espectral en agrupaciones de redes dispersas". Procedimientos de la Academia Nacional de Ciencias . 110 (52): 20935–20940. arXiv : 1306.5550 . Código Bib : 2013PNAS..11020935K. doi : 10.1073/pnas.1312486110 . PMC 3876200 . PMID  24277835. 
10. Lei, Jing; Rinaldo, Alessandro (febrero de 2015). "Consistencia de la agrupación espectral en modelos de bloques estocásticos". Los anales de la estadística . 43 (1): 215–237. arXiv : 1312.2050 . doi :10.1214/14-AOS1274. ISSN  0090-5364. S2CID  88519551.
11. Mossel, Eljanán; Neeman, Joe; Astuto, Allan (septiembre de 2013). "Propagación de creencias, reconstrucción sólida y recuperación óptima de modelos de bloques". Los anales de la probabilidad aplicada . 26 (4): 2211–2256. arXiv : 1309.1380 . Código Bib : 2013arXiv1309.1380M. doi :10.1214/15-AAP1145. S2CID  184446.
12. Fathi, Reza (abril de 2019). "Detección comunitaria distribuida eficiente en el modelo de bloques estocásticos". arXiv : 1904.07494 [cs.DC].
13. Karrer, Brian; Newman, Mark EJ (2011). "Modelos de bloques estocásticos y estructura comunitaria en redes". Revisión física E. 83 (1): 016107. arXiv : 1008.3926 . Código bibliográfico : 2011PhRvE..83a6107K. doi : 10.1103/PhysRevE.83.016107. PMID  21405744. S2CID  9068097. Archivado desde el original el 4 de febrero de 2023 . Consultado el 16 de junio de 2021 .
14. Peixoto, Tiago (2014). "Estructuras de bloques jerárquicos y selección de modelos de alta resolución en grandes redes". Revisión física X. 4 (1): 011047. arXiv : 1310.4377 . Código Bib : 2014PhRvX...4a1047P. doi : 10.1103/PhysRevX.4.011047. S2CID  5841379. Archivado desde el original el 24 de junio de 2021 . Consultado el 16 de junio de 2021 .
15. Galhotra, Sainyam; Mazumdar, Arya; Pal, Soumyabrata; Saha, Barna (febrero de 2018). "El modelo de bloques geométricos". AAAI . 32 . arXiv : 1709.05510 . doi : 10.1609/aaai.v32i1.11905. S2CID  19152144.
16. Airoldi, Eduardo ; 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 Bib : 2007arXiv0705.4485A. PMC 3119541 . PMID  21701698. 
17. Martín Gerlach; Tiago Peixoto; Eduardo Altmann (2018). "Un enfoque de red para modelos temáticos". Avances científicos . 4 (7): eaaq1360. arXiv : 1708.01677 . Código Bib : 2018SciA....4.1360G. doi :10.1126/sciadv.aaq1360. PMC 6051742 . PMID  30035215. 
18. Alyson Fox; Geoffrey Sanders; Andrés Knyazev (2018). "Investigación de agrupación espectral para representaciones de matrices de gráficos firmados". Conferencia de Computación Extrema de Alto Rendimiento (HPEC) de IEEE 2018 . págs. 1–7. doi :10.1109/HPEC.2018.8547575. ISBN 978-1-5386-5989-2. OSTI  1476177. S2CID  54443034.
19. [1] Archivado el 4 de febrero de 2023 en Wayback Machine DARPA/MIT/AWS Graph Challenge
20. [2] Archivado el 4 de febrero de 2023 en Wayback Machine DARPA/MIT/AWS Graph Challenge Champions
21. AJ Uppal; J. Choi; TB Rolinger; H. Howie Huang (2021). "Partición de bloques estocásticos más rápida mediante fusión inicial agresiva, representación comprimida y control de paralelismo". Conferencia de Computación Extrema de Alto Rendimiento (HPEC) del IEEE 2021 . págs. 1–7. doi :10.1109/HPEC49654.2021.9622836. ISBN 978-1-6654-2369-4. S2CID  244780210.
22. David Zhuzhunashvili; Andrés Knyazev (2017). "Agrupación espectral precondicionada para el desafío de gráficos de transmisión de particiones de bloques estocásticos (versión preliminar en arXiv.)". Conferencia de Computación Extrema de Alto Rendimiento (HPEC) de IEEE 2017 . págs. 1–6. arXiv : 1708.07481 . doi :10.1109/HPEC.2017.8091045. ISBN 978-1-5386-3472-1. S2CID  19781504.
23. Lisa Durbeck; Pedro Atanas (2020). "Partición de gráficos de transmisión incremental". Conferencia de Computación Extrema de Alto Rendimiento (HPEC) del IEEE 2020 . págs. 1–8. doi :10.1109/HPEC43674.2020.9286181. ISBN 978-1-7281-9219-2. S2CID  229376193.