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

• Processo: 09/16603-0
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Data de Início da vigência: 01 de março de 2010
• Data de Término da vigência: 31 de outubro de 2010
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Metodologia e Técnicas da Computação
• Pesquisador responsável: Franklina Maria Bragion de Toledo
• Beneficiário: Mariá Cristina Vasconcelos Nascimento Rosset
• Instituição Sede: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil
• Assunto(s): Meta-heurística Teoria dos grafos Pesquisa operacional
• Palavra(s)-Chave do Pesquisador: agrupamento de dados em grafo | detecção de comunidades | Metaheurísticas | relaxação espectral | Teoria de Grafos | Pesquisa Operacional

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. Este problema também pode ser encontrado na literatura como o problema de agrupamento de dados em grafos ou como o de particionamento de grafos. 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. Este 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 destas partições, a modularidade. Desde então, diversos trabalhos que otimizam (maximizam) esta medida para encontrar partições foram propostos. Em alguns destes trabalhos, foi observado que, para determinados tipos de redes, as comunidades encontradas por meio da maximização da modularidade representam um agrupamento fraco. Desta 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. Além disso, foi observado que os algoritmos espectrais, em geral, têm sido propostos sem a exploração dos limitantes encontrados pela relaxação espectral na avaliação da qualidade das partições. Desta forma, a candidata pretende, neste projeto, 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.