Private Edge Density Estimation for Random Graphs: Optimal, Efficient
and Robust
Private Edge Density Estimation for Random Graphs: Optimal, Efficient
and Robust
We give the first polynomial-time, differentially node-private, and robust algorithm for estimating the edge density of Erd\H{o}s-R\'enyi random graphs and their generalization, inhomogeneous random graphs. We further prove information-theoretical lower bounds, showing that the error rate of our algorithm is optimal up to logarithmic factors. Previous algorithms incur either exponential …