Private Analysis of Graphs
Date: Wednesday, October 02, 2013
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Contact: Ilya Razenshteyn, firstname.lastname@example.org
Relevant URL: http://www.ilyaraz.org/acseminar
Speaker URL: None
TALK: Private Analysis of Graphs
We discuss algorithms for the private analysis of network data. Such algorithms work on data sets that contain sensitive relationship information (for example, romantic ties). Their goal is to compute approximations to global statistics of the graph while protecting information specific to individuals. Our algorithms satisfy a rigorous notion of privacy, called node differential privacy. Intuitively, it means that an algorithm's output distribution does not change significantly when a node and all its adjacent edges are removed from a graph. We present several techniques for designing node differentially private algorithms. We also develop methodology for analyzing the accuracy of such algorithms on realistic networks. Our techniques are based on combinatorial analysis, network flow, and linear and convex programming.
Based on joint work with Shiva Kasiviswanathan, Kobbi Nissim and Adam Smith.
Created by Ilya Razenshteyn at Wednesday, September 25, 2013 at 10:44 PM.