Creating Robust and Fair Graph Structures for Connectivity and Clustering
COM3 Level 2
MR21, COM3 02-61
Abstract:
This thesis studies the design of graph algorithms for large-scale applications such as navigation systems, focusing on two central challenges: robustness to failures and fairness in data-driven decisions. The goal is to develop algorithmic techniques that make such systems efficient, resilient, and socially responsible.
In the first part, we investigate fault-tolerant reachability structures. Given a directed graph and a set of important node pairs, the objective is to construct a sparse subgraph that preserves connectivity between those pairs even under multiple failures. We present the first non-trivial constructions that remain resilient to two failures, either edges or vertices. These results significantly improve upon prior work, which was limited to handling a single failure, by achieving substantially smaller subgraph sizes.
In the second part, we study fair clustering. Classical clustering methods often fail to provide proportional representation for different demographic groups, potentially amplifying biases in the data. To address this, we design clustering algorithms that ensure each cluster approximately reflects the overall distribution of protected groups. We introduce a new framework called closest fair clustering and develop the first constant-factor approximation algorithms for fair consensus clustering in the case of two groups. We also show that the problem becomes computationally hard when the groups are of unequal size.
We then generalize this framework to multiple groups and develop efficient near-linear-time approximation algorithms. Building on these techniques, we obtain improved guarantees for fair correlation clustering and provide the first approximation algorithms for weighted and multi-group variants under realistic constraints.
Finally, we address scalability by studying fair consensus clustering in the streaming setting, where inputs arrive sequentially, and memory is limited. We design the first constant-factor approximation algorithm for this model, which processes the stream while storing only a logarithmic number of intermediate clusterings.
Overall, this thesis advances the design of graph algorithms that are both robust and fair. By ensuring reliable connectivity under failures and balanced representation in clustering outcomes, it contributes to building systems that are not only efficient in theory but also trustworthy and inclusive in practice.