Shape: The empirical distribution of a dataset.
Input Dataset: The dataset that differentially private algorithm is performed on to release information. For the task of releasing degree distribution, input dataset's true degree distribution is represented as a histogram.
Output Dataset: The resulting dataset after the differentially private algorithm has been performed on the original dataset. For the task of releasing degree distribution, output dataset's degree distribution is represented as a histogram.
Epsilon: The privacy parameter.
Algorithm: A differentially private algorithm for graphs.
L1 Error: The sum of the absolute difference between the true values and the noisy values.
Degree Distrtibution: The distriubtions of the degrees of the nodes in the graph.
Triangle Counting: A count of the number of triangle (A 3 node cycle) in the graph.
2k-Triangle Counting:A count of the number of 2 overlapping triangles (3 node cycles) in the graph.
3k-Star Counting: A count of the number of stars of size 3 (3 nodes connected to a central node) in the graph.
4k-Clique Counting: A count of cliques of size 4 in a graph. A clique is a set of vertices of a graph, where each pair is joined by an edge and no set containing this set has this property.