Seeding with Differentially Private Network Information

Yuxin Liu, M. Amin Rahimian, Fang-Yi YuSSRN 2025 · DOI

TL;DR

This paper introduces "influence-sample differential privacy" (ISDP), a novel privacy framework for influence maximization in social networks. It addresses the challenge of protecting individual privacy when using partial network data (like contact tracing) for public health interventions, offering a practical solution that balances privacy with utility.

What Problem Does This Paper Address?

Public health interventions, such as distributing HIV prevention medication (PrEP), often rely on "seeding" algorithms to identify key individuals who can amplify the intervention's reach through social networks. However, collecting complete social network data is often infeasible due to privacy concerns, especially in sensitive contexts like sexual behavior. Even partial data, like contact tracing records, can reveal sensitive information about individuals' associations. Existing privacy methods like node or edge differential privacy are too stringent for influence maximization with incomplete data, requiring excessive noise that destroys utility. This paper tackles the challenge of protecting individual privacy in these partial network "influence samples" while still enabling effective influence maximization for interventions.

Methods

The core contribution is the introduction of Influence-Sample Differential Privacy (ISDP). Unlike traditional DP that focuses on network structure, ISDP defines adjacency based on an individual's participation in a specific diffusion event (an "influence sample"). This allows for privacy guarantees even when the underlying network is unknown.

The paper proposes two main algorithmic approaches for ISDP:

  • Central DP with Exponential Mechanism: A trusted curator collects influence samples and uses an exponential mechanism to select seeds. This mechanism probabilistically chooses seeds based on their estimated influence, ensuring privacy by adding controlled noise to the selection process.
  • Local DP with Randomized Response: Individuals themselves randomize their influence sample data before submission using a randomized response mechanism. This enforces privacy at the data collection stage.

Both approaches are analyzed for their sample complexity and their ability to achieve a (1-1/e)OPT approximation guarantee for influence maximization.

Datasets

The paper uses two types of data for evaluation:

  • Synthetic data: Generated from Erdős-Rényi random graphs.
  • Empirically-grounded data: Sexual activity data from the ARTnet study, a cross-sectional egocentric survey of men who have sex with men (MSM) in the US. This data was used to construct dynamic network simulations of sexual partnerships.

Key Insights and Ideas

  • Privacy at the Activity Level: ISDP's focus on individual participation in diffusion events is more practical and relevant for sensitive data like contact tracing than traditional network-level DP.
  • Trade-off between Privacy and Utility: The study rigorously analyzes the trade-off between the privacy budget ($\epsilon$) and the effectiveness of the seeding algorithm. Smaller $\epsilon$ (stronger privacy) requires more samples and can reduce influence spread.
  • Central vs. Local DP: The paper demonstrates that central DP generally requires fewer influence samples than local DP to achieve comparable performance, due to the added noise in local DP.
  • Hardness of Traditional DP: The paper proves that standard node and edge DP are too strict for influence maximization with incomplete data, leading to poor performance guarantees.

Key Results

  • The proposed ISDP algorithms (both central and local) achieve a (1-1/e)OPT - $a \eta$ approximation guarantee for influence maximization, meaning they can find seed sets that are close to optimal, even with privacy constraints.
  • The central DP algorithm using the exponential mechanism requires significantly fewer influence samples (e.g., $O(k \ln n)$) compared to the local DP algorithm using randomized response (e.g., $O(k^3 V_{\rho,k} \ln n / \alpha^2)$) to achieve similar performance.
  • Simulations on MSM sexual activity data show that the exponential mechanism generally outperforms randomized response, especially at lower privacy budgets.
  • Performance degrades gracefully as privacy budgets tighten, with central privacy regimes offering better trade-offs.

Limitations and Future Work

  • Sample Complexity: While the paper provides theoretical bounds, the required number of influence samples can still be substantial, especially for local DP.
  • Temporal Dynamics: The current framework primarily focuses on static influence samples. The authors plan to extend ISDP to temporally evolving data to investigate how sequential data collection affects privacy and intervention effectiveness.
  • Consequentialist Notions of Privacy: Future work may explore new privacy notions that are robust to varying sampling distributions and randomization noise.
  • Post-processing for Local DP: The paper highlights the importance of post-processing in local DP to mitigate bias, and further research could explore alternative post-processing methods for improved bias-variance trade-offs.

Summary updated

BibTeX
@misc{liu2025seeding,
  author = {Yuxin Liu and M. Amin Rahimian and Fang-Yi Yu},
  title = {{Seeding with Differentially Private Network Information}},
  year = {2025},
  doi = {10.2139/ssrn.5807384},
  howpublished = {SSRN},
}
Figure