Busca avançada
Ano de início
Entree

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

Processo: 09/16603-0
Linha de fomento:Bolsas no Brasil - Pós-Doutorado
Vigência (Início): 01 de março de 2010
Vigência (Término): 31 de outubro de 2010
Área do 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   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.