Implementation and Evaluation of Algorithms for Releasing Graph Statistics Under Node Differential Privacy
Open Access
Author:
Lu, Edward
Area of Honors:
Computer Science
Degree:
Bachelor of Science
Document Type:
Thesis
Thesis Supervisors:
Sofya Raskhodnikova, Thesis Supervisor Dr. John Joseph Hannan, Thesis Honors Advisor
Keywords:
Computer Science Privacy
Abstract:
We implement and experimentally evaluate algorithms described by Kasiviswanathan~\etal~\cite{KNRS13}. These alg orithms satisfy node differential privacy. Roughly, if an algorithm ensuring node differential privacy outputs the approximate value of a statistic, the approximation does not change significantly if a single node and any adjacent edges are added or removed from a graph.
We study algorithms releasing simple statistics: edges, triangles, and $k$-stars. These algorithms make use of three different ``projection'' operators. The easiest and most sensitive operator is the naive truncation operator, which simply removes all nodes above a certain degree threshold. The other operators are based on reductions; thes e operators must be tailored for use for specific statistics, but add comparatively little noise while still guaran teeing node differential privacy.
These algorithms are run on large, real-world datasets from the Stanford Large Dataset Network Collection \cite {SLNDC}. We plot the median relative error of our results, and compare the algorithms to the only other known imple mentation of node differential privacy \cite{ChenZ13}. While the error is comparable to that produced by their algo rithm, the running time of our algorithm is superior.
