Differentially Private Analysis of Graphs - Sofya Raskhodnikova

From Katie Gentilello November 14th, 2016

19 plays 0 comments

Many types of data can be represented as graphs, where nodes correspond to individuals and edges capture relationships between them. Examples include datasets capturing “friendships” in an online social network, financial transactions, email communication, doctor-patient relationships, and romantic ties. On one hand, such datasets contain sensitive information about individuals. On the other hand, global information that can be gleaned from their analysis can provide significant benefits to society. Several naive attempts at anonymizing sensitive data by stripping obvious identifying information resulted in spectacular failures. In this talk, we discuss algorithms for analyzing network data that satisfy a rigourous notion of privacy called node differential privacy. We present several techniques for designing node differentially private algorithms, based on combinatorial analysis, network flow, and linear and convex programming.

Based on joint work with A. Smith (FOCS 2016) and with S. Kasiwisvanathan, K. Nissim, A. Smith (TCC 2013)

https://mediaspace.gatech.edu/media/raskhodnikova/1_b79ghzzr

Tags: arc colloquiumalgorithms and randomness centergeorgia techrecorded by gtlibraryfall 2016

name: Sofya Raskhodnikova
Date: November 7th, 2016
Appears In: Open Scholarship

Comments
Related Media

Loading…

Differentially Private Analysis of Graphs - Sofya Raskhodnikova

Related Media