ε-Differential node privacy in graph data queries
Christine Task, Chris Clifton · Annual Information Security Symposium · 2011
Epsilon differential privacy is a context-independent guarantee of individual privacy in data query results, defined by Cynthia Dwork of Microsoft Research. Given two data-sets which differ only on one (arbitrarily chosen) individual, a differentially private query will return an answer S with nearly the same probability on both sets. Thus given some query result S, we're unable to determine which data set the query ran on, obfuscating the contributions of any individual. Creating differentially private graph queries is especially challenging. If a graph's nodes represent individuals, and its edges represent relationships, the removal of an individual from a data set can have catastrophic effect on the result of the query. We explore which queries are impossible to privatize, which are feasible, and which are feasible under certain constraints.