Uma abordagem teórica e computacional para o problema de detecção de comunidades em redes

Resumo

O problema de detecção de comunidades consiste em encontrar grupos de nós em um grafo de forma que estes nós compartilhem de alta conectividade intra-comunidade. Seu objetivo é encontrar partições em uma rede ou grafo. Uma de suas aplicações compreende, por exemplo, a determinação de comunidades em redes sociais para explicar o comportamento de grupos de indivíduos baseando-se em suas interações. Esse problema pode ser abordado usando diversos objetivos e medidas de conectividade. Nas últimas décadas, o problema de detecção de comunidades recebeu mais atenção devido ao seu avanço com a derivação de uma nova medida de avaliação de comunidades (partições de um grafo), a modularidade. Desde então, diversos trabalhos que otimizam (maximizam) essa medida para encontrar partições foram propostos. Em alguns desses trabalhos, foi observado que, para determinados tipos de redes, as comunidades encontradas por meio de algoritmos baseados na maximização da modularidade representam um agrupamento fraco. Dessa forma, observou-se a necessidade de um estudo teórico que explique melhor o comportamento das partições encontradas por meio da otimização da modularidade. Neste projeto, a pesquisadora responsável pretende abordar dois tópicos visando o modelo de maximização de modularidade: seu estudo teórico utilizando teoria de matróides; e o desenvolvimento de algoritmos baseados na sua relaxação espectral, os hibridizando com metaheurísticas. Este projeto consiste na continuação da proposta do Proc. no. 2009/16603-0 referente ao auxílio regular de Pós-doutorado. O auxílio iniciou-se em março de 2010 e foi cancelado em outubro de 2010 (devido à nomeação da candidata em vaga de Professor Adjunto na UNIFESP). (AU)