Information Theoretic Optimal Surveillance for Epidemic Prevalence in Networks
Ritwick Mishra, Abhijin Adiga, Madhav Marathe, S. S. Ravi, Ravi Tandon, Anil Vullikanti · 2026
Read Information Theoretic Optimal Surveillance for Epidemic Prevalence in Networks by Ritwick Mishra, Abhijin Adiga, Madhav Marathe, S. S. Ravi, Ravi Tandon, Anil Vullikanti (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-04267.txt.
Introduction
Ritwick Mishra and five co-authors ask which people to watch if the goal is to learn an outbreak's true size. Surveillance is costly and biased, and earlier network methods picked watch sets to catch an outbreak early. Knowing the full size distribution, though, is what planners need, and that distribution can be complex and multi-peaked.
Their problem, TESTPREV, picks a node set that maximises mutual information with prevalence, a direct measure of what the sample reveals about outbreak size. Under an independent cascade model, all earlier surveillance choices can be highly suboptimal for this goal, and the problem is hard even to approximate. For several network classes the objective can still be computed fast. Their greedy method estimates the objective from cascade simulations and beats natural baselines on information and on expected variance.
Catalog record
| CREATOR | Ritwick Mishra, Abhijin Adiga, Madhav Marathe, S. S. Ravi, Ravi Tandon, Anil Vullikanti |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-04267
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Information Theoretic Optimal Surveillance for Epidemic Prevalence in Networks Ritwick Mishra, Abhijin Adiga, Madhav Marathe, S. S. Ravi, Ravi Tandon, Anil Vullikanti Abstract Estimating the true prevalence of an epidemic outbreak is a key public health problem. This is challenging because surveillance is usually resource intensive and biased. In the network setting, prior work on cost sensitive disease surveillance has focused on choosing a subset of individuals (or nodes) to minimize objectives such as probability of outbreak detection. Such methods do not give insights into the outbreak size distribution which, despite being complex and multi-modal, is very useful in public health planning. We introduce TestPrev , a problem of choosing a subset of nodes which maximizes the mutual information with disease prevalence, which directly provides information about the outbreak size distribution. We show that, under the independent cascade (IC) model, solutions computed by all prior disease surveillance approaches are highly sub-optimal for TestPrev in general. We also show that TestPrev is hard to even approximate. While this mutual information objective is computationally challenging for general networks, we show that it can be computed efficiently for various network classes. We present a greedy strategy, called GreedyMI , that uses estimates of mutual information from cascade simulations and thus can be applied on any network and disease model. We find that GreedyMI does better than natural baselines in terms of maximizing the mutual information as well as reducing the expected variance in outbreak size, under the IC model. 1 Introduction Effective surveillance in the context of disease outbreaks and contagion processes (e.g., modeled as SIR type processes on networks ( 15 ) ) involves monitoring or testing a subset of individuals (referred to henceforth as nodes ) to determine characteristics of an outbreak; see e.g., ( 19 ; 8 ; 27 ; 28 ; 2 ; 13 ) . This is also referred to as the problem of choosing “sensors” ( 19 ) . This is particularly important from a public health perspective because testing is very expensive, and resources are limited. In networked models of disease spread, a lot of prior work on surveillance has been on choosing optimal sensor sets, so that monitoring them allows a good estimation of metrics such as probability of infections, delay in detecting the outbreak (e.g., ( 19 ; 13 ) ) and time of peak (e.g., ( 8 ; 27 ) ). However, none of the prior methods provides information about the disease outbreak at a distribution level. Information theoretic strategies are a natural way to capture distribution level information, and such approaches have been developed in other settings, such as placing sensors for environmental monitoring. Using a Gaussian process based modeling approach, Caselton and Zidek ( 7 ) proposed the use of mutual information 1 1 1 Definitions of information theoretic concepts used in this paper can be found in standard texts such as 10 ; 20 . as the optimization criterion. Specifically, for a sensor set A\subset V , their goal is to maximize the mutual information I(X_{A};X_{V\setminus A}) , where X_{S} denotes the state vector for a subset S\subset V of nodes. Krause, Singh, and Guestrin ( 18 ) showed that this objective (referred to henceforth as the CZK objective) leads to sensor placements that are most informative regarding locations without sensors, compared to other objectives. Krause et al. ( 18 ) showed that finding a placement of sensors that maximizes this objective is NP-hard; they also showed that I(X_{A};X_{V\setminus A}) is a submodular function of A , and thus can be approximated well using a greedy strategy. Such an information theoretic perspective has not been studied for surveillance of disease outbreaks, and is our focus here. Specifically, we study the following: how should we select a subset A of nodes on a network which gives the most information about the outbreak size distribution, denoted by P(Z) , from the results obtained by testing only the nodes in A ? This is particularly useful in the case of disease outbreaks because they often exhibit threshold effects, e.g., ( 22 ; 25 ) , and a distribution level understanding gives better insights into the risk of having large outbreaks. Prior surveillance methods only optimize specific epidemic metrics, such as the probability of detection or peak. Their solutions cannot provide such insights about the outbreak, as we formally show. Our contributions. 1. We introduce a novel information theoretic criterion for optimizing surveillance for prevalence estimation. Motivated by ( 7 ; 18 ) , our goal is to choose a subset A which maximizes the mutual information I(X_{A};Z) with the prevalence (more generally, a weighted prevalence); we refer to this as the TestPrev problem. We show that, in general, subsets that optimize other epidemic objectives (e.g., detection probability), do not maximize the mutual information; they can be, in fact, arbitrarily away from the optimal mutual information. 2. We show that TestPrev is NP-hard, even to approximate within a \Theta(\log{n}) factor, where n is the number of nodes. We also show that there are significant differences between the TestPrev and CZK objectives. First, optimal solutions for the CZK objective can have arbitrarily low mutual information with the prevalence. Second, the CZK objective is computationally much simpler— it is submodular, and can be approximated within a (1-1/e) factor by a greedy algorithm, while the TestPrev objective cannot be approximated to within a \Theta(\log{n}) factor, unless P = NP . 3. In general, computing the mutual information is computationally challenging since it involves an exponential sum. We show that for trees and one-hop disease models, the value of mutual information can be computed efficiently. For a simple path network, we derive a closed form expression for the optimal solution to TestPrev . For the general setting, we present a greedy strategy, called GreedyMI , based on estimating the mutual information from cascade samples. 4. We evaluate our method through simulations over both synthetic networks and a real contact network between patients and providers in a hospital ICU, under various disease probability regimes. We compare the surveillance sets found by our method with natural baselines to show its efficacy in finding robust solutions. We find that GreedyMI outperforms the considered baselines and for budget as low as 2%, gives solutions with more than 60% reduction in variance about prevalence in many networks. 5. We analyze the solution sets in terms of their structural and dynamical properties. Our analysis reveals that GreedyMI achieves a favorable balance between relevance (i.e., high information content) and redundancy (i.e., low marginal information gain), outperforming baseline methods in this trade-off. For space reasons, proofs of some results are omitted. They can be found in the technical supplement. 2 Problem Definition Disease model. We consider the simplest SIR-type disease model on a network G=(V,E) , the Independent Cascade (IC) model. All nodes in the network except the Infected seed (s) start as Susceptible (S). At each time step, an Infected (I) node u can activate an adjacent Susceptible node v with probability \lambda_{(u,v)} , after which, it is Removed (R) from the process. The process continues until there are no more new infections. In a d -hop IC model, the spread is limited to a