A genetic algorithm for the problem of clustering dynamic digraphs

• Grant number: 17/17689-2
• Support type: Scholarships in Brazil - Scientific Initiation
• Effective date (Start): November 01, 2017
• Effective date (End): October 31, 2018
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
• Principal researcher: Mariá Cristina Vasconcelos Nascimento Rosset
• Grantee: Igor Luppi de Oliveira
• Home Institution: 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, Brazil

Abstract

Graph clustering strategies are useful for pattern recognition in large scale relational data, for example. In particular, airline ticket data can be modeled as oriented graphs (digraph). However, for better representation of these data, one must take into account the changes in costs and tickets availability. Thus, clustering these graphs that change over time, known as dynamic graphs, allows a better inference of these data. This project proposes the development of a low computational cost algorithm for the dynamic graph clustering, having airline ticket data as study case. The algorithm will be based on the SLPA and GA-LP algorithms that obtained good results for large scale graphs and present linear computational cost. At the end of this project, it is expected that the computational experiments attest the superior performance of the proposed algorithm in respect with dynamic graph clustering strategies, according to evaluation metrics such as, for example, the modularity. (AU)