{'fraction_non_alphanumeric': 0.028478437754271765, 'fraction_numerical': 0.00971617288086919, 'mean_word_length': 4.603728040767065, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Surveillance Testing for Rapid Detection of Outbreaks in Facilities

This paper develops an agent-based disease spread model on a contact network in an effort to guide efforts at surveillance testing in small to moderate facilities such as nursing homes and meat-packing plants. The model employs Monte Carlo simulations of viral spread sample paths in the contact network. The original motivation was to detect COVID-19 outbreaks quickly in such facilities, but the model can be applied to any communicable disease. In particular, the model provides guidance on how many test to administer each day and on the importance of the testing order among staff or workers.


Introduction
In this paper, we develop an agent-based disease spread model on a contact network to optimize surveillance testing in facilities. Generally speaking, the model's scope involves facilities of small to moderate size, say, with dozens to hundreds of employees. The original motivation derives from the need to quickly detect outbreaks of COVID-19 in facilities such as nursing homes, factories, and meat-packing plants, in which close contact is nearly unavoidable. Our focus is on surveillance testing or proactive testing of staff. In other words, the premise is that there is not currently an outbreak in the facility, and the manager wishes to proactively test asymptomatic staff in order to quickly detect, and prevent, an outbreak. Given a contact network, along with other modeling parameters detailed in the sequel, the primary goal is to answer the following: 1. How many employees should be tested each day in order to detect an outbreak with a given probability? 2. What is the optimal sequence in which to test employees?
We propose a relatively simple Monte Carlo simulation model that is tailored to answering the two questions. Our model is similar to other agent-based SEIR models in the literature. However, the novelty is in our focus on optimization and decision making, and how it relates to the structure of the contact network. In the first part of the paper, we examine generic contact networks that may be of use when there is little data on the interactions in a facility. In the second part of the paper, we present more nuanced contact models, that are derived from the staff and interaction structure in nursing homes. Such models are preferred when there is detailed data on a facility's operations.

Literature Review
COVID-19 is a critical health issue worldwide and is likely to continue to be of concern for many years. Even with vaccine development, it is imperative to detect outbreaks at an early stage to develop effective mitigation measures. According to some studies, 38%-80% of cases are pre-symptomatic or asymptomatic in Long-Term-Care Centers (LTCs) [5,35]. Moreover, 56%-95.5% of disease transmissions are caused by asymptomatic cases [14,17]. Early in the COVID-19 pandemic, in many facilities, only individuals with COVID-like symptoms were tested, due to limited testing resources. However, several studies show that screening symptomatic cases only is not enough to control outbreaks [33,16,17]. Starting in March 2020, the Centers for Disease Control and Prevention (CDC) and the Centers for Medicare & Medicaid Services (CMS) offered various COVID-19 surveillance testing strategies to hospitals, nursing homes, schools, and other facilities, as the pandemic progressed. Now, surveillance testing is a widely applied strategy to contain the spread of the virus, especially for asymptomatic cases [4,12]. Apart from suggestions provided by the government, managers and researchers in various facilities developed their own surveillance testing strategies, combined with contact interventions, based on the facility's contact patterns and healthcare resources. In LTCs for example, the strategies include daily individual health screening via surveys or front desk checks [3,16], daily temperature and oxygen level checks [33], serological anti-body checks [31], and reverse transcription-polymerase chain reaction (RT-PCR) tests.
In terms of evaluation of testing strategies, some strategies are evaluated by outbreak case studies or analysis of publicly recorded data [1,8,21,23,32]. In addition, strategies may be evaluated using variations of the stochastic susceptible-exposed-infected-recovered/removed (SEIR) model. Some researchers have made modifications to the traditional SEIR model, to account for nuances of COVID-19. These include adding, removing, or subdividing the standard stages in the network. For example, the exposed stage E is sometimes removed, and the remaining SIR model is used [11,15]. Saha [26] sub-divides the infected stage I into detected and undetected infected stages. Chapman et al. [7] assume all infected individuals experience a pre-symptomatic stage, after which the corresponding node in the model transitions to an asymptomatic, mild symptomatic or severe symptomatic stage. Another innovation is to allow the parameters in the differential equations defining the SEIR model to be non-linear. Chen and Wei [9] and Shu et al. [28] assume that the parameters in the differential equations can be non-linear functions of time. Some studies modify parameters and the contact network structure over time. These adaptations are primarily used in comparing and finding the best surveillance screening and intervention strategies. Hou et al. [20] and Shaikh et al. [27] estimate the parameter settings under various surveillance testing and intervention efficacy assumptions and perform a parametric analysis. Ciaperon et al. [11] study the dynamic SEIR model by temporarily removing the edges in the contact network due to quarantine intervention for individuals who have COVID-like symptoms or tested positive.
One key assumption in the differential-equation-based SEIR models is that the population is well-mixed and features are homogeneous among individuals [7,9,10]. The standard SEIR model might be suitable for predicting outbreak progression in a large well-mixed population while it might over-simplify dynamics in special networks [10]. Broadly speaking, two ways to address these issues have been developed in the literature. One is to classify individuals who share similar characteristics into subgroups and use specific differential parameters in each subgroup. For example, Besse and Faye [6] divide the population by spatial features and use a standard SIR model with heterogeneous parameters in each spatial group. The disease transmission between groups is estimated by heat equations. Shaikh et al. [27] divide the population in an LTC by the occupations, and use different transmission probabilities for each group. A second solution, requiring significant computational effort, is to use network-based stochastic models that model each individual. Ames et al. [2] believe human social networks tend to be clustered and heterogeneous. In particular, they study disease transmission features in networks with various coefficient and clustering properties. Their results show that the structure of the network has a profound influence on disease progression. Similarly, Meyers et al. [24] test intervention strategies for severe acute respiratory syndrome (SARS) in various networks. Their analysis indicates that contact patterns in the network impact the size of epidemic significantly, even if the basic reproduction rates are the same among different networks. Herrera et al. [18] study surveillance strategies in different networks and find that the best surveillance strategies are based on network structures.
Rennert et al. [25] modify the SIR model by distinguishing symptomatic and pre-symptomatic stages and adding an isolation stage. Their results show that voluntary and random testing is not enough to protect students and faculty on a campus. They recommend performing rigorous testing during the semester. They also provide a novel solution by continuing to test the target group if a positive case in random surveillance occurs, which can be more effective in controlling disease spread. Chapman et al. [7] applied the SEIR model to simulate COVID-19 transmission in a congregated shelter population. The model was tested in shelters in San Francisco, Boston, and Seattle. The results showed that a combined strategy that involves daily screening, twice-weekly PCR testing and contact intervention is the best strategy to detect and avert an outbreak at an early stage. Smith et al. [29,30] used an individual-based SEIR model to simulate the transmission of COVID-19 based on detailed contact data in an LTC in order to find the best surveillance strategy. They compared the strategies when daily testing capacities of 1, 2, 4, 8, 16, and 32 are available.
Apart from COVID-19-based models, other researchers have discussed the importance of considering the structure of contact networks when designing surveillance strategies. For example, Herrera-Diestra et al. [19] study contact networks modeling the spread of foot-and-mouth disease among cattle farms in Turkey, and note that such networks have typical "small-world" properties. Although they suggest some general surveillance principles based on their observations, they do not provide detailed suggestions. Mastin et al. [22] examine the spread of plant pathogens. Their paper is close in spirit to our work, in that they focus of optimization of surveillance nodes by building a stochastic optimization model, using Monte Carlo samples. However, their model applies to a "static" surveillance strategy in which a fixed number of nodes are selected to aid detection. In this paper we investigate dynamic testing, in which different nodes are tested each day.
Overall, we note that most previous research focuses on the effectiveness of various surveillance strategies to detect an outbreak of COVID-19, but few papers provide guidance on specific testing strategies, especially when testing resources are in shortage. The model in this paper is predicated on the belief that decisions makers have different risk tolerances, which in turn determine the amount of testing that is performed. We also assume the contacts of individuals in a facility can be heterogeneous. We simulate disease progression on a network and find the probability of detecting an outbreak for various levels of testing capacities and time thresholds, as described in the next section.

Model Description
The first component of our model is a contact graph G = (V, E) on a set V of nodes and a set E of undirected edges. We call two nodes neighbors if they are connected by an edge. Each node in the graph corresponds to a single staff member, and there is an edge connecting them if they have close contact during a day, i.e., there is a non-zero probability of COVID-19 passing between them if one of them is infectious. Apart from the graph structure just described, the model is characterized by the following parameters: • K := |V |, the number of staff in the facility • p: daily probability of external infection • : latency, the number of days to move from the exposed state to the infected state • d: degree of each node in the symmetric case, indicating the density of contact graph • r: daily probability of infection between neighbors, a representation of the force of infection • f : false negative rate for a disease test, after a node is infectious • t: outbreak threshold tolerance, in days.
We now describe the progression of the disease through the network. The spread model is a discrete-time Markov chain, with time index n = 0, 1, 2, . . . . At each time point the nodes can be in one of three states: susceptible (S), exposed (E), and infected (I). We do not model recovered nodes since our focus is on detecting initial outbreaks, generally in less than 10 days from the first infected staff member entering the facility. Nodes may be exposed either from external interactions, or internal interactions. We also have simplified assumptions regarding the exposed and infected states. In the exposed state a node cannot spread the disease to other nodes and cannot be detected via a test. After exactly days, an exposed node becomes infected. When a node is infected, each neighboring susceptible node enters the exposed state with probability r each day. The sequence of events corresponding to infected nodes infecting susceptible nodes is assumed to be mutually independent, both among nodes and across days. In addition, to model external infections, each susceptible node can move directly to the infected state, each day, with probability p. The reason we assume this direct move is that an exposed node cannot be detected by a test, and cannot infect other nodes, until it is in the "infected" state. Hence, from a dynamic systems point of view, there is no need to track or model nodes that are just "exposed" externally. The sequence of events corresponding to external infections are also mutually independent. Finally, an external infection resulting in a change to the infected state obviously supersedes a pending move to "infected" if the same node has already been exposed internally.
In terms of disease testing, a decision maker can administer k tests per day to try to detect an outbreak. For simplicity, we assume that such a test is administered in the "morning" to each of the k individuals chosen that day, and that it is a rapid test, whose results are available before the staff member interacts with the rest of the staff. From the point of view of our model, this means that the tested individuals are identified immediately if: (a) they are tested on a given day, (b) are in the infected state on the same day, and (c) the test does not yield a false negative result on this day. At this point, we stop the process, since a detection has occurred. We do not assume that the test is perfect. Specifically, there is a false negative rate given by f . This rate applies to a test given to an individual that is already in the infected state. We assume the false negative rate is constant throughout the period a node is infected. This is obviously a simplification of the case for most diseases, such as COVID-19, in which the false negative rate fluctuates as an individual moves through the progression of the disease. However, recall that our model is generally concerned with rapid detection, within the first several days of infection (after the "incubation" period given by ).
Up until Section 5, we assume that the contact network is homogeneous in several ways. First, all nodes have an equal probability of external infection (characterized by p). Second, all nodes have equal degree and are vertex transitive (see Section 3.1). Third, each edge has an equal "weight," in that the infection force r is the same for every edge. In Section 5, we relax some of these assumptions to model heterogeneous contact networks, based on more realistic contact data. Part of the reason to first study homogeneous networks is to gain insights into different principles, such as the effect of the structure of the graph on testing thresholds and efficient testing protocols. To the best of our knowledge, these issues have not been studied before in the literature on surveillance testing.

Graph Structure
In our study of so-called homogeneous graphs, we confine our analysis to d-regular graphs, in order to preserve some sense of internal symmetry. In addition, this allows us to systematically explore the effect of internal interaction density, as embodied by the single parameter d. Of course, there are numerous other ways to quantify graph structure, even for d-regular graphs, but we do not explore those other avenues in this paper.
First, we recall that in a d-regular graph each node has exactly d neighbors. A complete graph is a d-regular graph in which each node is connected to every other node in the graph. Although there are many types of d-regular graphs for a given d, in this paper we only study the class of circulant graphs, which are always d-regular. A circulant graph is a graph whose adjacency matrix is a circulant matrix. More specifically, a circulant graph can be characterized by a vector (a 1 , a 2 , . . . , a m ) where a 1 < a 2 < · · · < a m−1 < a m and a m < (K + 1)/2. For simplicity, we assume that a m < K/2. In this case, the corresponding circulant graph is d-regular with d = 2m. This allows us to uniquely define m, for a specified even d (which we vary to study the effect of graph density on disease spread). The vector (a 1 , a 2 , . . . , a m ) is sometimes called the jump sequence, and it characterizes the connections in the graph as follows.
Circulant graphs are useful for our study as they have a number of desirable properties. As mentioned above, they are always d-regular, with a degree directly related to the parameter m. We also design our graphs so that they are always connected. Further, circulant graphs are vertex transitive so that, roughly speaking, every vertex looks similar. Note that circulant graphs need not be edge transitive and hence are not symmetric in the graph-theoretic sense. In studying the effect of graph structure and density on surveillance protocols, we use three classes of circulant graphs: complete graphs, neighboring graphs, and crossing graphs. The first class is standard. The latter two terms were created for this study. A neighboring graph is one in which the jump sequence is given by (1, 2, . . . , m). In other words, each node is connected to its m closest neighbors, if one envisions the nodes being arranged, as labeled, in a circle. A crossing graph is one in which the jump sequence is given by ( K/2 − 1 − m + 1, . . . , K/2 − 1 ). In this case, each is node is connected to its m farthest neighbors. In Figure 1 we display representatives of each graph class for a small network.

Monte Carlo Simulation
In order to answer the questions posed in the introduction, we perform Monte Carlo simulations of disease spread, and detection, on networks of varying structures and sizes. To keep the insights manageable, the parameters = 3, r = 0.05, and f = 0.21 are kept constant throughout the numerical studies. Otherwise, we vary network size, density, external infection rate, and the outbreak threshold tolerance. Given a particular network and testing protocol we typically simulate 50,000 outbreaks in a facility. An outbreak is initiated by at least one node becoming infectious at time 0, and the resulting nodes that are exposed and infected, until the outbreak threshold tolerance t, at which point the simulation is stopped. For each sample outbreak, we record whether or not there was a successful detection. An outbreak may not be detected due to an infected node not being tested, or due to a false negative result. These simulations then produce point estimates and confidence intervals on the true detection probability for a particular testing protocol. In general, we found 50,000 sample paths sufficient to distinguish among policies.
In our numerical results, the primary performance criterion is the probability of successfully detecting an outbreak within t days, given that an outbreak occurs. It is important to note that this is what one might call a conditional outbreak probability. We believe that it is more useful than computing the unconditional probability of detecting an outbreak, as this type of performance metric essentially penalizes a protocol for failing to detect an outbreak that does not exist. As we shall see below, this needs to be kept in mind, as some results under this metric might appear counterintuitive. For example, the probability of successful detection actually increases with the community infection rate of p. To see why, imagine the extreme case in which everyone walks in the door on day 1 infected with a disease and the false negative rate is 0. In this case, it does not matter who is tested, as everyone will set off the detection alarm.
In particular you only need one test to detect an outbreak when p = 1 and f = 0. However, when the community infection rate is very low, this means that it is very likely that one, and only one, person is the genesis of an outbreak. This makes the outbreak more difficult to detect with a small number of tests.

Parameter Comparisons
In our first set of experiments, we investigate the effect of graph density, embodied by the parameter d, on the number of tests per day needed to detect an outbreak. In our model, d represents the number of other staff members a particular staff member is in contact with each day. For example, when K = 100 and d = 99, the resulting contact network is a complete graph, and the graph implies that all staff members come into contact with all other staff members each day. Obviously, this is an extreme situation. As such, we also examine lower density networks. In Figure 2, we examine the case of 100 staff members and an external community infection probability of p = 0.0001 (per day). We set t = 6, indicating that our goal is to detect an outbreak within 6 days of the introduction of the disease into the facility. Keeping these parameters fixed, we plot the point estimates for the probability of detection versus the number of tests per day, and plot this curve for various values of d. The first thing to note is that there appear to be diminishing marginal benefits of administering more tests, as one might expect. From the graph we also see that the number of tests required to meet a certain benchmark probability of detection can vary significantly with d. For example, if our threshold probability is 0.7, and d = 99 then roughly 4 tests per day are needed. However, if d = 20 then about 13 tests per day are needed. This may seem counterintuitive but it is related to our observation above relating to the community infection rate. The more quickly a disease spreads in a facility, the more quickly it can be detected. We also observe that if we wish to enforce a very high (say 0.95) detection probability, then a large number of staff need to be tested daily. This is unlikely to be palatable for management and staff.  In the next set of experiments, we vary the outbreak threshold tolerance t while keeping other parameters fixed. We choose a neighboring graph with d = 60 as the results for this graph show the contrast among different tolerance levels well. The results are shown in Figure 3. As must be the case, the detection probability curves are nested, with larger tolerance curves dominating lower tolerance curves. Again we notice that the number of tests required to detect an outbreak at various tolerance levels varies widely. If the probability threshold is again 0.7, and t = 8 then just one test per day is needed. However, if t = 4 then around 10 tests per day are needed, which implies that all staff are tested every 10 days.
Finally, we examine the effect of the external infection probability on the detection probability curves. The networks tested in Figure 4 have the same parameters as the networks tested in Figure 3, with one exception: we change the value of p from 0.01 to 0.0001. For each tolerance level t we note that the curve corresponding to p = 0.01 dominates the curve for p = 0.0001. For example when the probability threshold is 0.7, t = 4, and p = 0.01, around 10 tests per day are needed, as observed above. However, when we examine the case with p = 0.0001 the required number of tests per day is approximately 17. At first glance, this may seem counterintuitive: we require fewer tests when a disease is more prevalent in the community. However, the result is mathematically sound. For example, suppose we examine the extreme case when p is very close to 1. In that case, a large number of staff members would arrive to the facility each day being infectious. As such, we only need to test a small fraction of the staff to detect an outbreak. In contrast, when the community infection rate is low, it is likely that only 1 staff member out of, say 100, would initiate an outbreak. This one seed of an outbreak is harder to catch with a low number of tests.

The Effect of Testing Order
In the experiments of Section 4.1, the nodes of the graph were tested in "standard order." What this means is that we envision the nodes with a fixed numbering, 0 to K − 1, and arranged in a circle according to the numbering. This numbering is used to characterize various types of circulant graphs, as described already. In addition, the standard  testing order is to begin by testing nodes 0 through k − 1 on day 1, then testing nodes k through 2k − 1 on day 2, etc. We continue testing in this manner, returning to node 1 when all nodes have been tested. Of course, for some values of t and K not all nodes will be tested. With respect to our simulation results, it does not matter with which node we start since outbreaks are simulated in a uniform manner across all nodes, and the graphs are vertex transitive. However, it is not clear that testing in this standard order, for any given initial starting node, is optimal. Obtaining the optimal testing order is computationally prohibitive, as the underlying optimization problem is a stochastic integer program, with a very large number of feasible solutions. In this paper, we make no attempt to prove optimality bounds on testing orders, or to develop complex heuristics. Rather, we examine a few different testing algorithms on circulant graphs. Our results indicate that the testing order has little effect on the detection probability, at least for circulant graphs. This is good news in that it indicates that optimizing the testing order likely is not a high priority in tuning test protocols in contact networks.
In our next set of experiments, we examine the effect of changing the testing order, while keeping all the network parameters fixed. In Figure 5 we examine three possible testing protocols. The first protocol, labeled "circle" is the standard order described in the previous paragraph. The second protocol, labeled "new" works as follows. The first node to be tested is chosen uniformly at random. Call this node A. The second node that is tested is the node that has the maximum distance from A, with ties broken randomly. Recall that the distance between two nodes in a graph is the number of edges in the shortest path connecting the nodes. To continue the selection process after some set of nodes has already been selected, the next node chosen is one whose sum of distances from all previously selected nodes is largest. To break ties among equal distance sums, we select a node for which these distances have the smallest sample standard deviation (if there is still a tie, it is broken randomly). We repeat the selection process until all nodes have been selected, to create an ordered list that defines the testing order. In our simulation analysis, we test the nodes in the given order and then return to the beginning of the list once all nodes have been tested once. The third protocol is based on a randomly selected permutation of the numbers 0 through K − 1.
For the neighboring graph testing in Figure 5, we see that the distance algorithm does slightly outperform the circle protocol for testing levels of about 5 to 10 nodes per day. This also implies a slight difference in the required number of tests at the mid-level probability thresholds. For example, for a probability threshold of 0.9 the difference in the required tests per day appears to be about 2. Outside this middle zone, the difference is essentially negligible. Note that we do expect the circle protocol to have a slightly lower performance in a neighboring graph. When the virus is most likely to spread among close neighbors, when the nodes are arranged in a circle, then there is some redundancy in testing nodes in this same circular order. It is better to hop across the circle for subsequent tests, which is essentially what the "new" protocol does.
We next test the same three testing protocols in a crossing graph. In Figure 6, we see that there is almost no difference in the three protocols, across a range of testing levels. This is also expected in this case. In a crossing graph, the testing protocols circle and new are quite similar, because nodes that are "neighbors" when arranged on a circle are actually rather distant as measured by the number of hops required to travel between such nodes. Again, these results indicate that testing protocol does not have a large effect on detection probability, at least for circulant graphs.
Finally, in Figure 7, we test the same protocols on a randomly generated d-regular graph. As expected, there are relatively small differences among protocols. We also tested protocols for different graph densities, and the results are similar to those presented herein. We conclude that the difference among testing orders is usually insignificant, with some minor differences as shown in Figure 5. Since the "new" protocol performs well in all cases, we recommend this protocol, assuming that the decision maker has concrete knowledge of the graph structure. Otherwise, nodes can likely be tested in an arbitrary manner, with little loss of performance versus a good heuristic.

Model adjustment
In previous sections, we considered simplified contact networks in order to gain insight into the relationship between the parameters of the graph, and the number of tests needed to detect an outbreak. In the remaining sections, we consider more general graphs that are inspired by real-world situations and data. A primary difference is that we allow the parameters r and p to be heterogeneous, i.e., they can vary by node. The outside probability of infection p may vary since each staff member has different social interactions and risk outside of work. Also, in real facilities staff in different categories can have very different contact patterns. Hence, the corresponding contact graph is no longer "symmetric," and the internal infection probability r can vary by node. Our assumptions regarding the latency l, the false negative rate f , and disease testing procedures are the same as in Section 3.
In many facilities, the staff rosters differ each day as do the contact patterns. In theory, it might be possible to develop even more nuanced models in a particular facility. For example, Duval et al. [13] studied the contact patterns in one nursing home by asking the staff and patients to use wearable sensors and recorded the contact duration, distances, and frequencies. However, for legal and ethical reasons, there are obviously significant barriers to collecting such detailed data in most facilities. Hence, we do not attempt to model a representative facility at this level of detail. Instead, we collect general data on staff levels, categories and interactions. We believe that this level of modeling still provides important insight into appropriate testing levels for outbreak detection.
Let c be the number of different staff categories in a facility. The staff categories are given by the C = {1, 2, ..., c}. Since we have heterogeneous internal infection parameters, we now use r c1,c2 to denote the daily probability of infection between staff members in categories c 1 and c 2 , assuming that they are connected by an edge in the contact  graph. Of course, we allow c 1 = c 2 to reflect interactions between staff in the same category. Staff in a facility can be categorized by their job titles, rosters, offices, working units, etc. In our real-world case study, we categorize the staff in a nursing home by job title, and we assume the staff with the same job titles share the same contact patterns.

Parameter fitting
We estimate the parameter r c1,c2 for different choices of c 1 and c 2 based on the contact patterns among staff. Inspired by Smith et al. [29] and Temime et al. [34], we use the contact frequencies, average duration of each contact, and the rate of infection with close contact to estimate the probability of internal infection for staff in various categories. Let p 0 be the probability of infection per minute between two individuals with close contact, d 0 the average contact duration (in minutes), and n 0 the average contact frequency. Then we can estimate the internal probability of infection as r = p 0 · d 0 · n 0 . We collected data from a nursing home in the northern US by collecting information from the facility manager. The details of this contact data are shown in Table 1. Next, for each staff category, we estimated the number of other staff they come into contact with daily, for all other categories. This data is shown in Table 2. For a job category in row i of the table, the i, jth entry in the upper part of the table is the average number of contacts for a staff member of category i with staff members in category j. Note that the table would not be symmetric if the lower half was filled in, but the data in the upper portion is sufficient to estimate contacts between all pairs of staff categories.
Based on this data, we are now able to generate a representative contact graph for the case-study nursing home. First, we label all the nodes in the graph with their corresponding staff category. Then, we calculate the probability of generating an edge between two nodes by using the data in Tables 1 and 2. For example, if a node is labeled as a nurse, the probability that a contact is triggered with another nurse node is 15/68 ≈ 0.22, as each nurse has an average of 15 contacts with the other 68 nurses during a shift. Then, for every pair of nurses, we generate a Bernoulli(0.22) random variable and assign an edge to this pair if the outcome is a 1. Otherwise, there is no edge connecting the pair. When generating edges between nodes in different staffing categories, we use similar logic. For example, the probability that there is an edge connecting a nurse with a member of the housekeeping staff is 1.5/16, since, using Table 2, each nurse has an average of 1.5 contacts per day with a member of the housekeeping staff. Figure 8 shows an instance of the contact network induced by the procedure just described. Our estimates of these r i,j values appear in Table 3. For example, if in the contact network there exists an edge between a nurse and a housekeeper, then the probability of transmission (per day) between these two staff members is 0.01. If there is no edge between two staff members, then    Of course, the official count new infections in most cases is underestimating the true number of cases. Therefore, in conducting sensitivity analysis, we multiply the estimate above by 3, 5, and 10.

Computational experiments
In this section, we present results using the network generated from the data in Tables 1, 2, and 3. Similar to Section 4.1, we vary some basic model parameters to perform comparisons. In the first set of experiments, we fix the probability of external infection to p = 0.003, and vary the outbreak threshold tolerance t. As shown in Figure 9, the results align with the experiments we did for the circulant graph. Obviously, as before, a larger tolerance value requires a smaller number of tests per day, for a fixed conditional probability target. For example, if the facility manager targets a 0.8 probability of detecting an outbreak, with t = 3 then approximately 44 tests per day are required. However, if the threshold of tolerance is set to 4, 5 or even 10 days, then the required number of tests per day is 29, 19 and 3, respectively. We also note for t = 3 the graph appears to be piecewise linear. This makes intuitive sense, as we do not benefit from the "network" effect of virus spread in this case.  Next, we examine the effect of changing p, the probability of external infection. Table 10 shows the results of our simulations. As argued in Section 4.1, although it is counterintuitive that higher values of p require fewer tests per day to meet a given probability target, this is actually a logical outcome of the model. Keeping this observation in mind, we note the a facility manager may want to examine additional metrics when setting the tolerance level t and the detection probability target. For one parameter setting in our case-study network, we provide in Figure 11 various statistics on the spread on infection, as reflected by 50,000 simulation runs. In Figure 11, the blue line represents the cumulative number of infectious staff, the red line represents the number of infected staff, and the yellow line represents the number of newly infected staff. The shaded areas around the lines represent 95% of confidence intervals around the point estimates for these quantities, various days after the outbreak. As expected, the blue line point estimate is higher than the red line, because infection occurs three days before an individual becomes infectious. Examining the graph, if a facility manager wishes to detect an outbreak before 10% of the staff becomes infected then she would set t = 5 for the network depicted in Figure 11.
Finally, in Figure 12 we show the proportion of infected staff in various categories over 20 days, again averaged over 50,000 simulated outbreaks. Note that receptionists and nurses are the categories with the highest infection proportions. In contrast, salon workers have the lowest infection rates in this example. Our discussions with nursing home staff, indicate that their perception is that nurses are quite vulnerable to outbreaks, but receptionists are not. However, if we scrutinize Table 1 we note that receptionists and nurses both have frequent, close, and prolonged contact with other staff, so the model does seem to be reflecting the data provided.

Effect of Testing Order
In Section 4.2, we examined the effects of testing order in what we called homogeneous graphs, i.e., graphs with a significant amount symmetry and homogeneity among the nodes. There, we found small, but mostly insignificant differences among testing protocols. In contact networks arising from the real world, the associated graphs are not expected to have such a regular structure. Due to the less regular structure, there are also a larger variety of heuristic testing protocols that can be tested. The most intuitive protocols are based on testing "central" or important nodes first.
In this section, we test three such heuristics of varying levels of complexity. In each heuristic we need to produce an ordered list (permutation) of the nodes that determines the testing protocol. The first heuristic, which we call degree rank, we simply order the nodes from highest degree to lowest degree, breaking ties in an arbitrary manner. Nodes are then tested in this order. The idea, of course, is a higher degree node is more likely to "detect" an outbreak since it has connections to lots of other nodes. The second heuristic, which is called PageRank, is based on the well-known node ranking system first developed by the founders of Google. We compute the PageRank for all nodes, and test in the order of highest rank to lowest. Again, the idea of this ranking is that higher ranked nodes would be visited more often by a virus surfing the contact network. A potential drawback of this notion, as applied to surveillance testing, is that PageRank is essentially derived from the steady-state distribution of the virus surfing process alluded to above. However, in our virus spread and detection model, we are really concerned with the transient behavior of the virus. In particular, what is most important for early detection is the initial trajectory of the virus over the network. This observation inspires us to consider another algorithm which we call simulation rank. The idea is as follows: if our outbreak tolerance is t days, then we are interested in testing the nodes that are most likely to be involved in an outbreak during the t days. In particular, we should rank the nodes according to the probability that they are part of a t-day outbreak. In theory, one could compute this probability exactly, but it is clearly an intractable computation for networks of even moderate size. Instead, we simulate many virus sample paths to estimate the aforementioned probability for each node, and then use these estimates to create the ranking. It is clear that the degree rank ordering requires very little computational effort, as it just involves counting edges. PageRank is more difficult, but there are efficient algorithms to estimate the PageRank, even for large networks. Finally, simulation rank requires a considerable amount of effort, as potentially thousands of simulation samples are required to get a good estimate.
In Figures 13 and 14, we show the results of testing the three ranking algorithms for test protocols. In each case, we determine the test order and then evaluate the protocol using the network depicted in Figure 8. As in our previous computations, we using 50,000 virus sample paths to perform the evaluation. Figure 13 displays the results for a tolerance of t = 4 days. Clearly, the difference among the algorithms is imperceptible in this figure. We also ran statistical tests confirming that there no statistically significant difference among the algorithms. Figure 14 displays the results for a tolerance of t = 7 days. Again, the differences are almost negligible, although PageRank appears to slightly outperform the other algorithms when 7 to 10 tests per days are performed. Still, these differences do not appear to be statistically significant. We performed similar tests on a small set of other networks, with similar results. Although the tests are not comprehensive, they seem to indicate that a relatively simple algorithm such as degree rank works just as well as more sophisticated algorithms.