Pith. sign in

REVIEW 3 major objections 5 minor 51 references

Controlling the Spread of Epidemics on Networks with Differential Privacy

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper gives the first edge-differentially-private algorithms for choosing which nodes to vaccinate so that the residual contact network's maximum degree or spectral radius falls below a target, with vaccination cost within an…

desk verdict Interesting first attempt at edge-DP epidemic control, but the advertised Ω(log n) lower bound is unproved and the explicit solution algorithm contradicts its own threshold rule. read the letter →

arxiv 2506.00745 v1 pith:JFWIZIRV submitted 2025-05-31 cs.DS cs.CEcs.SI

Dung Nguyen , Aravind Srinivasan , Renata Valieva , Anil Vullikanti , Jiayi Wu This is my paper
classification cs.DScs.CEcs.SI
keywords differentialprivacyedgemulti-setmulti-covermaximumdegreereductionspectralradiusvaccinationstrategynetworkepidemiologyexponentialmechanism
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Controlling an outbreak by vaccination means removing a small set of nodes from a contact network, and the most effective proxy targets are the network's maximum degree and spectral radius. This paper asks how to choose that set when the edges themselves are sensitive and must be protected with differential privacy, a guarantee that changing any single contact only slightly changes the output distribution. It establishes that both targets admit edge-differentially-private algorithms: the private solution costs at most $O((1+1/\varepsilon')\log n)$ times the optimal non-private set, with high probability, and explicit lists of vaccinated nodes are possible at the price of $O(\log n/\varepsilon')$ slack in the degree target. It also claims lower bounds showing that any explicit private solution must incur $\Omega(\log n)$ additive error, so some residual degree overshoot is unavoidable. The reason a reader should care is that, if these results hold, privacy does not force giving up on principled epidemic planning: a near-optimal vaccination strategy can be released without revealing who is connected to whom.

What carries the argument

The central object is a reduction to multi-set multi-cover: each vertex $v$ becomes a set containing $\infty$ copies of itself and one copy of each neighbor, and the requirement $r_v$ is how far $v$'s degree exceeds the target $D$. The private routine, borrowed from the iterative exponential-mechanism approach, repeatedly samples a remaining set with probability exponential in its marginal remaining coverage, producing a permutation that implicitly encodes the cover. A second mechanism, AboveThreshold, is used as a noisy stopping rule to convert that permutation into an explicit list of nodes to remove, at the cost of $O(\log n/\varepsilon')$ slack in the final degree target.

What would settle it

Check the lower-bound construction in Theorem C.7: in an instance requiring $r_0$ copies of the only element, the set $S_1$ is built with only $r_0 - \beta - \alpha\log n$ copies, so it leaves $\alpha\log n$ copies uncovered and is not an optimal singleton cover for the nearby instance requiring $r_0 - \beta$ copies. Verifying whether every set in $\mathcal{S}^*$ covers at most $r_0 - \beta - 1$ copies, the inequality the group-privacy argument needs, will confirm or refute the claimed $\Omega(\log n)$ lower bound for explicit covers.

Watch

Extended reading notes

Core claim

