# Detecting Communities under Differential Privacy

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jul 2016.

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

- [Differentially Private Community Detection for Stochastic Block Models](https://mlsanity.com/paper/2202.00636/) (2022)
- [LPGNet: Link Private Graph Networks for Node Classification](https://mlsanity.com/paper/2205.03105/) (2022)
- [Differentially Private Densest Subgraph Detection](https://mlsanity.com/paper/2105.13287/) (2021)
- [Differentially private exact recovery for stochastic block models](https://mlsanity.com/paper/2406.02644/) (2024)
- [Privacy-Preserving Community Detection for Locally Distributed Multiple Networks](https://mlsanity.com/paper/2306.15709/) (2023)
- [On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Models](https://mlsanity.com/paper/2505.05816/) (2025)
- [How Private is Your Attention? Bridging Privacy with In-Context Learning](https://mlsanity.com/paper/2504.16000/) (2025)
- [Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency](https://mlsanity.com/paper/2510.07136/) (2025)
- [Privacy utility trade offs for parameter estimation in degree heterogeneous higher order networks](https://mlsanity.com/paper/2602.03948/) (2026)
- [Differentially Private Modeling of Disease Transmission within Human Contact Networks](https://mlsanity.com/paper/2604.07493/) (2026)

## Abstract (arXiv)

Complex networks usually expose community structure with groups of nodes sharing many links with the other nodes in the same group and relatively few with the nodes of the rest. This feature captures valuable information about the organization and even the evolution of the network. Over the last decade, a great number of algorithms for community detection have been proposed to deal with the increasingly complex networks. However, the problem of doing this in a private manner is rarely considered. In this paper, we solve this problem under differential privacy, a prominent privacy concept for releasing private data. We analyze the major challenges behind the problem and propose several schemes to tackle them from two perspectives: input perturbation and algorithm perturbation. We choose Louvain method as the back-end community detection for input perturbation schemes and propose the method LouvainDP which runs Louvain algorithm on a noisy super-graph. For algorithm perturbation, we design ModDivisive using exponential mechanism with the modularity as the score. We have thoroughly evaluated our techniques on real graphs of different sizes and verified their outperformance over the state-of-the-art.