Ciência de Computadores
Descrição da Oportunidade
A contagem de subgrafos é uma tarefa fundamental em análise de redes, estando na base de metodologias amplamente usadas como network motifs ou graphlets, aplicadas em domínios tão diversos como biologia, redes sociais ou redes de transportes. Trata-se, no entanto, de um problema computacionalmente muito exigente, e ao longo das últimas duas décadas foram propostos numerosos algoritmos exatos para o resolver, com diferentes estratégias, limitações e desempenhos. O trabalho terá como ponto de partida o survey "A Survey on Subgraph Counting: Concepts, Algorithms and Applications to Network Motifs and Graphlets" (Ribeiro et al., ACM Computing Surveys, 2021), que fornece uma taxonomia estruturada de algoritmos exatos, aproximados e paralelos, com indicação de quais têm implementações publicamente disponíveis.
Habilitações Académicas
Estudantes de Licenciatura ou Mestrado em Ciência de Computadores, Informática ou áreas afins.
Requisitos Mínimos
- Boa capacidade de programação (C/C++, Python, ou similar);- Conhecimentos básicos de estruturas de dados e algoritmos, nomeadamente teoria de grafos;- Autonomia na instalação e configuração de software (compilação, gestão de dependências, ambientes Linux);- Boa capacidade de organização e comunicação escrita.
Fatores de Preferência
- Experiência prévia com programação em C/C++ (muitas das implementações a comparar estão escritas nestas linguagens); - Conhecimentos de teoria de grafos e/ou análise de redes complexas; - Experiência com scripting para automatização de experiências (ex.: Bash, Python) e análise/visualização de dados (ex.: Pandas, Matplotlib); - Experiência com Git/GitHub para gestão de código e documentação reprodutível.
Período de candidatura
Desde 30 Jul 2026 a 12 Aug 2026
Centro
Sistemas de Computação Avançada