Advanced search
Start date

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


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)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

Please report errors in scientific publications list by writing to: