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

Resumo Técnico: Maximização de Modularidade e Detecção de Comunidades via Recozimento Hierárquico Recursivo no D-Wave

Definição do Problema
A detecção de comunidades em redes complexas é um problema fundamental na ciência de redes, tipicamente formulado como a maximização do índice de modularidade ($Q$). Esta tarefa de otimização é NP-difícil. Embora existam algoritmos heurísticos clássicos (ex: Louvain, Leiden), eles não garantem ótimos globais. O Recozimento Quântico (QA) oferece um caminho potencial para resolver tais problemas NP-difíceis ao encontrar o mínimo global de um landscape de energia. No entanto, uma barreira significativa para a aplicação de QA puro à detecção de comunidades é a codificação do problema. Abordagens padrão frequentemente dependem da codificação "one-hot" para representar $M$ comunidades usando $N \times M$ variáveis binárias. Isso exige restrições rígidas (garantindo que cada nó pertença a exatamente uma comunidade), que são tipicamente impostas via multiplicadores de Lagrange. Ajustar os pesos de penalidade para esses multiplicadores é empiricamente difícil e frequentemente requer suposições específicas do problema, o que pode obscurecer o processo quântico e limitar a escalabilidade. Além disso, soluções híbridas quântico-clássicas existentes muitas vezes carecem de transparência quanto à divisão de trabalho entre os processadores clássico e quântico.

Metodologia
Os autores propõem um novo algoritmo, Recozimento Hierárquico (Hierarchical Annealing), projetado para maximizar a modularidade usando recozcimento quântico puro em QPUs D-Wave Advantage sem codificação one-hot ou multiplicadores de Lagrange.

• Decomposição Binária Recursiva: Em vez de atribuir nós a $M$ comunidades simultaneamente, o algoritmo subdivide recursivamente a rede. Ele começa com a rede inteira como uma única comunidade e, iterativamente, divide cada comunidade em duas subcomunidades. Isso transforma o problema em uma sequência de problemas de otimização binária sem restrições.
• Formulação QUBO:
  • Para redes não direcionadas, o ganho de modularidade ao dividir uma comunidade $k$ em $k_1$ e $k_2$ é mapeado para um problema de Otimização Binária Quadrática Sem Restrições (QUBO). A função de custo é derivada da matriz de modularidade generalizada $B^k$, onde o objetivo é minimizar a mudança negativa na modularidade ($p_k = -[Q(C_{k+1}) - Q(C_k)]$).
  • Para redes direcionadas, os autores abordam a assimetria da matriz de modularidade otimizando a combinação linear simetrizada $\frac{1}{2}(p_k + p_k^\top)$. Isso garante que o primeiro passo da hierarquia otimize a função global correta e mantenha o formalismo QUBO sem termos lineares.
• Parâmetro de Resolução ($\gamma$): O parâmetro de resolução, que controla a escala das comunidades detectadas, é integrado diretamente no cálculo da matriz de modularidade generalizada. O algoritmo permanece formalmente independente de $\gamma$ em relação à estrutura de otimização, permitindo que seja tratado como um parâmetro livre.
• Fluxo de Execução: O processo é executado recursivamente (Algoritmo 1). Para cada etapa, uma matriz de modularidade generalizada é computada, um QUBO é construído e um embedding de clique é carregado de um cache. O amostrador D-Wave realiza o QA binário para encontrar a divisão ideal. A recursão para quando uma divisão não gera melhoria (mudança de modularidade é zero) ou resulta em um conjunto vazio.
• Implementação: Os autores desenvolveram uma biblioteca Python, Qommunity, que faz interface com o ecossistema D-Wave. Eles utilizaram o sistema Advantage (topologia Pegasus, grau 16) com estratégias de força de cadeia padrão e votação por maioria para cadeias quebradas.

Principais Contribuições

