Resumen Técnico: Optimización Heurística y Exacta de la Modularidad con Comunidades Restringidas por Tamaño

Enunciado del Problema

La detección de comunidades es una tarea fundamental en el análisis de redes, sin embargo, los algoritmos estándar a menudo fallan en incorporar conocimiento previo específico del dominio respecto a los tamaños de las comunidades. En aplicaciones como la segmentación de mercados, la neurociencia (conectomas cerebrales) y la genómica (interacciones cromosómicas), los expertos suelen poseer conocimiento de rangos razonables para los tamaños de las comunidades. No obstante, los métodos existentes sin restricciones frecuentemente producen particiones con disparidades extremas de tamaño (por ejemplo, una comunidad masiva y muchas triviales) o fallan en alinearse con realidades biológicas o funcionales.

Aunque las técnicas de multi-resolución permiten a los usuarios influir indirectamente en el tamaño promedio de la comunidad ajustando un parámetro de resolución ($\gamma$), este enfoque no controla el tamaño de las comunidades individuales, ni garantiza que todas las comunidades caigan dentro de un rango específico definido por el usuario. Este artículo aborda el problema de la Maximización de la Modularidad con Restricciones de Tamaño (SMM): encontrar una partición de una red que maximice la modularidad asegurando que el tamaño de cada comunidad $n_c$ satisfaga $n_{min} \le n_c \le n_{max}$.

Metodología

Los autores proponen un enfoque dual para resolver el problema SMM: una línea base de optimización exacta y una heurística escalable.

1. Línea Base de Optimización Exacta (SMMk)

Para establecer una verdad fundamental para la fiabilidad, los autores formulan el problema como un Programa Entero (IP).

• Formulación: Extienden la formulación estándar de Programación Entera para la partición $k$ de la Modularidad Máxima (MMk).
• Restricciones: El modelo incluye restricciones lineales para imponer los límites de tamaño. Específicamente, introducen restricciones que aseguran que para cualquier comunidad no vacía $c$, el número de nodos $\sum x_{ic} \ge n_{min}$, y para todas las comunidades potenciales, $\sum x_{ic} \le n_{max}$.
• Solver: El modelo se resuelve utilizando el optimizador Gurobi para obtener particiones globalmente óptimas (o casi óptimas) para grafos de tamaño pequeño a mediano. Esto sirve como línea base para evaluar la heurística.

2. Optimización Heurística (Leiden Restringido - CL)

Imponer directamente restricciones de tamaño dentro de heurísticas estándar de modularidad (como el algoritmo Leiden) es problemático porque los movimientos locales de nodos pueden violar fácilmente los límites de tamaño (por ejemplo, mover un nodo a una nueva comunidad singleton viola $n_{min} > 1$).

• Enfoque de Penalización: En lugar de un método de barrera (que restringe el espacio de búsqueda), los autores emplean un enfoque de penalización. Transforman el problema restringido en uno sin restricciones optimizando una función objetivo modificada:
  $$Q'(G, P) = Q(G, P) - \phi \Theta(P)$$
  Donde $\Theta(P)$ es una función de penalización para comunidades que violan las restricciones de tamaño, y $\phi$ es un peso de penalización.
• Función de Penalización: La penalización $\theta(n_c)$ para una comunidad de tamaño $n_c$ se define como:
  $$\theta(n_c) = \begin{cases} \sqrt{n_{min} - n_c} & \text{si } n_c < n_{min} \\ \sqrt{n_c - n_{max}} & \text{si } n_c > n_{max} \end{cases}$$
  Se elige la función raíz cuadrada porque es sub-aditiva, evitando que el algoritmo quede atrapado en óptimos locales donde dividir una comunidad grande que viola las restricciones en dos comunidades más pequeñas que también violan las restricciones produzca una penalización total menor.
• Programa Progresivo: El algoritmo comienza con $\phi = 0$ (sin restricciones). Si la partición resultante viola las restricciones, $\phi$ se incrementa (comenzando en $10^{-4}$ y duplicándose) y la optimización se reinicia desde la solución anterior. Esto continúa hasta que se encuentra una partición factible.

Resultados Clave

Los autores evaluaron el método propuesto Leiden Restringido (CL) contra el Leiden Sin Restricciones (UL) y la línea base de Programación Entera Restringida (CIP) en redes sintéticas y del mundo real.

Benchmarks Sintéticos

• Modelos de Partición Plantada: En redes con comunidades de verdad fundamental conocidas, CL y CIP superaron significativamente a UL en tasas de recuperación (medidas por la Información Mutua Ajustada, AMI), particularmente cuando el parámetro de mezcla era bajo a medio. UL falló frecuentemente en recuperar las comunidades plantadas porque produjo particiones con tamaños fuera del rango esperado.
• Anillo de Clíques: En un grafo de 50 cliques (tamaño 5) conectados secuencialmente, UL solo recuperó la partición correcta si el parámetro de resolución se ajustó manualmente a un rango específico ($[5, 40]$). En contraste, CL recuperó con precisión la partición plantada en la resolución predeterminada ($\gamma=1$) cuando se le dio el rango de tamaño correcto $[2, 8]$.
• Fiabilidad: Las tasas de recuperación de la heurística CL fueron consistentemente cercanas a, y a veces iguales a, la línea base exacta CIP, demostrando que la heurística no sacrifica la precisión por la velocidad en estos contextos.

Redes del Mundo Real

• Conectoma Cerebral: Aplicado a la red del conectoma cerebral de Budapest, UL produjo una partición trivial de cuatro comunidades (correspondientes a los hemisferios), la cual carece de utilidad en neurociencia.
• Alineación con el Dominio: Al aplicar CL con un rango de tamaño derivado del conocimiento experto (basado en los atlas Brainnetome y Schaefer, $[43, 187]$ nodos), el método produjo 6 comunidades. Este resultado se alinea mucho mejor con los clusters funcionales cerebrales conocidos (por ejemplo, los 7 clusters definidos por Yeo et al.) que el resultado sin restricciones.
• Control de la Variación: Los autores demostraron que cambiar el parámetro de resolución en UL controla el tamaño promedio de la comunidad pero falla en controlar la variación (varianza) de los tamaños. CL proporciona control directo tanto sobre la media como sobre la variación, asegurando que todas las comunidades caigan dentro de los límites especificados.

Significado y Afirmaciones

El artículo afirma que el método propuesto ofrece una manera principista de incorporar la experiencia del dominio en la detección de comunidades.

• Control Directo: A diferencia de la práctica de "prueba y error" de ajustar parámetros de resolución, CL permite a los usuarios definir explícitamente el tamaño mínimo y máximo de las comunidades, abordando directamente las necesidades de los expertos del dominio.
• Escalabilidad: Mientras que el método IP exacto (CIP) está limitado por la complejidad computacional a grafos más pequeños, la heurística CL es escalable y puede aplicarse a redes grandes, haciéndola práctica para aplicaciones del mundo real.
• Implementación: El método está implementado dentro del paquete de algoritmo Leiden en Python, haciéndolo accesible para uso inmediato.

Los autores concluyen que, si bien la modularidad tiene limitaciones conocidas (como el límite de resolución y la falta de una base estadística clara), la capacidad de imponer restricciones de tamaño mediante su heurística permite particiones más informativas y alineadas con el dominio. Sugieren que el trabajo futuro podría explorar la incorporación de restricciones de tamaño en otros marcos, como Modelos de Bloques Estocásticos (SBMs), para aprovechar estas restricciones dentro de un contexto de inferencia estadística.