Applications of Differential Privacy in Social Network Analysis: A Survey

Honglu Jiang, Jian Pei, Dongxiao Yu, Jiguo Yu, Bei Gong, Xiuzhen Cheng

TL;DR

This survey provides a comprehensive overview of how differential privacy, a robust privacy-preserving technique, can be applied to social network analysis. It bridges the gap between differential privacy fundamentals and its practical application in social networks, highlighting challenges and future research directions in this rapidly evolving field.

What Problem Does This Paper Address?

Social networks are rich sources of sensitive personal information, making privacy a critical concern. While differential privacy offers strong guarantees, its application to complex, interconnected social network data presents unique challenges. Traditional differential privacy methods, developed for tabular data, struggle with the inherent correlations and scale of social networks. This paper addresses the need for a unified understanding of how to adapt differential privacy to social network analysis, covering privacy attacks, different privacy models, and common analytical tasks.

Methods

The paper surveys existing research on applying differential privacy to social network analysis. It covers:

  • Foundations of Differential Privacy: Explains the core concepts, including the definition of differential privacy (both $\epsilon$-differential privacy and approximate $(\epsilon, \delta)$-differential privacy), noise calibration mechanisms (global sensitivity, smooth sensitivity), and composition properties (sequential and parallel).
  • Variations of Differential Privacy: Discusses dependent differential privacy (for correlated data) and local differential privacy (where users handle their own privacy).
  • Privacy Attacks in Social Networks: Categorizes and explains common attacks like identity disclosure, attribute disclosure, link disclosure, and graph metrics disclosure.
  • Types of Differential Privacy for Social Networks: Adapts differential privacy to social networks by defining node privacy, edge privacy, out-link privacy, and partition privacy.
  • Applications in Social Network Analysis: Reviews differentially private algorithms for common tasks like degree distribution, subgraph counting (triangles, k-stars, k-cliques), and edge weight analysis.

Datasets

Not explicitly discussed in the paper, but the Stanford Network Analysis Platform (SNAP) is mentioned as a repository for social network data used in research.

Key Insights and Ideas

  • Social Networks are Fundamentally Different: The inherent correlations and scale of social networks pose significant challenges for standard differential privacy techniques designed for tabular data.
  • Privacy Models Need Adaptation: Simply applying tabular differential privacy to social networks is insufficient. New models like node, edge, out-link, and partition privacy are necessary to capture the nuances of network data.
  • Trade-offs are Crucial: Achieving differential privacy in social networks often involves a delicate balance between privacy guarantees and data utility. High privacy often means significant noise, which can distort analytical results.
  • Complexity is a Major Hurdle: Many social network analysis tasks (e.g., subgraph counting) are computationally complex, and applying differential privacy to them can exacerbate this, sometimes leading to NP-hard problems.
  • Local Differential Privacy Offers a Decentralized Approach: For scenarios where a trusted third-party data collector is unavailable, local differential privacy shifts the privacy burden to individual users, offering a promising alternative.

Key Results

The paper is a survey, so it doesn't present new experimental results. Instead, it synthesizes findings from existing research. Key takeaways include:

  • Node privacy is often infeasible for high utility: Due to high sensitivity, node privacy typically requires substantial noise, leading to poor data utility for many social network analysis tasks.
  • Edge privacy offers a better balance: Protecting individual edges is more practical and widely used, offering meaningful privacy protection for relationships.
  • Out-link privacy is a weaker but more efficient alternative: It can simplify sensitivity calculations and reduce noise for certain queries compared to node and edge privacy.
  • Subgraph counting is particularly challenging: These queries often have high sensitivities, requiring significant noise and complex algorithms, sometimes leading to NP-hard problems.
  • Existing differentially private algorithms struggle with large-scale and complex graphs: Achieving both good utility and strong privacy simultaneously remains a significant challenge.

Limitations and Future Work

The authors identify several open research problems:

  • Differential Privacy for Complex and Correlated Social Network Data: Effectively applying differential privacy to complex network structures and highly correlated data remains a grand challenge. This includes developing techniques to handle dependencies between nodes and attributes.
  • Trade-off between Privacy Budget and Data Utility: Quantifying and optimizing this trade-off, especially in practical scenarios, is still not well understood. There's a lack of clear consensus on how to choose the privacy budget ($\epsilon$).
  • Differentially Private Publishing of High-Dimensional Social Network Data: Effectively publishing high-dimensional social network data while preserving privacy and utility is difficult due to varying sensitivities of dimensions, complex correlations, and the "Curse of Dimensionality."
  • Differentially Private Publishing of Dynamic Data: Extending differential privacy to dynamic social network data, where data is continuously updated, presents challenges in budget allocation, noise accumulation, and maintaining utility over time.

Summary updated

Abstract

Differential privacy provides strong privacy preservation guarantee in information sharing. As social network analysis has been enjoying many applications, it opens a new arena for applications of differential privacy. This article presents a comprehensive survey connecting the basic principles of differential privacy and applications in social network analysis. We concisely review the foundations of differential privacy and the major variants. Then, we discuss how differential privacy is applied to social network analysis, including privacy attacks in social networks, models of differential privacy in social network analysis, and a series of popular tasks, such as analyzing degree distribution, counting subgraphs and assigning weights to edges. We also discuss a series of challenges for future work.
BibTeX
@article{jiang2023applications,
  author = {Honglu Jiang and Jian Pei and Dongxiao Yu and Jiguo Yu and Bei Gong and Xiuzhen Cheng},
  title = {{Applications of Differential Privacy in Social Network Analysis: A Survey}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2023},
  url = {https://openreview.net/forum?id=0On7vJLdSyF},
}
Figure