Abstract
We discuss differentially private algorithms for analysis of network data. Such algorithms work on data sets that contain sensitive relationship information (for example, romantic ties). There are two natural variants of differential privacy for graphs: edge differential privacy and node differential privacy. We will survey results for both notions and then focus on the stronger of the two—node differential privacy. We present several techniques for designing node differentially private algorithms, based on combinatorial analysis, network flow, and linear and convex programming. We also discuss the accuracy of such algorithms on realistic networks, showing theoretical and empirical results.