Hehir Jonathan, Slavković Aleksandra, Niu Xiaoyue
Department of Statistics, Penn State University, University Park, PA, USA.
J Priv Confid. 2022 Nov 2;12(2). doi: 10.29012/jpc.811.
The stochastic block model (SBM) and degree-corrected block model (DCBM) are network models often selected as the fundamental setting in which to analyze the theoretical properties of community detection methods. We consider the problem of spectral clustering of SBM and DCBM networks under a local form of edge differential privacy. Using a randomized response privacy mechanism called the edge-flip mechanism, we develop theoretical guarantees for differentially private community detection, demonstrating conditions under which this strong privacy guarantee can be upheld while achieving spectral clustering convergence rates that match the known rates without privacy. We prove the strongest theoretical results are achievable for dense networks (those with node degree linear in the number of nodes), while weak consistency is achievable under mild sparsity (node degree greater than ). We empirically demonstrate our results on a number of network examples.
随机块模型（SBM）和度校正块模型（DCBM）是经常被选作基础框架的网络模型，用于分析社区检测方法的理论特性。我们考虑在局部形式的边差分隐私下，SBM和DCBM网络的谱聚类问题。通过使用一种名为边翻转机制的随机响应隐私机制，我们为差分隐私社区检测建立了理论保障，证明了在实现与无隐私情况下已知速率相匹配的谱聚类收敛速率的同时，能够维持这种强隐私保障的条件。我们证明，对于密集网络（节点度与节点数量成线性关系的网络），可以取得最强的理论结果，而在轻度稀疏（节点度大于 ）的情况下可以实现弱一致性。我们通过多个网络示例对我们的结果进行了实证验证。
