Modelo de bloques estocásticos

El modelo de bloques estocásticos es un modelo generativo para grafos aleatorios . Este modelo tiende a producir grafos que contienen comunidades , subconjuntos de nodos que se caracterizan por estar conectados entre sí con densidades de aristas particulares. Por ejemplo, las aristas 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 un punto de referencia útil para la tarea de recuperar la estructura de la comunidad en datos de grafos.

Definición

El modelo de bloque 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 arista. ${\displaystyle r\times r}$ ${\displaystyle P}$

El conjunto de aristas se muestrea entonces de forma aleatoria de la siguiente manera: dos vértices cualesquiera y están conectados por una arista con probabilidad . Un problema de ejemplo es: dado un grafo con vértices, donde las aristas se muestrean como se describe, recuperar 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 asortativo para el modelo de bloque estocástico.

Si la matriz de probabilidad es una constante, en el sentido de que para todo , entonces el resultado es el modelo de Erdős–Rényi . Este caso es degenerado (la partición en comunidades se vuelve irrelevante), pero ilustra una relación estrecha con el modelo de 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. Por lo tanto, 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, este modelo restringido es el que se denomina modelo de bloque estocástico. El caso en el que se denomina modelo asortativo , mientras que el caso se denomina 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 denomina fuertemente asortativo si siempre que : todas las entradas diagonales dominan a todas las entradas fuera de la diagonal. Un modelo se denomina débilmente asortativo si siempre que : solo se requiere que cada entrada diagonal domine al resto de su propia fila y columna. ^{[2] Existen formas} disassortativas de esta terminología, al invertir todas las desigualdades. Para algunos algoritmos, la recuperación puede ser más sencilla para los modelos de bloques con condiciones asortativas o disassortativas 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 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 muestreado, si el gráfico tiene una estructura comunitaria latente. Más precisamente, un gráfico podría generarse, con cierta probabilidad previa conocida, a partir de un modelo de bloque estocástico conocido, y en caso contrario a partir de un modelo Erdos-Renyi similar . 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 esté correlacionada 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 la partición latente en comunidades de manera exacta. 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 del umbral

Los modelos de bloques estocásticos exhiben un efecto de umbral agudo 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 todos los ajustes de parámetros no degenerados. Sin embargo, si reducimos la matriz de probabilidad a una tasa adecuada a medida que aumenta, observamos una transición de fase aguda: 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 qué algoritmo se use. ${\displaystyle n}$ ${\displaystyle n}$

Para la recuperación parcial, la escala apropiada es tomar para fijo , lo que da como resultado gráficos de grado promedio constante. En el caso de dos comunidades de igual tamaño, en el modelo de partición plantada asortativa con matriz de probabilidad, la recuperación parcial es factible ^[4] con probabilidad siempre que , mientras que cualquier estimador falla ^[3], la recuperación parcial con probabilidad siempre que . ${\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),}$$ ${\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, la escala adecuada es tomar , lo que da como resultado gráficos de grado promedio logarítmico. Aquí existe un umbral similar: para el modelo de partición plantada asortativa con comunidades de igual tamaño, el umbral se encuentra en . De hecho, el umbral de recuperación exacto se conoce para el modelo de bloque estocástico completamente 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 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, no hay algoritmos eficientes conocidos que calculen 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 configuraciones de recuperación parcial como 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 de comunidad ^[12] entre otros.

Variantes

Existen varias variantes del modelo. Una modificación menor asigna vértices a las comunidades de forma aleatoria, según una distribución categórica , en lugar de hacerlo en una partición fija. ^[5] Las variantes más significativas incluyen el modelo de bloque estocástico con corrección de grado, ^[13] el modelo de bloque estocástico jerárquico, ^[14] el modelo de bloque geométrico, ^[15] el modelo de bloque censurado y el modelo de bloque de membresía mixta. ^[16]

Modelos de temas

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

Extensiones a gráficos con signo

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

Desafío gráfico DARPA/MIT/AWS: partición de bloques estocásticos en tiempo real

GraphChallenge ^[19] fomenta enfoques comunitarios para desarrollar nuevas soluciones para analizar gráficos y datos dispersos derivados de redes sociales, feeds de sensores y datos científicos para permitir que se descubran relaciones entre eventos a medida que se desarrollan en el campo. La partición de bloques estocásticos en tiempo real 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]}

Véase 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 referencia con comunidades

Referencias

