We investigate techniques for analyzing the structure of social network datasets while preserving the privacy of individuals’ information. The techniques we consider satisfy node-differential privacy, which is a notion quantifying ”privacy” for graph-like datasets. More specifically, we implement and evaluate methods proposed in various literature for selecting an optimal threshold parameter for these algorithms to maintain privacy while still providing useful information about the graph.
We concentrate on two statistics for the purposes of this paper: the number of edges in a graph and the number of triangles. Using algorithms that compute the values of a statistic for varying truncation parameters, we analyze their results to determine a near-optimal threshold value of the statistic to release. We evaluate two methods for this threshold selection, one due to Kasiviswanathan et. al. and another due to Raskhodnikova and Smith. We find that, in most cases, the second method performs better than first.
