Private community detection in the weighted stochastic block model

Community structure in sensitive weighted networks is often used for security and privacy applications, but releasing such analyses can leak information about individual weighted links. We study when communities in these graphs can be recovered while guaranteeing edge-level (ε,δ)-differential privacy (DP) for every edge. We provide a systematic information-theoretic study of differentially private community recovery in weighted stochastic block models. Working with the weighted stochastic block model (WSBM), we derive sufficient conditions that describe when exact community recovery is information-theoretically possible with edge-level privacy constraints and a necessary condition for the two-community case (S=2). These conditions make explicit how the privacy budget and the separation between within- and across-community weight distributions trade off. We also provide a practical estimator based on a stability-based mechanism for weighted community detection under (ε,δ)-DP, and experiments on synthetic WSBM graphs confirm the predicted privacy–recovery trade-offs.