Computer Science
Work description
Subgraph counting is a fundamental task in network analysis, serving as the basis for widely used methodologies such as network motifs and graphlets, which are applied in fields as diverse as biology, social networks, and transportation networks. It is, however, a computationally very demanding problem. Over the past two decades, numerous exact algorithms have been proposed to solve it, each with different strategies, limitations, and performance characteristics. This work will take as its starting point the survey “A Survey on Subgraph Counting: Concepts, Algorithms, and Applications to Network Motifs and Graphlets” (Ribeiro et al., ACM Computing Surveys, 2021), which provides a structured taxonomy of exact, approximate, and parallel algorithms, indicating which ones have publicly available implementations.
Academic Qualifications
Undergraduate or graduate students in computer science, informatics, or related fields.
Minimum profile required
- Strong programming skills (C/C++, Python, or similar);- Basic knowledge of data structures and algorithms, particularly graph theory;- Ability to independently install and configure software (compilation, dependency management, Linux environments);- Strong organizational skills and written communication skills.
Preference factors
- Previous experience with C/C++ programming (many of the implementations to be compared are written in these languages); - Knowledge of graph theory and/or complex network analysis; - Experience with scripting for automating experiments (e.g., Bash, Python) and data analysis/visualization (e.g., Pandas, Matplotlib); - Experience with Git/GitHub for code management and reproducible documentation;
Application Period
Since 30 Jul 2026 to 12 Aug 2026
Centre
Advanced Computing Systems