Research map / Federated learning and privacy / Differential privacy
Controlling The Spread of Epidemics on Networks with Differential Privacy
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Designs edge-differentially-private algorithms for choosing vaccinated nodes to reduce maximum degree and spectral radius, by reducing to a private multi-set multi-cover problem solved with an iterative exponential mechanism and AboveThreshold.
Problem
Choosing nodes to remove (vaccinate) from a contact network to reduce maximum degree or spectral radius while guaranteeing edge differential privacy on the private network edges.
Approach
Reformulates private max-degree and spectral-radius reduction as a multi-set multi-cover instance and solves it with an iterative exponential mechanism producing an implicit permutation; an explicit solution is obtained via AboveThreshold/sparse vector, and matching lower bounds are proven for explicit covers.
Key results
- Implicit PrivateMaxDeg solutions on Montgomery subgraphs (target D=45) are within about a factor of 10 of the non-private greedy baseline across epsilon in {0.25,...,4}.
- For epsilon=4 on BTER graphs (D=20), explicit solutions use budget about 66-84 nodes but leave max degree around 93, while implicit solutions use about 430-507 nodes and reach max degree 20.
- Explicit solution cost increases with epsilon in the BTER experiments, because AboveThreshold halts selection earlier at low epsilon.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the explicit rather than implicit solution | PrivateMaxDeg · BTER (γ=0.3, ρ=0.95, η=0.05) | vaccination budget: 506.62 -> 83.89 | Helped |
| Use the explicit rather than implicit solution | PrivateMaxDeg · BTER (γ=0.3, ρ=0.95, η=0.05) | max degree: 20 -> 92.78 | Hurt |
| Use the explicit rather than implicit solution | PrivateMaxDeg · BTER (γ=0.3, ρ=0.95, η=0.05) | spectral radius: 18.35 -> 72.28 | Hurt |
| Use the explicit rather than implicit solution | PrivateMaxDeg · BTER (γ=0.5, ρ=0.95, η=0.05) | vaccination budget: 430.36 -> 66.19 | Helped |
| Use the explicit rather than implicit solution | PrivateMaxDeg · BTER (γ=0.5, ρ=0.95, η=0.05) | max degree: 20 -> 92.80 | Hurt |
| Use the explicit rather than implicit solution | PrivateMaxDeg · BTER (γ=0.5, ρ=0.95, η=0.05) | spectral radius: 18.55 -> 77.99 | Hurt |
| Increase ε | implicit PrivateMaxDeg · Montgomery County subnets | vaccination budget | Helped |
| Increase ε | explicit PrivateMaxDeg · BTER networks | vaccination budget | Hurt |
| Increase ε | explicit PrivateMaxDeg · BTER networks | max degree violation | Helped |
Surprising findings
- Explicit solution cost increases with the privacy budget epsilon, counter to intuition.
- Explicit solutions are much cheaper in vaccination budget but leave maximum degree far above the target.
Limitations
- Implicit solutions are not directly usable as an explicit vaccination set and only give approximate guarantees.
- Explicit solutions cannot satisfy the full covering requirement under DP; lower bounds show additive Omega(log n) error in target degree.
- Approximation factors are O(log n / epsilon) and the spectral radius walk-based bound requires sensitivity Delta^2.
Experimental setup
Datasets: Montgomery County, VA digital twin contact network subgraphs (10,000 nodes) BTER random graphs (1,000 nodes)
Benchmarks: Montgomery County digital twin subgraphs BTER power-law graphs
Metrics: vaccination budget (solution cost) maximum degree spectral radius
Baselines: non-private greedy multi-set multi-cover
Builds on: iterative exponential mechanism sparse vector technique GreedyWalk
Closest papers by meaning
- Learn to Vaccinate: Combining Structure Learning and Effective Vaccination for Epidemic and Outbreak Control (ICML 2025 · similarity 0.87)
- Differentially Private Decentralized Learning with Random Walks (ICML 2024 · similarity 0.83)
- Privacy amplification by random allocation (NeurIPS 2025 · similarity 0.83)
- Differentially Private Worst-group Risk Minimization (ICML 2024 · similarity 0.83)
- Differential Privacy Guarantees of Markov Chain Monte Carlo Algorithms (ICML 2025 · similarity 0.82)
- Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.