The central discovery is that the two epidemic-control optimization problems, PRIVATEMAXDEG and PRIVMINSR, can be solved under edge differential privacy by reducing them to a multi-set multi-cover problem and privatizing the cover routine. For maximum degree, the paper proves that its Algorithm 1 outputs an implicit cover whose size is at most $O((1+1/\varepsilon')\ln|V|)$ times the optimal non-private cover with high probability, and that Algorithm 2 makes that cover explicit with a degree violation of $D + O(\log n/\varepsilon')$. For spectral radius, it gives two routes: privatizing a greedy walk-removal algorithm yields a bound around $n^{1/4}\Delta^{1/2}$ on the residual spectral radius, and a second reduction based on the degree-of-neighbors bound $\rho(G) \leq \max_u \sqrt{\sum_{v\sim u} d(v,G)}$ brings the same multi-set machinery to bear at a $4\Delta$ privacy-sensitivity price. The paper further claims that implicit solutions fully satisfy coverage constraints while explicit solutions cannot, and states lower bounds that any explicit private solution with near-optimal size must leave $\Omega(\log n)$ additive slack in the degree target.

Load-bearing premise

The load-bearing assumption is that the repeated sampling mechanism that is private for ordinary set cover stays private and near-optimal when neighboring problem instances may differ in several coverage counts or multiplicities at once (up to four changes, or up to $4\Delta$ in the spectral-radius variant); the paper relies on this transfer instead of fully proving it.

Editorial extensions

If this is right

  • If the degree-reduction guarantee is correct, a public-health authority can publish a vaccination list under edge differential privacy and still achieve maximum degree below $D + O(\log n/\varepsilon')$, at a vaccination cost within $O((1+1/\varepsilon')\log n)$ of the optimal non-private plan.
  • The spectral-radius algorithms give the first private analogues of structural epidemic control: one reduces length-four walks to force $\rho(G) \leq O(n^{1/4}\Delta^{1/2})$, which beats the trivial $\Delta$ bound on dense graphs.
  • The lower bounds, if they survive scrutiny, imply a hard trade-off: an explicit private vaccine list cannot both use near-optimal size and meet the coverage target exactly, so some violation of the target degree is unavoidable.
  • Implicit solutions retain full coverage and better metric reduction, but they require each node to infer its own membership from the private permutation, which is not a directly publishable vaccine list.
  • Experiments on contact-network and synthetic graphs show the private implicit solution's cost within a roughly constant factor (about 10) of a non-private greedy cover on tested instances, and explicit solutions' cost and violation trade off with $\varepsilon$, so privacy budgets need careful selection.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper, if the $\Omega(\log n)$ lower bound can be rigorously established, the practical design question shifts from eliminating overshoot to calibrating it: choose $\varepsilon$ and $D$ so that $D + O(\log n/\varepsilon')$ sits below the epidemic threshold.
  • The multi-set multi-cover reduction is generic enough to cover other threshold-based node-removal objectives, such as reducing $k$-core numbers or bounding local clustering, suggesting a template for private structural interventions beyond degree and spectral radius.
  • A testable extension is to use the implicit permutation directly as a priority ranking for vaccine allocation rather than converting it to an explicit set; in the paper's own experiments this preserves more of the degree reduction and may be the more privacy-favorable output.
  • Because the spectral-radius route pays a $4\Delta$ sensitivity penalty, it is likely to be most useful on degree-assortative or bounded-degree networks; on heavy-tailed contact networks, a future algorithm that privatizes a lower-sensitivity spectral bound would be needed.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper initiates the study of edge-differentially private algorithms for choosing vaccination sets that reduce the maximum degree (PRIVMAXDEG) or the spectral radius (PRIVMINSR) of a contact network. The approach reduces these problems to a private multi-set multi-cover problem, provides an implicit-solution algorithm based on the iterative exponential mechanism of Gupta et al. [19], and an explicit-solution variant using the AboveThreshold mechanism. The paper also claims lower bounds showing that any explicit private solution must incur an additive error of Ω(log n) in the coverage requirement, and it reports experiments on synthetic and real-world networks. The main theorem (Theorem 4.2) claims an O((1 + 1/ε') ln|V|)-approximation with high probability for PRIVMAXDEG; Theorem C.7 claims the Ω(log n) lower bound for explicit solutions, and Lemma 4.5 transfers it to PRIVMAXDEG.

Significance. If the results were fully established, they would provide the first edge-differentially private algorithms for two epidemic-control optimization problems that have so far only been studied without privacy, and the explicit-solution lower bound would delineate a fundamental privacy–utility tradeoff. The reduction to multi-set multi-cover and the use of sparse-vector techniques for explicit solutions are natural and potentially useful. However, the lower-bound proof in Appendix C.3 contains a false premise about the constructed instance, and the explicit-solution analysis in Section 4.2 is inconsistent with the stated algorithm. These issues affect headline claims, so the significance is conditional on repair.

major comments (3)
  1. [Appendix C.3, Theorem C.7] The lower-bound construction is not valid as written. In instance I2 the coverage requirement is r_e = r0 − β, but the set S1 is defined with only r0 − β − α log n copies of e, so S1 alone does not cover I2. Therefore the claim 'S1 is the optimal solution, |OPT| = 1' is false for I2; the optimal cover must include additional copies beyond S1. Furthermore, the definition of S* is impossible for the stated set system: S contains exactly two sets, S1 and {e}×(β+α log n), so a subcollection S ⊂ S can contain at most one copy of the second set; the description 'contains S1 and up to α−1 copies of {e}' does not correspond to subsets of S. If α log n ≥ 2, then the valid subcollection {S1, S2} lies in S* and fully covers I2, contradicting the claim that every S ∈ S* covers at most r0−β−1 copies. Consequently the probability separation Pr[M(I1)∈S*] ≤ C and Pr[M(I2)∈S*] ≥ 1−C is not established, and the Ω(log n) lower bound of Theorem C.7 is unproved. Since Lemma 4.5 in Section 4.2 explicitly inherits this lower bound, the paper's third main contribution is not supported.
  2. [Section 4.2, Algorithm 2 and Theorem 4.3] The explicit-solution algorithm and its analysis are inconsistent. Algorithm 2 lines 2–6 define T′ ← 6 ln n/ε′ − Lap(2/ε1), γ_i ← L_i − Lap(4/ε1), and stop at the first k with γ_k ≤ T′. This is the opposite of the standard AboveThreshold rule in Definition B.5, which returns the first index whose noisy query exceeds the noisy threshold. The quantity L_i used in line 4 is never defined in the pseudocode; it first appears in the proof of Theorem 4.3 as the maximum utility after removing the first i nodes, but the algorithm does not state this. In the proof, the sentence 'for i ≥ k̂, L_i ≤ 6 ln n/ε′ but γ_i ≥ T′' is also inconsistent with the stopping condition γ_k ≤ T′, and the subsequent argument that the Laplace noises are 'greater' relies on an unspecified comparison. As written, the proof does not establish the claimed bound Δ(G − ∪_{i=1}^k{π_i}) ≤ D + O(log n/ε′) or the bound k = O(OPT · log n/ε′).
  3. [Appendix C.1.1, Lemma C.1 and Lemma 4.1] The utility proof for the implicit multi-set multi-cover algorithm contains a load-bearing step that is only asserted. The proof states that 'the greedy approximation is a O(ln q) approximation' and therefore the exponential-mechanism process covers the high-utility region with O(OPT ln q) sets, but no proof or precise reference is given for this multi-set multi-cover greedy bound. The standard set-cover greedy analysis does not directly apply to the multi-set multi-cover setting with element multiplicities and residual requirements used here. Since Lemma C.1 is the basis for Theorem 4.2, the main upper bound for PRIVMAXDEG, the O(ln q) approximation claim needs a complete argument or an exact citation that covers this formulation.
minor comments (5)
  1. [Section 4.2, Algorithm 2] The variable L_i should be defined in the pseudocode; currently it is used in line 4 but only explained later in the proof of Theorem 4.3.
  2. [Definition 3.2] There is a typographical error in the displayed definition of OP T_MAXDEG: the condition contains 'S ⊆ V, ,∆(G[V \ S]) ≤ D' with an extra comma before the maximum-degree condition.
  3. [Appendix A] The phrase 'egde-differential privacy' should be 'edge-differential privacy'.
  4. [Section 5.1, Lemma 5.1] The privacy parameters in Lemma 5.1 are stated as (Δ²(ε+ε₁), Δ²δe^{(Δ²−1)ε}), but Algorithm 3 sets ε′ = ε/(2 ln(e/δ)) for the set-cover phase, so the composition of the Δ²-fold group privacy with the AboveThreshold step would naturally involve ε′ rather than ε; the statement should be reconciled with the algorithm's parameter choices.
  5. [Section 6, Experiments] The experimental section notes for the explicit-solution experiments that the privacy guarantee was relaxed to the multi-set multi-cover definition rather than the edge-DP definition; this should be stated more prominently, since it weakens the empirical evidence for the edge-DP claims of Section 4.2.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: the main reductions and privacy proofs are self-contained or rely on external prior work; the lower-bound defect is a correctness issue, not circularity.

full rationale

The paper's central utility transfers do not reduce to their own inputs. Algorithm 4 is an adaptation of the iterative exponential mechanism of [19], with a proof skeleton given in Appendix C.1; Algorithm 1 is a genuine reduction of PRIVATEMAXDEG to PRIVATEMULSET, and its approximation bound follows from Lemma 4.1 rather than from assuming the conclusion. The explicit solution (Algorithm 2) uses the standard AboveThreshold accuracy guarantee. The spectral-radius algorithms either use the external spectral bound [17] and the greedy approximation of [44], or transfer PRIVATEMULSET with an adjusted sensitivity of 4Delta; none of these steps sets a parameter to equal the output by construction. There are author-overlapping citations: [30] (Li, Nguyen, Vullikanti) for a differentially private partial set cover algorithm and [44] (Saha, Adiga, Prakash, Vullikanti) for greedy spectral-radius reduction. These are prior published algorithms invoked as lemmas, not self-referential definitions, and the present target results are not contained in those citations; hence they are at most minor self-citations and do not make the derivation circular. The lower-bound proof in Theorem C.7 contains a serious flaw as written: the set S1 defined with r0 - beta - alpha log n copies is not a feasible cover of instance I2 with requirement r0 - beta, so the claim that S1 is the optimal solution is false, and the subcollection S* is ill-defined. This undermines the advertised Omega(log n) lower bound, but it is a correctness defect rather than a circularity. Overall, no prediction or first-principles result reduces by definition to a fitted input or to a self-citation chain, so the circularity score is low; the two points reflect the presence of author-overlapping citations in the derivation chain rather than any detected circular step.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

There are no fitted constants, but the paper relies on standard DP composition, on a domain assumption that network-proxy reduction controls spread, and on asserting that the prior private set-cover algorithm transfers to multi-set multi-cover with a 4-step neighbor relation. The lower-bound construction in Appendix C.3 is internally inconsistent.

assumptions (4)
  • standard math Standard differential privacy composition and the exponential, Laplace, and AboveThreshold mechanisms satisfy their usual guarantees.
    Used throughout Sections B and C to argue privacy guarantees; standard but unverified in the paper.
  • domain assumption Reducing maximum degree or spectral radius of the contact network is an effective proxy for reducing SIR/SIS epidemic spread.
    Invoked in Section 3.1 to justify the proxy objectives; not validated by new simulations in this paper for the privacy setting.
  • ad hoc to paper The iterative exponential mechanism of [19] remains (epsilon,delta)-differentially private for multi-set multi-cover under the paper's 4-step neighboring relation, and for the spectral version under a 4Delta-step relation.
    The paper asserts this transfer in Sections 4.1, 4.2 and Appendix D.2, but the proof is dense and does not fully address all combinations of 4-step neighbor changes.
  • standard math The greedy walk-removal algorithm of [44] and the inequality W4(G) <= nT^4 imply rho(G) <= O(n^{1/4}T).
    Used in Section 5.1 to convert walk reduction into spectral radius bound; cited from [44] but not rederived.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Controlling the Spread of Epidemics on Networks with Differential Privacy." pith.science (2026). https://pith.science/paper/JFWIZIRV

@misc{pith2026250600745,
  author       = {Pith},
  title        = {Pith review of: Controlling the Spread of Epidemics on Networks with Differential Privacy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JFWIZIRV}},
  note         = {Machine review of arXiv:2506.00745}
}
abstract

Designing effective strategies for controlling epidemic spread by vaccination is an important question in epidemiology, especially in the early stages when vaccines are limited. This is a challenging question when the contact network is very heterogeneous, and strategies based on controlling network properties, such as the degree and spectral radius, have been shown to be effective. Implementation of such strategies requires detailed information on the contact structure, which might be sensitive in many applications. Our focus here is on choosing effective vaccination strategies when the edges are sensitive and differential privacy guarantees are needed. Our main contributions are $(\varepsilon,\delta)$-differentially private algorithms for designing vaccination strategies by reducing the maximum degree and spectral radius. Our key technique is a private algorithm for the multi-set multi-cover problem, which we use for controlling network properties. We evaluate privacy-utility tradeoffs of our algorithms on multiple synthetic and real-world networks, and show their effectiveness.

Figures

Figures reproduced from arXiv: 2506.00745 by the authors.

Figure 1
Figure 1. Effect of Privacy on Budget Requirements on Montgomery County Subnets [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Effect of Privacy on Budget Requirements on BTER Graphs [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Effect of Privacy on Max Degree Violation on BTER Graphs [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Effect of Privacy on Spectral Radius on BTER Graphs [PITH_FULL_IMAGE:figures/full_fig_p021_4.png]
Figure 5
Figure 5. Figure 5: Tradeoff of Degree Violation vs Budget on BTER Graphs [PITH_FULL_IMAGE:figures/full_fig_p022_5.png]
Figure 6
Figure 6. Figure 6: Tradeoff of Spectral Radius vs Budget on BTER Graphs [PITH_FULL_IMAGE:figures/full_fig_p022_6.png]
Figure 7
Figure 7. Figure 7: Tradeoff of Spectral Radius vs Budget on BTER Graphs for Implicit Solution ( [PITH_FULL_IMAGE:figures/full_fig_p022_7.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

51 extracted references · 46 canonical work pages

  1. [19]

    Differentially private combinatorial optimization, 2009

    Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization, 2009

    work page 2009

  2. [1]

    Mathematical models for covid-19 pandemic: a comparative analysis

    Aniruddha Adiga, Devdatt Dubhashi, Bryan Lewis, Madhav Marathe, Srinivasan Venkatra- manan, and Anil Vullikanti. Mathematical models for covid-19 pandemic: a comparative analysis. Journal of the Indian Institute of Science, pages 1–15, 2020

    work page 2020

  3. [2]

    C. L. Barrett, R. J. Beckman, M. Khan, et al. Generation and analysis of large synthetic social contact networks. In Proceedings of the 2009 Winter Simulation Conference (WSC) , pages 1003–1014, 2009

    work page 2009

  4. [3]

    Differentially private data analysis of social networks via restricted sensitivity

    Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. Differentially private data analysis of social networks via restricted sensitivity. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS ’13, page 87–96, New York, NY , USA,

    work page

  5. [4]

    Bollobás and O

    B. Bollobás and O. Riordan. Robustness and vulnerability of scale-free random graphs. Internet Mathematics, 2004

    work page 2004

  6. [5]

    Privacy concerns can explain unwillingness to download and use contact tracing apps when covid-19 concerns are high

    Eugene Chan and Najam Saqib. Privacy concerns can explain unwillingness to download and use contact tracing apps when covid-19 concerns are high. Computers in Human Behavior, 119:106718, 01 2021

    work page 2021

  7. [6]

    Edge differential privacy for algebraic connectivity of graphs

    Bo Chen, Calvin Hawkins, Kasra Yazdani, and Matthew Hale. Edge differential privacy for algebraic connectivity of graphs. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 2764–2769. IEEE, 2021

    work page 2021

  8. [7]

    Differentially private computation of basic reproduction numbers in networked epidemic models

    Bo Chen, Baike She, Calvin Hawkins, Alex Benvenuti, Brandon Fallin, Philip E Paré, and Matthew Hale. Differentially private computation of basic reproduction numbers in networked epidemic models. In 2024 American Control Conference (ACC), pages 4422–4427. IEEE, 2024

    work page 2024

Show all 51 references
  1. [8]

    Effective social network-based allocation of covid-19 vaccines

    Jiangzhuo Chen, Stefan Hoops, Achla Marathe, Henning Mortveit, Bryan Lewis, Srinivasan Venkatramanan, Arash Haddadan, Parantapa Bhattacharya, Abhijin Adiga, Anil Vullikanti, et al. Effective social network-based allocation of covid-19 vaccines. InProceedings of the 28th ACM SI...

    2022

  2. [9]

    Efficient immunization strategies for computer networks and populations

    Reuven Cohen, Shlomo Havlin, and Daniel ben Avraham. Efficient immunization strategies for computer networks and populations. Phys. Rev. Lett., 91:247901, Dec 2003

    2003

  3. [10]

    Near-optimal correlation clustering with privacy

    Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, and Jakub M Tarnawski. Near-optimal correlation clustering with privacy. Advances in Neural Information Processing Systems, 35:33702–33715, 2022

    2022

  4. [11]

    Fine-grained privacy guarantees for coverage problems

    Laxman Dhulipala and George Z Li. Fine-grained privacy guarantees for coverage problems. arXiv preprint arXiv:2403.03337, 2024

    2024 arXiv

  5. [12]

    Differential privacy from locally adjustable graph algorithms: k-core decomposi- tion, low out-degree ordering, and densest subgraphs

    Laxman Dhulipala, Quanquan C Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdi Yu. Differential privacy from locally adjustable graph algorithms: k-core decomposi- tion, low out-degree ordering, and densest subgraphs. In 2022 IEEE 63rd Annual Symposium on Foundat...

    2022

  6. [13]

    The algorithmic foundations of differential privacy

    Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Founda- tions and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014

    2014

  7. [14]

    Eames, Jonathan M

    Ken T.D. Eames, Jonathan M. Read, and W. John Edmunds. Epidemic prediction and control in weighted networks. Epidemics, 1(1):70 – 76, 2009

    2009

  8. [15]

    Eubank, V

    S. Eubank, V . S. Anil Kumar, M. V . Marathe, A. Srinivasan, and N. Wang. Structure of Social Contact Networks and Their Impact on Epidemics. In Discrete Methods in Epidemiology , volume 70, pages 179–200. American Math. Soc., Providence, RI, 2006

    2006

  9. [16]

    Modelling disease outbreaks in realistic urban social networks

    Stephen Eubank, Hasan Guclu, VS Anil Kumar, Madhav V Marathe, Aravind Srinivasan, Zoltan Toroczkai, and Nan Wang. Modelling disease outbreaks in realistic urban social networks. Nature, 429(6988):180–184, 2004. 10

    2004

  10. [17]

    Some eigenvalue properties in graphs (conjectures of graffiti - ii)

    Odile Favaron, Maryvonne Mahéo, and Jean-François Saclé. Some eigenvalue properties in graphs (conjectures of graffiti - ii). Discret. Math., 111:197–220, 1993

    1993

  11. [18]

    Individualized privacy accounting via subsampling with applications in combinatorial optimization

    Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Adam Sealfon. Individualized privacy accounting via subsampling with applications in combinatorial optimization. arXiv preprint arXiv:2405.18534, 2024

    2024 arXiv

  12. [20]

    Node and edge differential privacy for graph laplacian spectra: Mechanisms and scaling laws

    Calvin Hawkins, Bo Chen, Kasra Yazdani, and Matthew Hale. Node and edge differential privacy for graph laplacian spectra: Mechanisms and scaling laws. IEEE Transactions on Network Science and Engineering, 11(2):1690–1701, 2023

    2023

  13. [21]

    Unbalanced graph cuts

    Ara Hayrapetyan, David Kempe, Martin Pál, and Zoya Svitkina. Unbalanced graph cuts. In Proceedings of the 13th Annual European Conference on Algorithms, ESA’05, page 191–202, Berlin, Heidelberg, 2005. Springer-Verlag

    2005

  14. [22]

    Locally differentially private analysis of graph statistics

    Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. Locally differentially private analysis of graph statistics. In 30th USENIX Symposium on Security, 2021

    2021

  15. [23]

    Differentially private community detection in attributed social networks

    Tianxi Ji, Changqing Luo, Yifan Guo, Jinlong Ji, Weixian Liao, and Pan Li. Differentially private community detection in attributed social networks. In Asian Conference on Machine Learning, pages 16–31. PMLR, 2019

    2019

  16. [24]

    New upper bounds on the spectral radius of graphs

    M Kargar and T Sistani. New upper bounds on the spectral radius of graphs. Journal of Mathematical Extension, 14(4), 2020

    2020

  17. [25]

    Private analysis of graph structure

    Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, and Grigory Yaroslavtsev. Private analysis of graph structure. ACM Transactions on Database Systems (TODS), 39(3):1–33, 2014

    2014

  18. [26]

    Analyz- ing graphs with node differential privacy

    Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Analyz- ing graphs with node differential privacy. In Proceedings of the 10th Theory of Cryptography Conference on Theory of Cryptography, TCC’13, pages 457–476, Berlin, Heidelberg, 2013. Springer-Verlag

    2013

  19. [27]

    Maximizing the spread of influence through a social network

    David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137–146, 2003

    2003

  20. [28]

    The bter graph model: Blocked two-level erdos-renyi

    Tamara Gibson Kolda, Ali Pinar, and Seshadhri Comandur. The bter graph model: Blocked two-level erdos-renyi. Technical report, Sandia National Lab.(SNL-CA), Livermore, CA (United States), 2011

    2011

  21. [29]

    SNAP Datasets: Stanford large network dataset collection

    Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014

    2014

  22. [30]

    Differentially private partial set cover with applications to facility location

    George Z Li, Dung Nguyen, and Anil Vullikanti. Differentially private partial set cover with applications to facility location. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, pages 4803–4811, 2023

    2023

  23. [31]

    Computing epidemic metrics with edge differential privacy

    George Z Li, Dung Nguyen, and Anil Vullikanti. Computing epidemic metrics with edge differential privacy. In International Conference on Artificial Intelligence and Statistics, pages 4303–4311. PMLR, 2024

    2024

  24. [32]

    Computational epidemiology

    Madhav Marathe and Anil Vullikanti. Computational epidemiology. Communications of the ACM, 56(7):88–96, 2013

    2013

  25. [33]

    Miller and James Mac Hyman

    Joel C. Miller and James Mac Hyman. Effective vaccination strategies for realistic social networks. pages 780–785, 2007

    2007

  26. [34]

    Differentially private densest subgraph detection

    Dung Nguyen and Anil Vullikanti. Differentially private densest subgraph detection. In 38th International Conference on Machine Learning (ICML). PMLR, July 2021. 11

    2021

  27. [35]

    Preciado

    Masaki Ogura and Victor M. Preciado. Optimal Containment of Epidemics in Temporal and Adaptive Networks, pages 241–266. Springer Singapore, Singapore, 2017

    2017

  28. [36]

    Epidemic processes in complex networks

    Romualdo Pastor-Satorras, Claudio Castellano, Piet Van Mieghem, and Alessandro Vespignani. Epidemic processes in complex networks. Reviews of modern physics, 87(3):925, 2015

    2015

  29. [37]

    Public perspectives on covid-19 vaccine prioritization

    Govind Persad, Ezekiel J Emanuel, Samantha Sangenito, Aaron Glickman, Steven Phillips, and Emily A Largent. Public perspectives on covid-19 vaccine prioritization. JAMA network open, 4(4):e217943–e217943, 2021

    2021

  30. [38]

    Threshold conditions for arbitrary cascade models on arbitrary networks

    B Aditya Prakash, Deepayan Chakrabarti, Nicholas C Valler, Michalis Faloutsos, and Christos Faloutsos. Threshold conditions for arbitrary cascade models on arbitrary networks. Knowledge and information systems, 33:549–575, 2012

    2012

  31. [39]

    Preciado, Michael Zargham, Chinwendu Enyioha, Ali Jadbabaie, and George J

    Victor M. Preciado, Michael Zargham, Chinwendu Enyioha, Ali Jadbabaie, and George J. Pappas. Optimal vaccine allocation to control epidemic outbreaks in arbitrary networks. In IEEE Conference on Decision and Control. IEEE, 2013

    2013

  32. [40]

    Preciado, Michael Zargham, Chinwendu Enyioha, Ali Jadbabaie, and George J

    Victor M. Preciado, Michael Zargham, Chinwendu Enyioha, Ali Jadbabaie, and George J. Pappas. Optimal resource allocation for network protection against spreading processes. In IEEE Transactions on Control of Network Systems, pages 99 – 108. IEEE, 2014

    2014

  33. [41]

    Preciado, Michael Zargham, and David Sun

    Victor M. Preciado, Michael Zargham, and David Sun. A convex framework to control spreading processes in directed networks. In Annual Conference on Information Sciences and Systems (CISS). IEEE, 2014

    2014

  34. [42]

    Rajagopalan and V .V

    S. Rajagopalan and V .V . Vazirani. Primal-dual rnc approximation algorithms for (multi)-set (multi)-cover and covering integer programs. In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pages 322–331, 1993

    1993

  35. [43]

    Differences in the mechanics of information diffusion across topics: idioms, political hashtags, and complex contagion on twitter

    Daniel M Romero, Brendan Meeder, and Jon Kleinberg. Differences in the mechanics of information diffusion across topics: idioms, political hashtags, and complex contagion on twitter. In Proceedings of the 20th international conference on World wide web, pages 695–704, 2011

    2011

  36. [44]

    Approximation algorithms for reducing the spectral radius to control epidemic spread

    Sudip Saha, Abhijin Adiga, B Aditya Prakash, and Anil Kumar S Vullikanti. Approximation algorithms for reducing the spectral radius to control epidemic spread. In Proceedings of the 2015 SIAM International Conference on Data Mining, pages 568–576. SIAM, 2015

    2015

  37. [45]

    Min-max multiway cut

    Zoya Svitkina and Éva Tardos. Min-max multiway cut. In Klaus Jansen, Sanjeev Khanna, José D. P. Rolim, and Dana Ron, editors,Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 207–218, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg

    2004

  38. [46]

    Decreasing the spectral radius of a graph by link removals

    Piet Van Mieghem, Dragan Stevanovi´c, Fernando Kuipers, Cong Li, Ruud Van De Bovenkamp, Daijie Liu, and Huijuan Wang. Decreasing the spectral radius of a graph by link removals. Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 84(1):016101, 2011

    2011

  39. [47]

    Differential privacy preserving spectral graph analysis

    Yue Wang, Xintao Wu, and Leting Wu. Differential privacy preserving spectral graph analysis. In Advances in Knowledge Discovery and Data Mining: 17th Pacific-Asia Conference, PAKDD 2013, Gold Coast, Australia, April 14-17, 2013, Proceedings, Part II 17 , pages 329–340. Springer, 2013

    2013

  40. [48]

    Efficient vaccination strategies for epidemic control using network information

    Yingrui Yang, Ashley McKhann, Sixing Chen, Guy Harling, and Jukka-Pekka Onnela. Efficient vaccination strategies for epidemic control using network information. Epidemics, 27:115 – 122, 2019

    2019

  41. [49]

    Procopiuc, Divesh Srivastava, and Xiaokui Xiao

    Jun Zhang, Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava, and Xiaokui Xiao. Private release of graph statistics using ladder functions. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data , SIGMOD ’15, page 731–745, New York, NY , USA...

    2015

  42. [51]

    algebraic connectivity

    studied the problem of estimating the reproductive number R0 of an epidemic on its contact network in the SIS and SIR models. The reproductive number R0 is closely related to the spectral radius, i.e., the reproductive number R0 can be expressed as a function of the first eige...

  43. [2013]

    Association for Computing Machinery

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.