Graph approximation
Fast, provably bounded graph metrics on networks with millions of edges.
- Year
- 2026
- Role
- Rebuilt and extended a team project
- Stack
- C++ · CMake · GoogleTest · Python
The problem
On graphs the size of a web crawl, exact algorithms for classic metrics stop being practical: exact betweenness centrality is O(VE). This project implements approximation algorithms with provable error bounds, and checks them against the exact versions where that is still feasible.
How it works
- Four algorithms: HyperANF for average path length, Riondato sampling for betweenness, uniform-wedge sampling for the clustering coefficient, and Karger for min-cut.
- They ship as subcommands of one CLI that read and write graphs on stdin and stdout, so they compose.
- A benchmark pipeline regenerates the report’s figures on the cnr-2000 web graph (325K nodes, 3.2M edges) and 50 synthetic scale-free networks.
Key decisions
Seeded reproducibility
Every randomised algorithm takes a seed and produces byte-identical reruns, which makes the tests deterministic and the figures reproducible.
Check against the original report
HyperANF results on cnr-2000 land within HyperLogLog’s 1.06/√m theoretical bound for every register size tested.
Results
- Average path length estimates within the theoretical error bound
- Full report figures regenerated in about four minutes
- 16 deterministic tests and CI
HyperANF runtime scales with E log V
Riondato sampling runtime
What I’d do next
Reimplementing the clustering experiments that were missing from the original sources.
The original implementation and report were joint work with Miguel Sena, Joana Alves and Tomás Vieira.