the number of s-stars of an input graph $G=(V,E)$ is $\sum\limits_{v\in V}\binom{d(v)}{S}$
when $d(v)$ is the degree of the node $v$. In this problem, we address the publication of the number of $s$-stars under $k$-edge differential privacy (defined in the final slide of Lecture 4).
Question 2.1: Let us suppose that the degrees of all nodes are public information. Give a $k$-edge $E$-differentially private algorithm to publish the number of $s$-stars.
Question 2.2: Let us suppose that the degrees are sensitive information, but the maximum degree is public. Give a $k$-edge $e$-differentially private algorithm to publish the number of $s$-stars based on the Laplacian mechanism.
Question 2.3: Calculate the variance of your mechanism in Question 2.2.
Question 2.4: Let us suppose that the degrees are sensitive information, but the maximum degree is public. Give a local $k$-edge $e$-differentially private algorithm to publish the number of $s$-stars based on the Laplacian mechanism.
Question 2.5: Calculate the variance of your mechanism in Question 2.4.
Hint: Let $X_1,\cdots,X_n$ be an independent random variable. We have that $\mathrm{Var}(X_1+\cdots+X_n) = \mathrm{Var}(X_1)+\cdots+\mathrm{Var}(X_n)$.
Question 2.6: Compare the results that you have from Question 2.3 and 2.5. Which one is better in your opinion?