cs.DS cs.LG
Efficiently Estimating Erdos Renyi Graphs with Node Differential Privacy. We give a simple, computationally efficient, and node differentially private algorithm for estimating the parameter of an Erdos Renyi graph that is, estimating p in a G(n,p) with near optimal accuracy. Our algorithm nearly matches the information theoretically optimal exponential time algorithm for the same problem due to Borgs et al. (FOCS 2018). More generally, we give an optimal, computationally efficient, private algorithm for estimating the edge density of any graph whose degree distribution is concentrated on a small interval.