Um estudo teórico do problema de agrupamento em grafos

• Processo: 12/10698-2
• Modalidade de apoio: Auxílio à Pesquisa - Pesquisador Visitante - Internacional
• Data de Início da vigência: 01 de outubro de 2012
• Data de Término da vigência: 15 de outubro de 2012
• Á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
• Pesquisador visitante: Leonidas S. Pitsoulis
• Instituição do Pesquisador Visitante: Aristotle University of Thessaloniki (AUTh) , Grécia
• 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
• Município da Instituição Sede: São José dos Campos
• Vinculado ao auxílio: 10/20231-9 - Uma abordagem teórica e computacional para o problema de detecção de comunidades em redes, AP.JP
• Assunto(s): Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: agrupamento em grafos | Modularidade | teoria de matróides | Otimização

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)