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

• Processo: 14/13696-6
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de agosto de 2014
• Data de Término da vigência: 30 de junho de 2015
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Metodologia e Técnicas da Computação
• Pesquisador responsável: Mariá Cristina Vasconcelos Nascimento Rosset
• Beneficiário: Rodrigo Francisquini da Silva
• Instituição Sede: Instituto de Ciência e Tecnologia (ICT). Universidade Federal de São Paulo (UNIFESP). Campus São José dos Campos. São José dos Campos , SP, Brasil
• Vinculado ao auxílio: 10/20231-9 - Uma abordagem teórica e computacional para o problema de detecção de comunidades em redes, AP.JP
• Assunto(s): Algoritmos Heurística
• Palavra(s)-Chave do Pesquisador: agrupamento em grafos | Algoritmos espectrais | detecção de comunidades em redes | Otimização

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.