Uma metaheurística multi-nível para maximização da modularidade em grafos de larga escala

• Processo: 12/12182-3
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de setembro de 2012
• Data de Término da vigência: 31 de maio de 2013
• Á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: Camila Pereira dos Santos Tautenhain
• 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): Heurística Otimização combinatória Agrupamento em grafos Modularidade biológica Estado da arte Metodologia e técnicas de computação
• Palavra(s)-Chave do Pesquisador: agrupamento em grafos | heuristicas | Otimização Combinatória | agrupamento em grafos

Resumo

O problema de detecção de comunidades em redes objetiva identificar, a partir de um dado grafo, grupos de vértices altamente relacionados. A identificação desses grupos é aplicada em diversas áreas do conhecimento, motivo pelo qual o problema vem sendo bastante estudado. A maximização da modularidade é uma abordagem bastante utilizada para detecção de comunidades em redes. Entretanto, o problema de decidir se uma partição tem modularidade máxima é NP-Completo, de forma que é bastante comum encontrar estratégias heurísticas na literatura para a sua solução. A premissa do projeto é propor, com base na literatura, uma heurística para o problema da maximização da modularidade eficiente para grafos de larga escala para os quais existem heurísticas na literatura em número reduzido. Espera-se que a heurística proposta, além de eficiente, encontre soluções competitivas com o atual estado da arte.(AU)