Differentially private analysis of graphs[1] studies algorithms for computing accurate graph statistics while preserving differential privacy.
For examples, edges could correspond to friendships, sexual relationships, or communication patterns.
Differential privacy imposes a restriction on the algorithm.
Intuitively, it requires that the algorithm has roughly the same output distribution on neighboring inputs.
be a randomized algorithm that takes a graph as input and returns an output from a set
-edge-differentially private if, in the definition above, the notion of edge neighbors is used.
-node-differentially private if, in the definition above, the notion of node neighbors is used.
Intuitively, a node differentially private algorithm has similar output distributions on any pair of graphs that differ in one one nodes and edges adjacent to it, thus protecting information pertaining to each individual.
The first edge differentially private algorithm was designed by Nissim, Raskhodnikova, and Smith.
[2] The distinction between edge and node differential privacy was first discussed by Hay, Miklau, and Jensen.
[3] However, it took several years before first node differentially private algorithms were published in Blocki et al.,[4] Kasiviswanathan et al.,[5] and Chen and Zhou.
Raskhodnikova and Smith gave the first node differentially private algorithm for releasing a vector, specifically, the degree count and the degree distribution.