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: 10/20231-9
Linha de fomento:Auxílio à Pesquisa - Apoio a Jovens Pesquisadores
Vigência: 01 de julho de 2011 - 31 de dezembro de 2015
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Metodologia e Técnicas da Computação
Pesquisador responsável:Mariá Cristina Vasconcelos Nascimento Rosset
Beneficiário:Mariá Cristina Vasconcelos Nascimento Rosset
Instituição-sede: 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, Brasil
Auxílios(s) vinculado(s):12/10698-2 - Um estudo teórico do problema de agrupamento em grafos, AV.EXT
Bolsa(s) vinculada(s):14/13696-6 - Uma heurística espectral para o problema de detecção de comunidades em redes, BP.IC
12/12182-3 - Uma metaheurística multi-nível para maximização da modularidade em grafos de larga escala, BP.IC
11/10315-3 - Uma meta-heurística de Busca Tabu para o problema de agrupamento em grafos, BP.IC
11/13638-8 - Uma metaheurística de colônia de formigas para o problema de detecção de comunidades em redes, BP.IC
Assunto(s):Matemática da computação  Meta-heurística  Teoria dos grafos  Grafos aleatórios  Matroides  Algoritmos 

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)

Publicações científicas
(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)
MAXIMO, VINICIUS R.; NASCIMENTO, MARIA C. V.; CARVALHO, ANDRE C. P. L. F. Intelligent-guided adaptive search for the maximum covering location problem. Computers & Operations Research, v. 78, p. 129-137, FEB 2017. Citações Web of Science: 6.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.
Mapa da distribuição dos acessos desta página
Para ver o sumário de acessos desta página, clique aqui.