Subgrafos coesos

• Processo: 24/18049-0
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de abril de 2025
• Data de Término da vigência: 31 de março de 2029
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Cristina Gomes Fernandes
• Beneficiário: Yan Soares Couto
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Assunto(s): Otimização combinatória Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: Mineração de Grafos | Otimização Combinatória | teoria dos grafos | Teoria dos Grafos

Resumo

Grafos são muitas vezes usados para modelar estruturas reais como, por exemplo, redes sociais ou interações entre proteínas. Nessas situações, se torna muitas vezes importante a visualização e análise destes grafos para extração de padrões e informações relevantes (mineração de dados). Um dos interesses nessa área é a busca por comunidades, como por exemplo um grupo de amigos próximos em uma rede social. Isso pode ser feito pela busca de subgrafos coesos, que são pequenas partes de um grafo que consistem de entidades similares densamente conectadas com certas propriedades.O problema de buscar subgrafos coesos pode ser abordado de diversas formas, como busca por cliques, k-núcleos ou componentes fortemente conexos, e pode ser estudado em diversos modelos de grafos, como grafos dirigidos, com peso, dinâmicos (com arestas sendo adicionadas e removidas), e sob diferentes modelos algorítmicos, por exemplo o modelo LP (localmente persistente) em que cada vértice acessa apenas informação local, ou o modelo Congest, um modelo distribuído em que o processamento ocorre nos próprios vértices, que podem se comunicar pelas arestas.O interesse do projeto é o estudo e busca de novos algoritmos e resultados na área de subgrafos coesos. Buscamos resultados teóricos e práticos, com atenção à implementação dos algoritmos, e experimentação com dados reais.