Algorithms for Private and Dynamic Graphs

Graphs are a fundamental modelling tool in computer science, modelling diverse systems such as social networks, communication infrastructure and maps. We focus on two central challenges. First, due to the ubiquitous use of personal data, it is essential to guarantee the privacy of individuals when extracting useful information from sensitive graphs: one should not be able to infer sensitive data from the output of an algorithm. Second, as the size of the analysed networks grows, maintaining solutions efficiently as the graph is updated also becomes necessary. This thesis contributes to finding solutions to these two challenges.
We study fundamental graph problems in the context of differential privacy. Differential privacy gives formal guarantees about the privacy loss: the output of an algorithm should not enable one to distinguish between two datasets differing by a single entry with certainty; depending on the exact model, one instead bounds the probability of doing so. The main contributions in this domain are:
• Private Graph Colouring with Limited Defectiveness. The defectiveness of a colouring is the maximum number of conflicts that a vertex can have with its neighbours; in other words, a colouring has defectiveness d if there exists a vertex that has d neighbour of the same colour, but no more. We give a lower bound on the necessary defectiveness of an edge differentially private graph colouring: any ϵ-edge differentially private algorithm that returns a c-vertex colouring of a graph of maximum degree Δ > 0 with high probability must have defectiveness at least d ∈ Ω(log n/(ϵ + log c)). We show that this is tight up to lower order terms, unless the number of colours is polynomial in n.
• Differentially Private Vertex Cover. We study vertex cover in the context of edge-differential privacy and give the first algorithm that outputs an explicit partial vertex cover, achieving a constant-factor approximation to the optimal full vertex cover in expectation. We also study a weight-differentially private model, where the network topology is public, but vertex weights are private, and give matching upper and lower bounds on the additive error for constant privacy budget, together with a second algorithm offering improved guarantees when the optimal solution has few vertices.
In the dynamic model, we study how fast one can update a solution upon insertion and deletion of edges. The contribution in this model is the following:
• From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation.We give a practical evaluation of recent approximation algorithms that dynamically maintain a low out-degree orientation, presenting implementations that trade off memory against speed, and show that our approach offers speed-ups of up to 112 times compared to existing methods.
We include an additional paper in Appendix A. The results were presented as the author’s master thesis, and are therefore not original PhD material.
• Sparsity-Parametrised Dynamic Edge Colouring. We give deterministic algorithms for edge colouring that use Δ + O(α) colours and polylogarithmic amortised update time, adapting to the current maximum degree Δ and arboricity α of a graph. This improves the state of the art for sparse graphs in terms of running time, number of colours and by giving deterministic algorithms.