  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 $\sqrt{n}$). We empirically demonstrate our
results on a number of network examples.
