Modelo de Bloques Estocásticos — Detección Probabilística de Comunidades en Redes
- Año
- 1983
- Tipo
- Probabilistic generative graph model
Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés
¿Qué hace?
El Modelo de Bloques Estocásticos (SBM, por sus siglas en inglés), introducido por Holland, Laskey y Leinhardt (1983), es un modelo generativo probabilístico para grafos que asigna nodos a bloques latentes y estima paramétricamente las probabilidades de conexión entre bloques.
Es el enfoque fundamental para la detección de comunidades, la identificación de núcleo-periferia y el descubrimiento de estructuras jerárquicas en el análisis de redes.
La intuición detrás del método
Imagine una red social donde las personas se agrupan en clústeres — colegas, familia, equipos deportivos — y las conexiones dentro de un grupo son más probables que las conexiones entre grupos. El Modelo de Bloques Estocásticos formaliza esta intuición: asume que existe una etiqueta de grupo oculta para cada nodo, y que la probabilidad de una arista entre dos nodos cualesquiera depende únicamente de a qué grupos pertenecen esos dos nodos. Ajustar el modelo significa encontrar las etiquetas ocultas que mejor explican el patrón de aristas observado. El resultado es una partición de la red en bloques, basada en principios y estadísticamente fundamentada, sin necesidad de que los grupos sean clics densos — el modelo acomoda estructuras núcleo-periferia e incluso patrones disasortativos donde las conexiones entre grupos superan a las intragrupo.
Historia
El Modelo de Bloques Estocásticos fue introducido por Holland, Laskey y Leinhardt en su artículo de 1983 en Social Networks como una generalización probabilística de trabajos anteriores de modelado de bloques en el análisis de redes sociales. Durante dos décadas, se mantuvo principalmente como una herramienta teórica; ganó tracción práctica con el desarrollo de algoritmos de inferencia escalables — EM variacional y MCMC — en la década de 2010. El SBM Corregido por Grado fue introducido por Karrer y Newman (2011) para abordar el problema de la heterogeneidad de grado. La revisión de Lee y Wilkinson de 2019 en Applied Network Science consolidó la familia de extensiones, cubriendo modelos de partición plantada, SBM de membresía mixta y variantes jerárquicas. Hoy en día, SBM y sus descendientes son el marco probabilístico de referencia para la detección de comunidades y el agrupamiento de grafos.
Cuándo usarlo
Utilice el Modelo de Bloques Estocásticos cuando tenga una red con al menos 50 nodos y desee descubrir una estructura de grupo latente sin asumir que los grupos deben ser clics densos. Es apropiado para grafos dirigidos o no dirigidos, ponderados o no ponderados, y se adapta tanto a tareas exploratorias como de clasificación. La variante DCSBM se prefiere cuando los grados de los nodos varían sustancialmente. Si el grafo tiene menos de 20 nodos, la estructura de comunidad no se puede estimar de manera fiable y se deben utilizar métricas descriptivas más simples en su lugar. Supuestos: las membresías de bloque son latentes y no observadas; se asume que la matriz de conexión de bloques es homogénea dentro de cada par de bloques; y K debe seleccionarse mediante BIC o factor de Bayes en lugar de fijarse arbitrariamente.
Limitaciones y consideraciones
- Requiere al menos unos 50 nodos para una estimación de bloque fiable; grafos muy pequeños producen soluciones inestables.
- La inferencia es computacionalmente costosa para grafos grandes: se requiere EM variacional o MCMC, y la convergencia no está garantizada.
- La suposición de homogeneidad del SBM básico dentro de los pares de bloques se rompe cuando las tasas de conexión dentro de los bloques varían — el DCSBM mitiga pero no elimina esto.
- La selección de bloques mediante BIC o factor de Bayes aún puede sub- o sobre-segmentar si el grafo tiene comunidades débilmente separadas.
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Marco probabilístico con principios que permite la selección del modelo a través de BIC o factor de Bayes, evitando elecciones arbitrarias de parámetros.
- Acomoda una amplia gama de patrones estructurales — comunidades, núcleo-periferia, bipartitos y jerárquicos — más allá de la suposición de clic denso de los métodos algorítmicos.
- La variante Corregida por Grado maneja grafos con distribuciones de grado heterogéneas y nodos centrales (hubs) sin distorsionar las asignaciones de bloque.
- Proporciona probabilidades de membresía posteriores, permitiendo asignaciones de nodos suaves o inciertas en lugar de particiones duras.
Aplicaciones
- Detectar comunidades de investigación en redes de citación y colaboración en las ciencias sociales y naturales.
- Identificar módulos funcionales en redes biológicas como interacciones proteína-proteína y grafos de coexpresión génica.
- Descubrir segmentos de clientes o anillos de fraude en redes transaccionales y financieras.
- Caracterizar la estructura núcleo-periferia en redes interorganizacionales o de comercio interpaís.
- Evaluar y comparar otros algoritmos de detección de comunidades utilizando grafos sintéticos generados por SBM como verdad fundamental.
Cómo funciona
Cómo funciona
El analista especifica un rango candidato para el número de bloques K y elige una variante: el SBM básico asume una distribución de grado homogénea dentro de los bloques, mientras que el SBM Corregido por Grado (DCSBM, por sus siglas en inglés) añade parámetros de grado a nivel de nodo para manejar nodos centrales (hubs) y secuencias de grado heterogéneas. La elección de la variante se basa en la distribución de grado del grafo observado.
Dada la matriz de adyacencia, el modelo estima las membresías de bloque y una matriz K×K de probabilidades de conexión utilizando un algoritmo de inferencia. Para grafos pequeños y medianos, la maximización exacta es factible; para grafos grandes, se utiliza la Expectation-Maximisation variacional (EM variacional) o el muestreo de Cadena de Markov Monte Carlo (MCMC) para hacer la inferencia tratable.
El número de bloques K no se conoce de antemano y debe elegirse a partir de los datos. Los criterios de selección preferidos son el Criterio de Información Bayesiano (BIC, por sus siglas en inglés) y el factor de Bayes, ambos penalizan la complejidad del modelo y seleccionan el K que mejor equilibra el ajuste con la parsimonia. El principio de longitud mínima de descripción (MDL, por sus siglas en inglés) subyace a la implementación de graph-tool.
Una vez determinados el K óptimo y las asignaciones de bloque, se inspecciona la matriz de conexión de bloques para caracterizar la estructura: los bloques asortativos corresponden a comunidades, los bloques disasortativos a patrones similares a bipartitos y los perfiles mixtos a arreglos núcleo-periferia. Las membresías de los nodos se reportan con probabilidades posteriores cuando el algoritmo de inferencia las proporciona.
Errores comunes
- Fijar K arbitrariamente en lugar de seleccionarlo mediante BIC o factor de Bayes produce particiones poco fiables — utilice siempre un criterio de selección de modelo con principios.
- Aplicar el SBM básico a un grafo con una secuencia de grado heterogénea (hubs, distribución de grado de ley de potencias) infla las estimaciones del número de bloques; utilice DCSBM en su lugar.
- Tratar la membresía de bloque como cierta cuando la posterior está difusa sobreestima la confianza — reporte la incertidumbre cuando esté disponible.
- Confundir la salida del SBM con comunidades de verdad fundamental: el modelo encuentra estructuras latentes estadísticamente plausibles, no necesariamente grupos sociológicamente significativos. Valide contra el conocimiento del dominio.
- Ejecutar SBM en menos de 20 nodos produce soluciones degeneradas — recurra a métricas de red descriptivas o detección de comunidades simple para grafos pequeños.
Preguntas frecuentes
¿En qué se diferencia el Modelo de Bloques Estocásticos de la detección de comunidades basada en modularidad?
La maximización de modularidad (por ejemplo, Louvain, Leiden) optimiza un objetivo heurístico que asume implícitamente comunidades asortativas y de tamaño aproximadamente igual, y tiene un límite de resolución conocido que impide la detección de comunidades pequeñas. El SBM es un modelo generativo probabilístico con supuestos explícitos; el número de bloques se elige mediante selección de modelo (BIC o factor de Bayes) en lugar de optimización heurística, y puede detectar estructuras disasortativas y núcleo-periferia que los métodos basados en modularidad no captan.
¿Cuándo debo usar DCSBM en lugar del SBM básico?
Utilice DCSBM cuando la distribución de grado de los nodos sea heterogénea — por ejemplo, cuando un pequeño número de nodos centrales (hubs) representen una gran fracción de las aristas, o cuando la secuencia de grado siga una ley de potencias aproximada. El SBM básico trata a todos los nodos dentro de un bloque como intercambiables, lo que hace que los nodos centrales se agrupen en sus propios bloques espurios. DCSBM añade un término de corrección de grado que separa la posición estructural del grado, produciendo asignaciones de bloque más interpretables en tales grafos.
¿Cómo elijo el número de bloques K?
Ajuste modelos para un rango de valores de K y seleccione aquel que minimice BIC o maximice el factor de Bayes (o equivalentemente, minimice la longitud de descripción). No elija K basándose en la inspección visual del grafo o expectativas previas. La mayoría de las implementaciones (graph-tool, blockmodels en R) automatizan esta búsqueda. También se recomienda el análisis de sensibilidad — comprobar si la estructura de bloque cualitativa cambia al variar K en uno.
¿Cuál es el tamaño mínimo de red para que SBM sea fiable?
El registro especifica un mínimo de 50 nodos para una inferencia fiable. Con menos de 20 nodos, el modelo no puede identificar una estructura de comunidad significativa y ajustará el ruido — utilice estadísticas de red descriptivas o detección de comunidades simple en su lugar. Entre 20 y 50 nodos, los resultados deben tratarse como exploratorios y interpretarse con precaución.
Métodos relacionados
Fuentes
Holland, P.W., Laskey, K.B. & Leinhardt, S. (1983). Stochastic Blockmodels: First Steps. Social Networks, 5(2), 109-137.
Abrir referencia DOICopiado.Lee, C. & Wilkinson, D.J. (2019). A Review of Stochastic Block Models and Extensions for Graph Clustering. Applied Network Science, 4(1), 122.
Abrir referencia DOICopiado.