Vector-Based Approach to the Max-Cut Problem: Conversion to Clustering and Validation on Structured Graphs - Silva, Jailon W. B. Oliveira da; Araújo, Carlos V. Dantas; Soares, Pablo L. Braga (Anais do Encontro Nacional de Inteligência Artificial e Computacional (ENIAC); 2025: Anais do XXII Encontro Nacional de Inteligência Artificial e Computacional, 2025)
Este trabalho propõe uma abordagem não supervisionada para o Problema do Corte Máximo (Max-Cut) via conversão em tarefa de agrupamento. Combina três representações de vértices (Node2Vec, Spectral e atributos locais) com algoritmos KMeans e hierárquico. Validação em 57 instâncias da Big Mac Library (coeficiente de aglomeração > 0.2) mostra desempenho superior da representação por atributos locais com KMeans (91.4% de similaridade, 41 instâncias > 90%), seguida por Spectral (82%) e Node2Vec (72%). Resultados indicam eficácia em grafos com alta aglomeração, com limitações em estruturas esparsas (coeficiente < 0.2). A abordagem substitui métodos combinatórios por análise vetorial direta, oferecendo solução escalável para Max-Cut em média escala.