1. Recozimento Quântico Puro sem Restrições: O trabalho demonstra um procedimento sistemático para encontrar ótimos globais para maximização de modularidade usando apenas recededores puros, contornando a necessidade de codificação one-hot e a dificuldade associada ao ajuste de multiplicadores de Lagrange.
2. Formalismo Generalizado: Os autores estendem o formalismo de maximização de modularidade para lidar com redes não direcionadas, direcionadas e ponderadas dentro de um arcabouço recursivo unificado.
3. Interpretabilidade: Ao contrário dos solvers híbridos de "caixa-preta", a natureza recursiva do algoritmo produz um dendrograma de subdivisões intermediárias. Isso oferece uma visão interpretável da hierarquia de comunidades, revelando como a estrutura da rede se desenrola em diferentes níveis de resolução.
4. Escalabilidade e Eficiência: O estudo fornece evidências empíricas de que esta abordagem produz soluções pelo menos tão ótimas quanto algoritmos clássicos de ponta (Louvain, Leiden), mantendo tempos de computação tratáveis.

Resultados

• Benchmarking: O algoritmo foi testado em várias topologias de rede, incluindo Erdős-Rényi, Barabási-Albert, redes agrupadas de lei de potência e redes de escala livre direcionadas.
  • Em cadeias simples de 3 cliques e na rede Zachary Karate Club, o H. Annealing alcançou pontuações de modularidade idênticas ou ligeiramente superiores às do Louvain e Leiden.
  • Em modelos de blocos estocásticos (SBM), o método recuperou com sucesso comunidades plantadas através de variados parâmetros de mistura, performando competitivamente contra métodos de inferência probabilística.
  • Para redes de escala livre, o algoritmo mostrou desempenho robusto, frequentemente superando contrapartes clássicas em termos de pontuações de modularidade, particularmente quando hierarquias inerentes estavam presentes.
• Sensibilidade de Resolução: O algoritmo permaneceu estável através de diferentes valores do parâmetro de resolução $\gamma$. Embora o desempenho tenha degradado ligeiramente para valores extremos de $\gamma$ em redes direcionadas, ele permaneceu competitivo próximo a $\gamma=1$.
• Complexidade Computacional:
  • O pré-processamento clássico (computação da matriz de modularidade) escala como $O(n^2)$.
  • A complexidade da árvore recursiva é estimada em $O(n \log n)$ baseado no teorema de Akra-Bazzi, assumindo divisões equilibradas.
  • Empiricamente, os tempos de acesso à QPU escalaram logaritmicamente com o tamanho da rede ($t \propto \ln N$), sugerindo um escalonamento eficiente para o componente quântico.
  • O tempo de execução total é dominado por overheads de comunicação e fila, em vez do tempo de execução da própria QPU.
• Aplicação no Mundo Real: O método foi aplicado a uma rede real de conectividade estrutural cerebral (166 nós). A estrutura de comunidade resultante e o dendrograma foram altamente consistentes com os encontrados pelo Louvain e Leiden, com diferenças menores apenas em bordas frontoparietais altamente interconectadas.

Significância e Alegações
O artigo posiciona este trabalho como um "primeiro passo para um uso prático aplicável de recozcimento quântico puro". Os autores alegam que conseguiram unir a ciência de redes e a computação quântica ao demonstrar que o QA puro pode resolver problemas de detecção de comunidades sem depender de soluções híbridas de "caixa-preta" ou ajustes complexos de restrições.

A significância reside em:

• Transparência: Fornecer uma solução recursiva interpretável (dendrogramas) em vez de uma partição plana única, o que é valioso para descobrir hierarquias ocultas em sistemas complexos como redes cerebrais.
• Viabilidade: Mostrar que o hardware quântico atual (D-Wave Advantage) pode lidar com tarefas de detecção de comunidades de tamanho prático (até ~166 nós testados, limitado pela topologia Pegasus) com desempenho competitivo.
• Mudança Metodológica: Oferecer uma alternativa viável à codificação one-hot que evita o ajuste empírico de pesos de penalidade, tornando potencialmente a otimização quântica mais acessível para análise de redes.

Os autores permanecem modestos, reconhecendo que o processo recursivo não garante a otimalidade global (uma limitação compartilhada por todas as heurísticas para este problema NP-difícil) e que a escalabilidade para redes muito grandes atualmente requer solvers híbridos ou acesso local à QPU para mitigar os overheads de comunicação. Eles não reivindicam superioridade universal sobre métodos clássicos, mas destacam o potencial do recozcimento quântico para fornecer soluções significativas, interpretáveis e igualmente ótimas em contextos topológicos específicos.