O problema da descoberta do subgrafo mais denso (DSD) é uma tarefa fundamental em mineração de grafos com aplicações em redes sociais, bioinformática, bancos de dados de grafos e engenharia de sistemas. Dado um grafo G = (V, E) e um inteiro k ≥ 2, o objetivo é encontrar um subconjunto de vértices D ⊆ V cujo subgrafo induzido G(D) maximize a densidade de k-cliques, definida como o número de k-cliques por vértice. Valores maiores de k capturam padrões de conectividade de ordens superiores além das arestas, permitindo a descoberta de estruturas mais coesas. Apresentamos uma estrutura acelerada por GPU que integra um algoritmo de enumeração de k-cliques a nível de warp juntamente com técnicas de poda baseadas em núcleo de clique e poda de arestas para reduzir o espaço de busca, seguido de decomposição paralela de componentes conectados para dividir o grafo podado em subproblemas menores independentes. A solução exata é então obtida formulando o DSD em cada componente conectada como um problema de fluxo máximo e resolvendo-o usando um algoritmo de push-relabel centrado em vértices, aprimorado com limites de densidade superiores e inferiores apertados e estruturas de dados compactas e amigáveis para GPU. Experimentos em um conjunto diversificado de grafos reais e sintéticos mostram acelerações substanciais em relação à implementação atual em CPU, enquanto produzem soluções idênticas.
Manzoor et al. (Mon,) estudaram essa questão.