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 caracterizados 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 ellas. 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 comunidades en datos de grafos.

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

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

El conjunto de aristas se muestrea luego al azar de la siguiente manera: cualesquiera dos vértices${\displaystyle u\in C_{i}}$y${\displaystyle v\in C_{j}}$están conectados por una arista con probabilidad${\displaystyle P_{ij}}$. Un ejemplo de problema es: dado un gráfico con ${\displaystyle n}$vértices, donde las aristas se muestrean como se describe, recuperan los grupos ${\displaystyle C_{1},\ldots ,C_{r}}$.

Si la matriz de probabilidad es una constante, en el sentido de que${\displaystyle P_{ij}=p}$a pesar de${\displaystyle i,j}$, entonces el resultado es el modelo Erdős-Rényi${\displaystyle G(n,p)}$Este caso es degenerado —la partición en comunidades se vuelve irrelevante—, pero ilustra una estrecha relación con el modelo de Erdős-Rényi.

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

Volviendo al modelo general de bloques estocásticos, un modelo se denomina fuertemente asociativo si${\displaystyle P_{ii}>P_{jk}}$cuando sea${\displaystyle j\neq k}$: todas las entradas diagonales dominan a todas las entradas fuera de la diagonal. Un modelo se denomina débilmente asociativo si${\displaystyle P_{ii}>P_{ij}}$cuando sea${\displaystyle i\neq j}$Cada entrada diagonal solo debe dominar el resto de su propia fila y columna. ^{[ 2 ]} Existen formas disasortativas de esta terminología, invirtiendo todas las desigualdades. Para algunos algoritmos, la recuperación podría ser más fácil para modelos de bloques con condiciones asociativas o disasortativas de esta forma. ^{[ 2 ]}

Gran parte de la bibliografía sobre detección algorítmica de comunidades aborda tres tareas estadísticas: detección, recuperación parcial y recuperación exacta.

Los modelos de bloques estocásticos exhiben un marcado efecto umbral que recuerda a los umbrales de percolación . ^{[ 7 ] [ 3 ] [ 8 ]} Supongamos que permitimos el tamaño${\displaystyle n}$del gráfico para crecer, manteniendo los tamaños de las comunidades 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 degeneradas. Sin embargo, si reducimos la matriz de probabilidad a una tasa adecuada como${\displaystyle n}$A medida que aumenta, observamos una transición de fase abrupta: para ciertas configuraciones 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 utilice.

Para una recuperación parcial, la escala apropiada es tomar${\displaystyle P_{ij}={\tilde {P}}_{ij}/n}$para fijo${\displaystyle {\tilde {P}}}$, 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 selectiva con matriz de probabilidad $${\displaystyle P=\left({\begin{array}{cc}{\tilde {p}}/n&{\tilde {q}}/n\\{\tilde {q}}/n&{\tilde {p}}/n\end{array}}\right),}$$ La recuperación parcial es factible ^{[ 4 ]} con probabilidad${\displaystyle 1-o(1)}$cuando sea${\displaystyle ({\tilde {p}}-{\tilde {q}})^{2}>2({\tilde {p}}+{\tilde {q}})}$, mientras que cualquier estimador falla ^{[ 3 ]} recuperación parcial con probabilidad${\displaystyle 1-o(1)}$cuando sea${\displaystyle ({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})}$.

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

En principio, la recuperación exacta puede resolverse dentro de su rango factible mediante máxima verosimilitud , pero esto equivale a resolver un problema de corte restringido o regularizado , como la bisección mínima, que suele ser 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 configuraciones de recuperación parcial como exacta. Los algoritmos exitosos incluyen agrupamiento espectral de vértices, ^{[ 9 ] [ 4 ] [ 5 ] [ 10 ]} programación semidefinida , ^{[ 2 ] [ 8 ]} formas de propagación de creencias , ^{[ 7 ] [ 11 ]} y detección de comunidades ^{[ 12 ]} entre otros.

Existen varias variantes del modelo. Una pequeña modificación asigna los vértices a las comunidades de forma aleatoria, según una distribución categórica , en lugar de en una partición fija. ^{[ 5 ]} Las variantes más significativas incluyen el modelo de bloques estocásticos con corrección de grado, ^{[ 13 ]} el modelo de bloques estocásticos jerárquicos, ^{[ 14 ]} el modelo de bloques geométricos, ^{[ 15 ]} el modelo de bloques censurados y el modelo de bloques de membresía mixta. ^{[ 16 ]}

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.

Los grafos con signos permiten relaciones tanto favorables como adversas y constituyen una opción de modelo común para diversas aplicaciones de análisis de datos, por ejemplo, la agrupación por correlación. El modelo de bloques estocásticos puede extenderse fácilmente a grafos con signos asignando pesos positivos y negativos a las aristas o, de forma equivalente, utilizando 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 grafos y datos dispersos derivados de redes sociales, flujos de sensores y datos científicos para permitir el descubrimiento de relaciones entre eventos a medida que se desarrollan en el campo. La partición estocástica de bloques en tiempo real es uno de los desafíos desde 2017. ^{[ 20 ]} El agrupamiento espectral ha demostrado un rendimiento excepcional en comparación con el algoritmo base original e incluso mejorado ^{[ 21 ]} , igualando su calidad de clústeres y siendo varios órdenes de magnitud más rápido. ^{[ 22 ] [ 23 ]}

• modelado de bloques
• Algoritmo de Girvan-Newman : algoritmo de detección de comunidades. 
• Referencia Lancichinetti–Fortunato–Radicchi : páginas de algoritmos que muestran descripciones breves sin espacios para generar redes de referencia con comunidades.