CONSISTENT SPECTRAL CLUSTERING OF NETWORK BLOCK MODELS UNDER LOCAL DIFFERENTIAL PRIVACY

Area of Science:

• Network Science
• Computer Science
• Data Privacy

Background:

• Stochastic block models (SBM) and degree-corrected block models (DCBM) are foundational for analyzing community detection algorithms.
• Spectral clustering is a common technique for identifying communities in networks.
• Ensuring data privacy in network analysis is crucial, especially with sensitive information.

Purpose of the Study:

• To develop theoretical guarantees for differentially private spectral clustering on SBM and DCBM networks.
• To investigate the impact of edge differential privacy on community detection performance.
• To establish conditions for maintaining strong privacy while achieving accurate community detection.

Main Methods:

• Utilized the edge-flip mechanism, a randomized response technique, to ensure local edge differential privacy.
• Applied spectral clustering to SBM and DCBM networks under the edge-flip privacy model.
• Derived theoretical convergence rates for the private spectral clustering algorithm.

Main Results:

• Achieved theoretical guarantees for differentially private community detection using the edge-flip mechanism.
• Demonstrated that spectral clustering convergence rates matching non-private methods are possible under strong privacy.
• Identified conditions for dense networks where optimal rates are maintained, and weak consistency under mild sparsity.

Conclusions:

• The edge-flip mechanism enables effective differentially private community detection in SBM and DCBM networks.
• Strong privacy guarantees can be upheld without sacrificing the theoretical performance of spectral clustering, particularly in dense networks.
• The findings provide a robust framework for privacy-preserving network analysis.