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.
El modelo de bloques estocástico toma los siguientes parámetros:
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 .
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.
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 .
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]
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.
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]
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]
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]
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.
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 variada 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 .
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]
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.
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]
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.
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]
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]