Um algoritmo genético para o problema de agrupamento de dígrafos dinâmicos

• Processo: 17/17689-2
• Linha de fomento: Bolsas no Brasil - Iniciação Científica
• Vigência (Início): 01 de novembro de 2017
• Vigência (Término): 31 de outubro de 2018
• Área do 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: Igor Luppi de Oliveira
• 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
• Assunto(s): Agrupamento em grafos Dígrafos Reconhecimento de padrões Heurística

Resumo

Estratégias de agrupamento em grafos são úteis para, por exemplo, reconhecer padrões em dados relacionais de larga escala. Em particular, dados de passagens de empresas aéreas podem ser modelados como grafos orientados (dígrafos). Entretanto, para uma melhor representação desses dados, deve-se levar em consideração na modelagem as alterações nos custos e na disponibilidade de passagens. Dessa forma, agrupar esses grafos que alteram com o tempo, conhecidos como grafos dinâmicos, possibilita uma melhor inferência desses dados. Este projeto propõe o desenvolvimento de um algoritmo de baixo custo computacional para realizar o agrupamento de grafos dinâmicos, tendo como estudo de caso, dados de passagens aéreas. O algoritmo será baseado nos algoritmos SLPA e GA-LP que obtiveram bons resultados para grafos grandes e apresentam custo computacional linear. Ao término do projeto, espera-se que os experimentos computacionais atestem o desempenho superior do algoritmo proposto em relação a estratégias de agrupamento em grafos dinâmicos, segundo métricas de avaliação como, por exemplo, a modularidade. (AU)