Differentially Private Analysis of Graphs and Social Networks

Many types of data can be represented as graphs, where nodes correspond to individuals and edges capture relationships between them. It turns out that the graph structure can be used to infer sensitive information about individuals, such as romantic ties. This talk will discuss the challenge of performing and releasing analyses of graph data while protecting personal information. It will present algorithms that satisfy a rigorous notion of privacy, called differential privacy, and compute accurate approximations to network statistics, such as subgraph counts and the degree sequence.