Uma meta-heurística de Busca Tabu para o problema de agrupamento em grafos

• Processo: 11/10315-3
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de agosto de 2011
• Data de Término da vigência: 31 de julho de 2012
• Á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: Desiree Maldonado Carvalho
• 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): Meta-heurística Agrupamento em grafos Pesquisa Tabu
• Palavra(s)-Chave do Pesquisador: agrupamento em grafos | meta-heurísticas | Otimização

Resumo

O estudo de análise de agrupamento em grafos tem sido alvo de intensa investigação nas últimas décadas. Os principais motivos são: seus recentes avanços e o aumento considerável do número de suas aplicações em razão das inovações tecnológicas que provém dados que necessitam de tais ferramentas para seu processamento. Uma abordagem de estudo para agrupamento em grafos que vem se destacando é o de maximização de modularidade, que é de natureza estatística, e tem apresentado resultados bem satisfatórios para diversas aplicações. Entretanto, devido à sua natureza combinatorial, esse problema tem sido resolvido heuristicamente, o que compete a qualidade das soluções a aproximações das soluções ótimas. Este projeto visa o desenvolvimento de uma meta-heurística de busca tabu para resolver heuristicamente o problema de maximização de modularidade. Pretende-se aplicar essa meta-heurística a grafos com milhares de nós e arestas que são os sistemas mais difíceis de se obter bons resultados por meio de heurísticas para o mesmo problema. Além disso, pretende-se encontrar resultados melhores do que as melhores heurísticas da literatura, que serão utilizadas para comparar os resultados obtidos pela meta-heurística proposta. (AU)