Stochastic block models (SBMs) are a very commonly studied network model for
community detection algorithms. In the standard form of an SBM, the $n$
vertices (or nodes) of a graph are generally divided into multiple
pre-determined communities (or clusters). Connections between pairs of vertices
are generated randomly and independently with pre-defined probabilities, which
depend on the communities containing the two nodes. A fundamental problem in
SBMs is the recovery of the community structure, and sharp
information-theoretic bounds are known for recoverability for many versions of
SBMs.
Our focus here is the recoverability problem in SBMs when the network is
private. Under the edge differential privacy model, we derive conditions for
exact recoverability in three different versions of SBMs, namely Asymmetric SBM
(when communities have non-uniform sizes), General Structure SBM (with
outliers), and Censored SBM (with edge features). Our private algorithms have
polynomial running time w.r.t. the input graph's size, and match the recovery
thresholds of the non-private setting when $\epsilon\rightarrow\infty$. In
contrast, the previous best results for recoverability in SBMs only hold for
the symmetric case (equal size communities), and run in quasi-polynomial time,
or in polynomial time with recovery thresholds being tight up to some constants
from the non-private settings.

使用边差分隐私模型，我们针对非对称 SBM（具有非均匀大小的社区）、一般结构 SBM（带有异常值）和被审查 SBM（带有边特征）推导了准确可恢复性的条件。与之前针对 SBM 的对称情况（社区大小相等）的最佳结果相比，我们的私有算法在多项式时间内具有与非私有设置相匹配的恢复阈值。