Teoria Espectral para a Análise de Agrupamento em Grafos

Resumo

A literatura é vasta quando se trata de algoritmos para abordar o problema de agrupamento em grafos. Algoritmos baseados em relaxação espectral de diversas formulaçõesdesse problema são responsáveis pela classe de heurísticas espectrais, conceitualmentebastante elegantes e com resultados bem satisfatórios. O custo computacional desses algoritmos, entretanto, muitas vezes os tornam inviáveis para lidar com grafos muito grandes.Além disso, a literatura aponta que relaxações baseadas na matriz de adjacências não conseguem detectar clusters de certos tipos de grafos esparsos. Nesse sentido, recentemente,foi proposta uma excelente alternativa para abordar grafos esparsos considerando a relaxação espectral de uma nova matriz, baseada em caminhos sem backtracking no grafo.Este projeto visa abordar o problema de agrupamento em grafos de larga escala por novasheurísticas espectrais. Por meio da manipulação da matriz sem backtracking, espera-se serpossível encontrar grupos em grafos grandes com milhares de vértices e arestas e refinarresultados obtidos na literatura para esses grafos com novas estratégias introduzidas nesseestudo. Além disso, intenta-se contribuir com aspectos teóricos e investigar novas medidasde avaliação que melhor mensurem a qualidade em grafos com essas características.