On Learning Cluster Coefficient of Private Networks.

Area of Science:

• Computer Science
• Network Science
• Data Privacy

Background:

• Analyzing social network data while maintaining differential privacy is difficult due to high sensitivity of graph features.
• Traditional privacy methods struggle with complex graph metrics like clustering coefficient and modularity.

Purpose of the Study:

• To develop a novel approach for accurate differential privacy analysis of social network graph statistics.
• To address the challenges posed by high sensitivity of graph features in privacy-preserving data analysis.

Main Methods:

• A divide and conquer strategy is proposed to decompose complex graph computations into simpler unit computations.
• Differential privacy is enforced by perturbing outputs of unit computations with Laplace noise, calibrated using smooth sensitivity for high-sensitivity metrics.
• The approach combines perturbed unit computations to achieve the final differentially private result.

Main Results:

• The divide and conquer approach demonstrates superior performance compared to direct computation methods.
• Empirical evaluations on real and synthetic social networks validate the effectiveness of the proposed method.
• Utilizing smooth sensitivity allows for stricter differential privacy guarantees with reduced noise magnitude.

Conclusions:

• The developed divide and conquer method offers an effective solution for accurate differential privacy in social network analysis.
• This approach enhances the feasibility of analyzing sensitive graph data while preserving individual privacy.
• The findings suggest a promising direction for privacy-preserving graph mining and analysis.