1. Holland, 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 2023-02-04 . Consultado el 2021-06-16 .
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; Sly, Allan (febrero de 2012). "Modelos de bloques estocásticos y reconstrucción". arXiv : 1202.1499 [math.PR].
4. Massoulie, Laurent (noviembre de 2013). "Umbrales de detección de comunidades y la propiedad débil de Ramanujan". arXiv : 1311.3085 [cs.SI].
5. 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].
6. Abbe, Emmanuel; Sandon, Colin (junio de 2015). "Recuperación de comunidades en el modelo de bloques estocásticos generales sin conocer los parámetros". arXiv : 1506.03729 [math.PR].
7. 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". Physical Review E . 84 (6): 066106. arXiv : 1109.3041 . Bibcode :2011PhRvE..84f6106D. doi :10.1103/PhysRevE.84.066106. PMID  22304154. S2CID  15788070.
8. Abbe, Emmanuel; Bandeira, Afonso S.; Hall, Georgina (mayo de 2014). "Recuperación exacta en el modelo de bloques estocásticos". arXiv : 1405.3267 [cs.SI].
9. Krzakala, Florent; Moore, Cristopher; Mossel, Elchanan; Neeman, Joe; Sly, 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. 
10. Lei, Jing; Rinaldo, Alessandro (febrero de 2015). "Consistencia de la agrupación espectral en modelos de bloques estocásticos". Anales de estadística . 43 (1): 215–237. arXiv : 1312.2050 . doi :10.1214/14-AOS1274. ISSN  0090-5364. S2CID  88519551.
11. Mossel, Elchanan; Neeman, Joe; Sly, Allan (septiembre de 2013). "Propagación de creencias, reconstrucción robusta y recuperación óptima de modelos de bloques". Anales de probabilidad aplicada . 26 (4): 2211–2256. arXiv : 1309.1380 . Código Bibliográfico :2013arXiv1309.1380M. doi :10.1214/15-AAP1145. S2CID  184446.
12. Fathi, Reza (abril de 2019). "Detección eficiente de comunidades distribuidas 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 de comunidad en redes". Physical Review 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 2023-02-04 . Consultado el 2021-06-16 .
14. Peixoto, Tiago (2014). "Estructuras de bloques jerárquicas y selección de modelos de alta resolución en redes grandes". Physical Review X . 4 (1): 011047. arXiv : 1310.4377 . Código Bibliográfico :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, Edoardo ; Blei, David; Feinberg, Stephen; Xing, Eric (mayo de 2007). "Modelos de bloques estocásticos de membresía mixta". Journal of Machine Learning Research . 9 : 1981–2014. arXiv : 0705.4485 . Código Bibliográfico :2007arXiv0705.4485A. PMC 3119541 . PMID  21701698. 
17. Martin Gerlach; Tiago Peixoto; Eduardo Altmann (2018). "Un enfoque de red para los modelos de tópicos". Science Advances . 4 (7): eaaq1360. arXiv : 1708.01677 . Bibcode :2018SciA....4.1360G. doi :10.1126/sciadv.aaq1360. PMC 6051742 . PMID  30035215. 
18. Alyson Fox; Geoffrey Sanders; Andrew Knyazev (2018). "Investigación de agrupamiento espectral para representaciones matriciales de grafos con signo". Conferencia de computación extrema de alto rendimiento (HPEC) del IEEE de 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 Desafío gráfico DARPA/MIT/AWS
20. [2] Archivado el 4 de febrero de 2023 en Wayback Machine Campeones del desafío gráfico DARPA/MIT/AWS
21. AJ Uppal; J. Choi; TB Rolinger; H. Howie Huang (2021). "Partición de bloques estocástica 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 de 2021. págs. 1–7. doi :10.1109/HPEC49654.2021.9622836. ISBN 978-1-6654-2369-4. Número de identificación del sujeto  244780210.
22. David Zhuzhunashvili; Andrew Knyazev (2017). "Agrupamiento espectral preacondicionado 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 IEEE 2017 (HPEC) . págs. 1–6. arXiv : 1708.07481 . doi :10.1109/HPEC.2017.8091045. ISBN . 978-1-5386-3472-1. Número de identificación del sujeto  19781504.
23. Lisa Durbeck; Peter Athanas (2020). "Particionamiento incremental de gráficos de transmisión". Conferencia de computación extrema de alto rendimiento IEEE 2020 (HPEC) . págs. 1–8. doi :10.1109/HPEC43674.2020.9286181. ISBN 978-1-7281-9219-2. Número de identificación del sujeto  229376193.