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

• Processo: 17/17689-2
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de novembro de 2017
• Data de Término da vigência: 31 de outubro de 2018
• Á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: 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
• Palavra(s)-Chave do Pesquisador: agrupamento em grafos | detecção de comunidades em redes | Grafos Dinamicos | heuristicas | Agrupamento em grafos

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)