Este trabalho foi publicado pelo Galoá e tem um DOI depositado. Para citar este trabalho, use um dos padrões abaixo:
Caso você seja um dos co-autores e queira cadastrar esse trabalho no seu Currículo Lattes, use o seguinte código: doi > 10.59254/sbpo-2019-106963
Se você NUNCA registrou um DOI no seu Lattes, veja nosso tutorial!Empresas aéreas produzem um grande volume de dados de passagens. Esses dados podem ser modelados como dígrafos, nos quais os vértices representam os aeroportos e os arcos os voos entre os aeroportos. Agrupar os vértices de tais dígrafos pode auxiliar outras aplicações, como, por exemplo, na solução heurística de um problema de otimização que consiste em encontrar uma rota aérea que minimize custos de passagens, considerando tempos de estadia e de forma que o viajante visite todas as cidades. Nesse contexto, o agrupamento dos vértices desses dígrafos visa identificar grupos de aeroportos que possuam maior conectividade intra-grupo do que inter-grupos. Neste trabalho foi desenvolvido um algoritmo para o agrupamento de dígrafos em que os vértices podem pertencer a mais de uma comunidade (overlapping). Ele foi baseado nos métodos de propagação de rótulos Speaker-Listener Label Propagation Algorithm (SLPA) e Genetic Algorithm - Label Propagation (GA-LP) da literatura. O SLPA é uma extensão do algoritmo Label Propagation Algorithm (LPA) capaz de detectar comunidades com overlapping. O GA-LP, por sua vez, é um algoritmo genético para agrupar vértices em dígrafos com custo computacional linear. Como o GA-LP foi proposto inicialmente para lidar com comunidades disjuntas, no algoritmo proposto a sua função fitness foi substituída por uma medida da literatura baseada na de modularidade para avaliar comunidades com overlapping. Para avaliar os resultados do algoritmo proposto, foram realizados experimentos computacionais com dígrafos compilados a partir de uma base de dados que contém informações de cerca de 13 milhões de voos, dispostos em um período de 1 ano em 2400 aeroportos. Em particular, um experimento com um dígrafo que representa os voos ocorridos nos principais aeroportos do Brasil ao longo de um período de quatro bimestres mostrou que os voos tendem a se manter estáveis ao longo dos bimestres, com poucas modificações em suas rotas, provenientes de eventuais sazonalidades. Por exemplo, todos os aeroportos do período de novembro à dezembro foram classificados em comunidades com overlapping, indicando um maior número de conexões aéreas com aeroportos em diferentes comunidades na época de fim de ano. Além disso, os aeroportos tendem ser classificados em comunidades em comum com hubs aéreos, ou seja, aeroportos com muitas conexões. Em experimentos com dígrafos obtidos a partir da seleção aleatória de aeroportos da base de dados, os resultados obtidos pelo algoritmo foram próximos aos da literatura. Nesse sentido, trabalhos futuros envolvem a aplicação do algoritmo proposto para servir de apoio à problemas que utilizem esses dados de passagens aéreas como objeto de estudo.
Com ~200 mil publicações revisadas por pesquisadores do mundo todo, o Galoá impulsiona cientistas na descoberta de pesquisas de ponta por meio de nossa plataforma indexada.
Confira nossos produtos e como podemos ajudá-lo a dar mais alcance para sua pesquisa:
Esse proceedings é identificado por um DOI , para usar em citações ou referências bibliográficas. Atenção: este não é um DOI para o jornal e, como tal, não pode ser usado em Lattes para identificar um trabalho específico.
Verifique o link "Como citar" na página do trabalho, para ver como citar corretamente o artigo