Um estudo teórico do problema de agrupamento em grafos

Resumo

O desafio de encontrar grupos de vértices (ou comunidades) altamente relacionados em um grafo (ou rede), conhecido como o problema de detecção de comunidades em redes ou o problema de agrupamento em grafos, tem despertado um grande interesse em físicos, cientistas da computação, matemáticos, estatísticos, entre outros pesquisadores na última década. A razão desse grande interesse é sua ampla aplicabilidade e, também, devido ao surgimento, em 2002, de uma medida conhecida como modularidade que tem sido utilizada na detecção dessas comunidades, problema esse conhecido por maximização da modularidade. Apesar dos inúmeros trabalhos existentes na literatura para tratar esse problema, o estudo teórico do problema de maximização da modularidade é um dos grandes desafios do tema de detecção de comunidades em redes. Um estudo formal a respeito dessa medida conhecida como modularidade se faz necessário, pois, já foi comprovado que, apesar da mesma ser a mais utilizada atualmente para determinação de agrupamentos em grafos, ela tem um problema de escala, ou seja, tal medida não consegue detectar determinadas comunidades com baixo número de vértices em determinados tipos de rede. Por essa razão, um dos enfoques, talvez o principal, dessa colaboração com o Prof Leonidas Pitsoulis é um estudo formal por meio de teoria de matróides para melhor caracterizar essa medida amplamente utilizada na comunidade científica para detecção de comunidades em redes. Aliado a esse estudo, com essa colaboração pretende-se estudar alternativas na detecção de comunidades em redes, principalmente, nos grafos que já foram comprovados que a modularidade se apresenta ineficiente. Com ambos os enfoques, espera-se apresentar importante avanço na área de detecção de comunidades em redes. (AU)