Modularity maximization and community detection in complex networks through recursive and hierarchical annealing in the D-Wave Advantage quantum processing units

Resumen Técnico: Maximización de la Modularidad y Detección de Comunidades mediante Recocido Jerárquico Recursivo en D-Wave

Planteamiento del Problema
La detección de comunidades en redes complejas es un problema fundamental en la ciencia de redes, típicamente formulado como la maximización del índice de modularidad ($Q$). Esta tarea de optimización es NP-duro. Aunque existen algoritmos heurísticos clásicos (p. ej., Louvain, Leiden), estos no garantizan los óptimos globales. El recocido cuántico (QA) ofrece una vía potencial para resolver tales problemas NP-duros al encontrar el mínimo global de un paisaje de energía. Sin embargo, una barrera significativa para aplicar el QA puro a la detección de comunidades es la codificación del problema. Los enfoques estándar suelen depender de una codificación "one-hot" para representar $M$ comunidades utilizando $N \times M$ variables binarias. Esto requiere restricciones estrictas (asegurar que cada nodo pertenezca exactamente a una comunidad), que suelen imponerse mediante multiplicadores de Lagrange. El ajuste de los pesos de penalización para estos multiplicadores es empíricamente difícil y a menudo requiere conjeturas específicas del problema, lo que puede oscurecer el proceso cuántico y limitar la escalabilidad. Además, las soluciones híbridas cuántico-clásicas existentes suelen carecer de transparencia respecto a la división del trabajo entre los procesadores cuánticos y clásicos.

Metodología
Los autores proponen un nuevo algoritmo, Recocido Jerárquico (Hierarchical Annealing), diseñado para maximizar la modularidad mediante el uso de recocido cuántico puro en QPUs D-Wave Advantage sin codificación one-hot ni multiplicadores de Lagrange.

• Descomposición Binaria Recursiva: En lugar de asignar nodos a $M$ comunidades simultáneamente, el algoritmo subdivide la red de forma recursiva. Comienza con la red completa como una sola comunidad e iterativamente divide cada comunidad en dos subcomunidades. Esto transforma el problema en una secuencia de problemas de optimización binaria sin restricciones.
• Formulación QUBO:
  • Para redes no dirigidas, la ganancia de modularidad al dividir una comunidad $k$ en $k_1$ y $k_2$ se mapea a un problema de Optimización Binaria Cuadrática sin Restricciones (QUBO). La función de costo se deriva de la matriz de modularidad generalizada $B^k$, donde el objetivo es minimizar el cambio negativo en la modularidad ($p_k = -[Q(C_{k+1}) - Q(C_k)]$).
  • Para redes dirigidas, los autores abordan la asimetría de la matriz de modularidad optimizando la combinación lineal simetrizada $\frac{1}{2}(p_k + p_k^\top)$. Esto asegura que el primer paso de la jerarquía optimice la función global correcta y mantenga el formalismo QUBO sin términos lineales.
• Parámetro de Resolución ($\gamma$): El parámetro de resolución, que controla la escala de las comunidades detectadas, se integra directamente en el cálculo de la matriz de modularidad generalizada. El algoritmo permanece formalmente independiente de $\gamma$ con respecto a la estructura de optimización, lo que permite que sea tratado como un parámetro libre.
• Flujo de Ejecución: El proceso se ejecuta recursivamente (Algoritmo 1). Para cada paso, se calcula una matriz de modularidad generalizada, se construye un QUBO y se carga un empaquetamiento de clique desde un caché. El muestreador D-Wave realiza el recocido binario (QA) para encontrar la división óptima. La recursión se detiene cuando una división no produce mejoras (el cambio de modularidad es cero) o resulta en un conjunto vacío.
• Implementación: Los autores desarrollaron una biblioteca de Python, Qommunity, que se interconecta con el ecosistema de D-Wave. Utilizaron el sistema Advantage (topología Pegasus, grado 16) con estrategias de fuerza de cadena por defecto y votación por mayoría para cadenas rotas.

Contribuciones Clave

1. Recocido Cuántico Puro sin Restricciones: El trabajo demuestra un procedimiento sistemático para encontrar óptimos globales para la maximización de la modularidad utilizando solo recocedores puros, evitando la necesidad de codificación one-hot y la dificultad asociada de ajustar los multiplicadores de Lagrange.
2. Formalismo Generalizado: Los autores extienden el formalismo de la maximización de la modularidad para manejar redes no dirigidas, dirigidas y ponderadas dentro de un marco recursivo unificado.
3. Interpretabilidad: A diferencia de los resolvedores híbridos de "caja negra", la naturaleza recursiva del algoritmo produce un dendrograma de subdivisiones intermedias. Esto ofrece una visión interpretable de la jerarquía de comunidades, revelando cómo se despliega la estructura de la red en diferentes niveles de resolución.
4. Escalabilidad y Eficiencia: El estudio proporciona evidencia empírica de que este enfoque produce soluciones al menos tan óptimas como los algoritmos clásicos de vanguardia (Louvain, Leiden), manteniendo tiempos de computación tratables.

Resultos

• Evaluación Comparativa (Benchmarking): El algoritmo fue probado en varias topologías de red, incluyendo Erdős-Rényi, Barabási-Albert, redes agrupadas de ley de potencia y redes de escala libre dirigidas.
  • En cadenas simples de 3 cliques y en la red Zachary Karate Club, el H. Annealing logró puntuaciones de modularidad idénticas o ligeramente superiores a las de Louvain y Leiden.
  • En modelos de bloques estocásticos (SBM), el método recuperó con éxito las comunidades plantadas a través de diversos parámetros de mezcla, compitiendo competitivamente contra métodos de inferencia probabilística.
  • Para redes de escala libre, el algoritmo mostró un rendimiento robusto, superando a menudo a sus contrapartes clásicas en términos de puntuaciones de modularidad, particularmente cuando existían jerarquías inherentes.
• Sensibilidad de la Resolución: El algoritmo se mantuvo estable a través de diferentes valores del parámetro de resolución $\gamma$. Aunque el rendimiento decayó ligeramente para valores extremos de $\gamma$ en redes dirigidas, se mantuvo competitivo cerca de $\gamma=1$.
• Complejidad Computacional:
  • El preprocesamiento clásico (cálculo de la matriz de modularidad) escala como $O(n^2)$.
  • La complejidad del árbol recursivo se estima en $O(n \log n)$ basado en el teorema de Akra-Bazzi, asumiendo divisiones equilibradas.
  • Empíricamente, los tiempos de acceso a la QPU escalaron logarítmicamente con el tamaño de la red ($t \propto \ln N$), lo que sugiere un escalamiento eficiente para el componente cuántico.
  • El tiempo de ejecución total está dominado por la comunicación y los retrasos de la cola más que por el tiempo de ejecución de la propia QPU.
• Aplicación en el Mundo Real: El método se aplicó a una red real de conectividad estructural cerebral (166 nodos). La estructura de comunidad resultante y el dendrograma fueron altamente consistentes con los encontrados por Louvain y Leiden, con diferencias menores solo en bordes frontoparietales altamente interconectados.

Significancia y Reivindicaciones
El artículo posiciona este trabajo como un "primer paso hacia un uso de práctica aplicable del recocido cuántico puro". Los autores afirman que cierran la brecha entre la ciencia de redes y la computación cuántica al demostrar que el QA puro puede resolver problemas de detección de comunidades sin depender de soluciones híbridas de "caja negra" o del complejo ajuste de restricciones.

La significancia reside en:

• Transparencia: Proporcionar una solución recursiva interpretable (dendrogramas) en lugar de una partición plana única, lo cual es valioso para descubrir jerarquías ocultas en sistemas complejos como las redes cerebrales.
• Viabilidad: Mostrar que el hardware cuántico actual (D-Wave Advantage) puede manejar tareas de detección de comunidades de tamaño práctico (hasta ~166 nodos probados, limitado por la topología Pegasus) con un rendimiento competitivo.
• Cambio Metodológico: Ofrecer una alternativa viable a la codificación one-hot que evita el ajuste empírico de los pesos de penalización, lo que potencialmente hace que la optimización cuántica sea más accesible para el análisis de redes.

Los autores mantienen la modestia, reconociendo que el proceso recursivo no garantiza la optimalidad global (una limitación compartida por todas las heurísticas para este problema NP-duro) y que la escalabilidad a redes muy grandes requiere actualmente resolvedores híbridos o acceso local a la QPU para mitigar los retrasos de comunicación. No pretenden una superioridad universal sobre los métodos clásicos, sino destacar el potencial del recocido cuántico para proporcionar soluciones significativas, interpretables e igualmente óptimas en contextos topológicos específicos.