# Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy

arXiv: https://arxiv.org/abs/1905.10477 · HTML: https://mlsanity.com/paper/1905.10477/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2019.

## Built on by (most cited first, 13 of 13)

- [Private estimation algorithms for stochastic block models and mixture models](https://mlsanity.com/paper/2301.04822/) (2023)
- [Differentially Private Community Detection for Stochastic Block Models](https://mlsanity.com/paper/2202.00636/) (2022)
- [SoK: Differential Privacy on Graph-Structured Data](https://mlsanity.com/paper/2203.09205/) (2022)
- [Privacy-Preserving Graph Machine Learning from Data to Computation: A Survey](https://mlsanity.com/paper/2307.04338/) (2023)
- [Robust Estimation for Random Graphs](https://mlsanity.com/paper/2111.05320/) (2021)
- [Near-Optimal Correlation Clustering with Privacy](https://mlsanity.com/paper/2203.01440/) (2022)
- [Sharper Utility Bounds for Differentially Private Models](https://mlsanity.com/paper/2204.10536/) (2022)
- [Private graphon estimation via sum-of-squares](https://mlsanity.com/paper/2403.12213/) (2024)
- [Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust](https://mlsanity.com/paper/2405.16663/) (2024)
- [On Differentially Private U Statistics](https://mlsanity.com/paper/2407.04945/) (2024)
- [It's My Data Too: Private ML for Datasets with Multi-User Training Examples](https://mlsanity.com/paper/2503.03622/) (2025)
- [On the Price of Differential Privacy for Hierarchical Clustering](https://mlsanity.com/paper/2504.15580/) (2025)
- [Differentially Private Modeling of Disease Transmission within Human Contact Networks](https://mlsanity.com/paper/2604.07493/) (2026)

## Abstract (arXiv)

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.