Â鶹´«Ã½AV

Submitted by admin on Wed, 10/23/2024 - 01:52

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.

Mohamed Seif
Yanxi Chen
Andrea J. Goldsmith
H. Vincent Poor