Uma heurística espectral para o problema de detecção de comunidades em redes

Resumo

Heurísticas espectrais para problemas de agrupamento em grafos ou de detecção de comunidades em redes têm sido alvo de constante estudo principalmente devido ao avanço de métodos numéricos para a determinação do conjunto de autovalores e autovetores de ma- trizes. Aliado a isso, a elegância matemática e a qualidade das soluções obtidas por essas heurísticas são fatores de grande apelo para seu estudo. Neste projeto, pretende-se orientar um aluno de IC para que ele adquira conhecimento do problema de agrupamento em grafos, mais especificamente, do problema de maximização de modularidade. Além disso, tem-se a intenção de apresentar a ele a motivação de heurísticas espectrais e a relaxação espectral do problema mencionado. A partir de tal relaxação, uma nova heurística espectral será desenvolvida de forma a ser mais eficiente do que a baseada em programação dinâmica conhecida da literatura. (AU)