Abstract
We study the community detection problem over binary symmetric stochastic block models (SBMs) while preserving the privacy of the individual connections between the vertices. We present and analyze the associated information-theoretic tradeoff for differentially private exact recovery of the underlying communities by deriving sufficient separation conditions between the intra-community and inter-community connection probabilities while taking into account the privacy budget and graph sketching as a speed-up technique to improve the computational complexity of maximum likelihood (ML) based recovery algorithms.
Original language | English (US) |
---|---|
Pages (from-to) | 331-346 |
Number of pages | 16 |
Journal | IEEE Journal on Selected Areas in Information Theory |
Volume | 5 |
DOIs | |
State | Published - 2024 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Computer Networks and Communications
- Media Technology
- Artificial Intelligence
- Applied Mathematics
Keywords
- Differential privacy
- community detection
- graph sketching
- graphs
- subsampling