## Konstantin Berestizshevsky , Koffi-Emmanuel Sadzi , Guy Even and Moni Shahar## |

Symbol | Domain | Description |
---|---|---|

[TeX:] $$\dot{\mathcal{X}}$$ | Set of all the people in the organization | |

[TeX:] $$\mathcal{D}$$ | Power set [TeX:] $$(\mathcal{X})$$ | Set of all the groups in the organization |

[TeX:] $$\text { riskext }(x)$$ | [0, 1] | The risk of a person x to get infected from the outside of the organization. |

[TeX:] $$\operatorname{risk}_{\text {int }}(x)$$ | [0, 1] | The risk of a person x to get infected from the inside of the organization due to personal susceptibility (not membership in groups) |

[TeX:] $$\text { risk }_{\text {int }}(d)$$ | [0, 1] | Risk of infection due to membership to group d |

[TeX:] $$\lambda(x)$$ | [0, 1] | Discount factor (influenced by time since recovery or quarantine) |

[TeX:] $$\tilde{\lambda}(x)$$ | [0, 1] | Discount factor used by the policy (influenced by time since known recovery, time since negative test, or quarantine) |

[TeX:] $$\delta(x)$$ | [0, 1] | Contagiousness of person x |

B | [TeX:] $$\mathbb{N}$$ | Daily budget of PCR-tests |

fact that we deal with testing and quarantining, rather than with vaccination. Additionally, we examine the quarantine efficiency (namely, the overlap between the quarantine period and illness period).

Machine-Learning based approaches learn the infection probabilities of individuals based on their features and reported interactions [18], [19]. Testees are chosen by combining graph neural networks and reinforcement learning.

This section describes the disease model we developed (Fig. 1 for a depiction of the state diagram of the model). The model employs individual parameters per person. In the subsections that follow, we describe the personal and group features (i.e., attributes) that affect susceptibility as well as infectiousness.

The community graph is a hypergraph [TeX:] $$G=(\mathcal{X}, \mathcal{D}),$$ where [TeX:] $$\mathcal{X}$$ denotes people and [TeX:] $$\mathcal{D}$$ denotes subsets of people that meet. We attach static features (i.e., attributes) per individual and per group. Individual features are partitioned to external and internal features. External features describe risks associated with the individual’s life style. In our implementation, we used the following external features: Number of working places, usage of public transportation, mobility (e.g., number of home visits per month in a boarding school), attendance of special events (e.g., weddings). Internal features describe risks associated with the individual’s role in the organization (not captured by membership in groups). In our implementation, we used the following internal features: Degree of interaction with people in the organization (e.g., caregiver vs. neighbor) and duration of interactions. Group features describe the risk associated with belonging to the group. In our implementation, we used the following group features: Quality of ventilation, density, and duration of interaction.

Transitions in the state diagram are stochastic. We attach a random variable [TeX:] $$T_{i}$$ per state and per individual, called state

TABLE II

Symbol | Description |
---|---|

spread(x) | A random variable that determines the spreading degree of x (this value is unknown to the policies) |

[TeX:] $$\alpha$$ | Vector of attribute weights related to the internal risk |

[TeX:] $$\beta$$ | Vector of attribute weights related to the external risk |

[TeX:] $$\gamma$$ | Vector of attribute weights related to group risks |

duration, that describes the number of days that a person remains in a state before a transition to the next state takes place. The state durations are random variables with the following distributions.

1) [TeX:] $$T_{0}=1.$$ Every day, person x may transition from the states “susceptible” or “recovered” to the state “infected”.

2) [TeX:] $$T_{1} \sim N(1,0.2).$$

3) [TeX:] $$T_{2} \sim N(2,0.3).$$

4) [TeX:] $$T_{3} \sim N(8,1).$$

5) [TeX:] $$T_{4} \sim 2+\operatorname{Exp}(0.5).$$

6) [TeX:] $$T_{5} \sim N(8,1)$$

For [TeX:] $$T_{1},$$ the average number of days before detection is 1. This is based on the work of Levine-Tiefenbrun et al. [20] that connects the viral load and the error rate. The duration of [TeX:] $$T_{1}+ \ T_{2}$$ is commonly referred to as the latent period of the disease, and the duration of [TeX:] $$T_{1}+T_{2}+T_{4}$$ is referred to as the incubation period. For COVID-19, the mean latent period was estimated as 3.3 days, and the mean incubation period was estimated to be 6.8 days [21]. Therefore, we tuned the parameters of [TeX:] $$T_{2}$$ and [TeX:] $$T_{4}$$ random variables to fit these reports, by having mean values of 2 and 4, respectively. For the variance of both [TeX:] $$T_{1} \text { and } T_{2}$$ we chose numbers much smaller than 1, so that, for a day-byday simulation, the duration of these stages can be viewed as deterministic. For [TeX:] $$\text { r } T_{3} \text { and } T_{5}$$ we based the distribution on the quarantine period [22]. For [TeX:] $$T_{4}$$ we based the numbers published on the official World Health Organization website [23].

There are three states with out-degree 2 (i.e., forks): “Susceptible”, “recovered”, and “contagious pre-symptomatic”. The choice of the next state (once the duration of the current state expires) is stochastic and is specified by the probabilities P(x infected) and [TeX:] $$P_{\text {symp }}(x).$$

We use the following notation. Let [TeX:] $$x \in \mathcal{X}$$ denote a person. Let [TeX:] $$\operatorname{ctg}(x) \in\{0,1\}$$ denote a predicate that indicates whether x is in one of the a contagious state (either contagious precontagious, contagious asymptomatic, or contagious symptomatic). Let [TeX:] $$\text { quarantined }(x) \in\{0,1\}$$ denote a predicate that indicates whether x is quarantined. Let spread(x) denote a random variable that determines the spreading degree of x. Let [TeX:] $$\delta(x)$$ denote the contagiousness of person x, defined by:

Let [TeX:] $$t_{\mathrm{rec}}(x)$$ denote the number of days that have elapsed since x entered the “recovered” state (if the state of x has never reached “recovered” yet, then [TeX:] $$\left.t_{\mathrm{rec}}(x)=\infty\right).$$ Let [TeX:] $$f_{\text {pos }}(t): \mathbb{N} \rightarrow \ [0,1]$$ denote a function that quantifies the susceptibility of a person to an infection as a function of the time from recovery [TeX:] $$\text { (i.e., } f_{\text {pos }}(t)$$ is a non-decreasing function that quantifies the “memory” of the immune system). In our implementation, we ruled out reinfection by defining:

One could easily modify the definition to account for the limited memory of the immune system or new variants that might cause reinfection. The [TeX:] $$f_{\text {pos }}$$ function can be also used to quantify the reduced susceptibility due to a vaccination, however we do not address the effect of vaccination in this study. Let [TeX:] $$\lambda(x) \in[0,1]$$ denote a personal susceptibility discount factor on the risk of person x.

In other words, [TeX:] $$\lambda(x)=0$$ if x has already been infected or is quarantined, else it is 1. Person x may be infected by a person outside [TeX:] $$\mathcal{X},$$ in which case we say that x is infected externally, or by a person in [TeX:] $$\mathcal{X},$$ in which case we say that x is infected internally.

infected internally. The probability that a person x is infected externally is defined as follows. Let [TeX:] $$\boldsymbol{z}(x)$$ denote the vector of external features of x. Let [TeX:] $$\beta$$ denote a vector of weights related to external risks. Define

The probability of external infection is given by:

The probability that a person x is infected internally is defined as follows. Let [TeX:] $$\alpha$$ denote a vector of weights related to internal risks. Let Let v(x) denote the internal features of person x. Let v(d) denote the group features of group d. Let [TeX:] $$\gamma$$ denote a vector of weights related to group risks. We define the internal risk factors per person and group as follows.

and the probability of person x infecting person y in group d is:

Note that [TeX:] $$\delta(x)>0$$ implies that x is contagious and not quarantined. We assume that infection events by the same individual are independent. Namely, the event that y infects x is independent of the event that y infects [TeX:] $$x^{\prime} \text { if } x \neq x^{\prime} .$$ In addition, we assume that the events of non-infection of x by y in different groups are independent. Namely, if x and y jointly belong to more than one group, then the events of non-infection in each group are independent. The probability that x infects y is therefore given by

The probability that x is infected internally is given by

Since x may be infected internally or externally, we have:

The transition of person x from the state “contagious pre-symptomatic” to “contagious-symptomatic” occurs with probability [TeX:] $$P_{\text {symp }}(x) ..$$ Based on studies in the literature of the rate of symptomatic people (Oran et al. [24] report 40%-45%, and Al-Qahtani et al. [25] report 30%–50%), we chose to fix

for every person [TeX:] $$x \in \mathcal{X}.$$

Intuitively, higher values of the probability [TeX:] $$P_{\text {symp }}$$ makes the problem easier because symptomatic people are quarantined and do not further spread the contagion. Conversely, lower values of the probability [TeX:] $$P_{\text {symp }}$$ (while all other parameters remain fixed) decreases severe cases and mortality. We, therefore, focus on the reported value of [TeX:] $$P_{\text {symp }}.$$

PCR-testing is employed to detect infected people [26]. PCR-tests are subject to errors (both false-positive and falsenegative). According to Wu et al. [27], false-positive rates are 12:16% for recovered people (i.e., state “recovered”). Cohen et al. [28] report a false-positive rate of 3:2% for susceptible people (i.e., state “susceptible”). Our simulator adopts these false-positive rates.

False-negative rates depend on the time since infection. Levine-Tiefenbrun et al. [20] report that false-negative rates are highest during the first 5 days after exposure (up to 22:8%), after which the false-negative rate reduces to 10:7%. Following this report, we set the false-negative rate in the simulator to:

1) 22:8% in the states “infected”, “detectable”, and “contagious-pre-symptomatic”.

2) 10:7% in the states “contagious-symptomatic” and the “contagious-asymptomatic”.

The policies are characterized by combinations of the following rules:

1) Quarantining of symptomatic people (SQ). Rule SQ dictates that every symptomatic person is immediately quarantined. A quarantined person cannot infect others.

2) Daily test samples (Test = (B,X)). Rule Test = (B,X) means that, every day, a sample of B people is tested among the un-quarantined people. The sampling algorithm X is one of three sampling algorithms: Rand, RFG, and Optimization. The Rand algorithm simply selects a random sample. The RFG algorithm selects the people with the top B weights (described in Section III-D). The Optimization algorithm selects B people computed by the optimization procedure described in Section III-E.

3) Testing of quarantined people (Retest(a; b)). A quarantined person is tested after (a - 1) days of quarantine. Further tests, if positive, are conducted every b days. After a negative test, a quarantined person is released.

We denote a policy by a three-tuple specifying the chosen rules.

The no-policy is a trivial policy in which no countermeasures are conducted (no tests and no quarantining). The no-policy is used as a reference of the contagion when no counter-measures are employed. One key feature that can be inferred from the no-policy approach is the herd-immunity. Namely, what is the morbidity ratio after which the epidemic decays in the absence of counter-measures? The herdimmunity threshold obtained from simulations serves as a “sanity-check” of the disease model as well as the simulator.

No tests are applied, but every symptomatic person is immediately quarantined. A quarantined person is tested starting from the 4th day of quarantine every 2 days until found negative. After a negative test, a quarantined person is released. The choice of the low values 4 and 2 allowed the research to focus on the selection of people for testing and isolation, by reducing the impact of recovered people being held in the quarantine. Choosing higher values will inevitably cause longer quarantining of the already recovered people and a reduction in quarantine efficiency (GQE, mPQE). We leave the exploration of a repeat testing for further work, and keep it fixed in our work. We do, however, provide an experimental section where we show the impact of reducing the repeat testing frequency from Retest(4, 2) to Retest(9, 7).

Every symptomatic person is quarantined. Every day, a random sample of B people among the unquarantined people is tested. Every positive person is quarantined. A quarantined person is tested starting from the 4th day of quarantine every 2 days until found negative. After a negative test, a quarantined person is released. We refer to this policy, in short, as Rand(B).

The RFG(B) policy is similar to Rand(B) except that the daily sample of B testees is computed greedily (rather than a random sample). The greedy selection of the testees assigns, every day, a weight [TeX:] $$w(x)$$ to every non-quarantined person [TeX:] $$x \in \mathcal{X}.$$ The B people with the highest weights constitute the sample for that day. We refer to this policy, in short, as RFG(B). We now elaborate on how weights are computed. The formula for the weight of person x is

[TeX:] $$\operatorname{risk}_{\text {ext }}(x), \text { risk }_{\text {int }}(x) \text { and } \text { risk }_{\text {int }}(d)$$ are defined in Section II. The parameter POS(d; T) equals the number of people in group d that were found positive in a test during the past T days. We note that the addition of 1 in the numerator of 13 is to avoid zeroing of the internal risk if no COVID-positive people were detected recently. We also note that the notation [TeX:] $$|d|$$ stands for the number of people in group d. The parameter [TeX:] $$\tilde{\lambda}(x)$$ is a discount factor defined by

Note that [TeX:] $$\lambda(x)$$ is a discount factor based on the ground truth, whereas [TeX:] $$\tilde{\lambda}$$ is a discount factor computed for the policy based on the information it has access to. The parameters [TeX:] $$t_{\mathrm{pos}}(x)$$ (resp., [TeX:] $$\left.t_{\text {neg }}(x)\right)$$ equals the number of days that have elapsed since the last positive test (resp., negative test) of person x. (If no such test result exists, then the parameter is set to [TeX:] $$\infty).$$ The function [TeX:] $$f_{\text {рos }}(t)$$ is defined in 2, from which it is implied that a person that was found positive in the past will receive [TeX:] $$f_{\text {pos }}=0,$$ and a person that has not yet been found positive will have [TeX:] $$f_{\mathrm{pos}}=1.$$ The function [TeX:] $$f_{\mathrm{neg}}(t)$$ is defined in 15

The definition of [TeX:] $$f_{\mathrm{neg}}(t)$$ implies that as the time since the last negative test grows, the likelihood of of infection increases. The monotone increase of [TeX:] $$f_{\text {neg }}(t)$$ provides negative incentive to test the same individual day after day. The precise numbers that define [TeX:] $$f_{\text {neg }}(t)$$ were chosen manually to alleviate the repetitive testing of the riskiest people in the community, however these values can be subject to a rigorous optimization, which we kept out of the scope of this work.

Conceptually, [TeX:] $$\tilde{\lambda}$$ is 0 for people who are either quarantined or recovered, and it degenerates to [TeX:] $$f_{\text {neg }}\left(t_{\text {neg }}(x)\right)$$ for other people (non-quarantined people who have not been known to be infected by COVID-19). The term [TeX:] $$f_{\text {neg }}\left(t_{\text {neg }}(x)\right)$$ causes people x who have recently been tested and found negative, to have their [TeX:] $$\tilde{\lambda}(x)$$ (and consequently w(x)) to drop while other candidates receive a higher weight.

The goal of the weight function w(x), is to approximate the probability of x to become infected. The intuition behind the structure of w(x) is that the probability of becoming infected is affected by the fully observable static features of the people and the groups [TeX:] $$\left(r i s k_{\text {intext }}\right)$$ as well as by the partially observable information regarding the actual illness state gathered by the policy [TeX:] $$(\tilde{\lambda}, P O S(d, T)).$$

The optimization-based approach is identical to RFG(B), except in the way that the daily sample of testees is computed. The daily set of B testees among the non-quarantined people is computed by an optimization algorithm. The optimization algorithm solves a maximization problem in a form of a Linear Program (LP) and rounds the fractions to a f0; 1g-solution. The LP balances the “coverage” of groups rather than simply choose “riskiest” people.

The unknowns (i.e., variables) of the LP are [TeX:] $$s(x) \in[0,1],$$ for every non-quarantined person [TeX:] $$x \in \mathcal{X} \text {. }$$ A value s(x) = 1 means that x is surely in the sample, whereas, a value s(x) = 0 means that x is surely not in the sample.

The LP uses the following coefficients (i.e., knowns):

(i) B - number of testees per day.

(ii) V - the set of unquarantined people.

(iii) E - set of sufficiently heavy groups (see Equation 16).

(iv) w(x) - the weight of x as defined by Equation 13.

(v) [TeX:] $$w(d) \triangleq \sum_{x \in d} w(x)$$ - weight of group d.

The variable c(d), for group d, measures “coverage” of d and is determined by the values of s(x), for [TeX:] $$x \in d .$$ Namely, [TeX:] $$c(d) \in[0,1]$$ describes which portion of the group weight will be removed (“covered”) if the currently selected people will be tested. The variable z simply equals [TeX:] $$\min _{d \in E} c(d),$$ hence maximizing z requires obtaining a fair coverage of all the sufficiently large groups. The set E of sufficiently heavy groups is defined by

We define the set E of sufficiently heavy groups in order to avoid the optimization to be constrained on covering groups whose total weight is below half the average personal weight in the community. Without the restriction of the groups to the set E, the sample selected by the solution of the LP contained people unlikely to become infected, due to their association with small groups.

The formulation of the LP is as follows.

[TeX:] $$\begin{aligned} \operatorname{maximize} & z+\frac{1}{100 \cdot|E|} \sum_{d \in E} c(d) \\ \text { subject to } \quad \frac{1}{w(d)} \cdot \sum_{x \in d} s(x) \cdot w(x)=c(d) \quad \forall d \in E \\ c(d) \geq z \quad \forall d \in E \\ \sum_{x \in V} s(x) \leq B \\ s(x) \in[0,1] \forall x \in V \end{aligned}$$

Note that the second addend in the objective function 1=100. [TeX:] $$|E| \sum_{d \in E} c(d)$$ is used to provide incentive to utilize the budget B (even if a smaller fractional sample achieves the same value z).

The solution of the LP outputs a fractional-sample, namely, [TeX:] $$0 \leq s \leq 1,$$ for every [TeX:] $$x \in \mathcal{X} \text {. }$$ A sample of B people is obtained by randomized rounding as follows:

1) Let [TeX:] $$b(x) \in\{0,1\}$$ denote a Bernoulli random variable with probability [TeX:] $$s(x) . \text { Let } B^{\prime} \triangleq \sum_{x} b(x).$$

2) If [TeX:] $$B^{\prime}>B \text { : }$$ among the people with b(x) = 1, set b(x) = 0 for [TeX:] $$B^{\prime}-B$$ people with the lowest fractional values s(x).

3) If [TeX:] $$B^{\prime}<B:$$ among the people with b(x) = 0, set b(x) = 1 for [TeX:] $$B-B^{\prime}$$ people with the highest fractional values s(x). The sample is taken to be the set [TeX:] $$\{x \in \mathcal{X} \mid b(x)=1\}.$$

This section describes the quantitative metrics used to asses the performance of the different policies.

Notation: Let [TeX:] $$D_{x}^{(i s o)}$$ denote the set of days during which person x is isolated. Let [TeX:] $$D_{x}^{(c t g)}$$ denote the set of days during which person x is in one of the contagious states. For [TeX:] $$p \in \{i s o, c t g\}, \text { let } D^{(p)} \subset \mathbb{N} \times \mathcal{X}$$ denote the set

Namely, [TeX:] $$D^{(i s o)}$$ denotes the set of person-day pairs (x, t) in which person x is isolated on day t.

**1) Total Morbidity** - total number of infected people is defined by

The total morbidity is an important metric for estimating mortality, severe cases of illness, etc.

**2) Peak Morbidity** - maximum number of simultaneously contagious people is defined by

Keeping the peak morbidity low (i.e., “flattening of the curve”) is extremely important to avoid the collapse of the healthcare system. When peak morbidity is bigger than the capacity of hospitals, proper medical treatment is infeasible, thus leading to rejection and prioritization of patients.

3) [TeX:] $$P Q E_{x}$$ - Personal quarantine efficiency of person x.

where [TeX:] $$\epsilon \in \mathbb{R}^{>}$$ is arbitrarily small constant (to avoid division by zero). We use [TeX:] $$\epsilon=2.22 \times 10^{-16}$$ in our implementation, as it was the smallest representable floating point number on the system we used.

The [TeX:] $$P Q E_{x}$$ metric is an intersection-over-union metric that captures both the precision of quarantine days of x and the recall of the contagious period of x. This metric is similar to the F1 metric in which the denominator assigned half the weight to the symmetric difference.^{2} A value of [TeX:] $$P Q E_{x}=1$$ implies a perfect decision. Conversely, [TeX:] $$P Q E_{x}$$ close to 0 indicates a poor choice of quarantine days for person x. There are two causes for mistaken decisions: not quarantining when contagious and quarantining when not contagious. For simplicity, we treat both errors equally (of course, not quarantining when contagious has an adverse effect on controlling the epidemic).

^{2} [TeX:] $$F 1=\frac{\mid D_{x}^{(t s o)} \cap D_{x}^{(c t g)}}{\left|D_{x}^{(18 o)} \cap D_{x}^{(c t g)}\right|+0.5 \cdot\left(\left|D_{x}^{(i s o)} \Delta D_{x}^{(c t g)}\right|\right)}$$

4) mPQE - Mean personal quarantine efficiency across all people in [TeX:] $$\mathcal{X}$$

5) GQE - Global quarantine efficiency

As opposed to the mPQE measure, the GQE equally treats the value of all human-days, rather than treating the people equally. Ashcroft et al. [29] define a similar metric, referred to as “utility of quarantine”, as the ratio between the number of correctly chosen quarantine days and the total number of quarantine days. This metric captures the precision of the quarantine days of chosen by the policy, but does not penalize for a bad recall of the contagious period of the people^{3}. GQE metric on the other hand, addresses both the precision and the recall capabilities of the policy at hand.

^{3} 3For example, in a 1-person community, a policy that assigns a total of 2 quarantine days that overlap 2 out of 10 contagious days will result in a 100% utility of quarantine, whereas the GQE and the mPQE metrics will be at 20%

**6) Policy Efficiency Counters** : Number of human-days during which the person is (i) healthy and free, (ii) contagious and quarantined, (iii) healthy and quarantined, or (iv) contagious and free.

It is hard to theoretically evaluate the ability of an intervention policy to cope with a disease spread due to the complexity of the interactions within the community of people. Therefore, we employ the simulation-driven approach (i.e. empiricallydriven, rather than theory driven), which is widely used in the research of epidemic control [30]–[32]. Apart from epidemic control, the simulation an approach is widely used in the research of controlling other complex systems such as power grids [33] or communication networks [34].

The simulator executes a day-by-day simulation of the disease model for all the people in the community-graph. The simulator takes into account the decisions of the policy that may select testees and quarantine people found positive. The simulator and the policy are separate entities, and hence, a policy has only partial information about the ground truth. The input of the policy consists of the community graph, features of the people and the group, budget B of daily tests, results of tests, and the subset of people currently in the state “contagious symptomatic”. See Fig. 3 for a high level depiction of the simulation-policy framework. We note that, in addition to the budget of tests B, quarantined people are tested according to the retesting rule (e.g., Retest(4, 2)).

We examine different policies using 4 scenarios. Each scenario is defined by: (i) The community graph, (ii) the features of each individual (i.e., external and internal features) and (iii) the features of each group.

The community graphs were designed to represent a realistic interaction between students and teachers in a school. For example, the sizes of the classrooms were chosen to be the typical capacity of 30–40 students. The interaction of the people was chosen to be relatively local (students interact within a class much more than across classes. We also consider larger community graphs with 7 schools in which interaction between individuals from different schools is either through families or through groups of friends. Larger communities can be viewed as having another level of hierarchy in their structure.

Individual features included 4 external features (having multiple jobs, usage of public transportation, frequency of appearance in the community and extremely infection-prone activity outside the community) with the respective attribute weights [TeX:] $$\boldsymbol{\beta}=(0.1,0.1,0.1,0.7).$$ In addition, 3 internal features (Highly interacting person, degree of physical presence of a person, and other infectious-prone activity of a person) were equally weighted by the weight vector [TeX:] $$\alpha=(1 / 3,1 / 3,1 / 3).$$ The spreading degree (spread(x)) of people were assigned randomly with 5% of the people having a high value of 0.5 (being super-spreaders) and the rest of the people to values below 0:25. Group features consisted of 5 features (social distancing negligence, poor room ventilation, crowdedness, duration of interaction in the group, and other highly infectious-prone activity), and were weighted by [TeX:] $$\gamma=(0.06,0.06,0.06,0.412,0.412).$$ The risk factors and the weights are generic and were tuned to achieve a significant contagion phenomenon in the simulated communities, as will be presented in Figs. 4(a) and 5(a). Determining more realistic weights for these risk factors, as well as discovering novel risk factors, can be of a great contribution to the simulation fidelity. We encourage a research in this direction by providing an open-sourced, easily configurable simulator infrastructure, in which the risk factor weights can be adjusted without reprogramming, but rather using a configuration file.

We now elaborate on the 4 scenarios in more details.

1) Single-School: A single school consists of 150 people, with 4 classes of students approximately of the same size i.e., 37 students), where each class is isolated from the rest. Besides students, there are 7 teachers who visit all the classes. In addition to the teachers and the students, there are 3 managers that only interact between themselves, and there is also a cleaner that interacts with everyone in the organization. Average number of people a single person is in a direct contact with: 54.64.

2) Single-School-Mobility: This scenario is the same as the Single-School scenario with the modification that between every two adjacent classes there are 5 pairs of interactions. This modification represents a less strict social distancing rule. Average number of people a single person is in a direct contact with: 62.9.

3) Multischool-Families: A community of 1000 people, consisting of 7 schools of the following form: 4 “Single- School”-type schools and 3 “Single-School-Mobility”-type schools. Schools are indexed 1 through 7, and two schools are adjacent if the absolute difference of the indexes is 1. In addition to the schools, there are 300 small groups referred to as families with an average of 2.3 children per family. The children of a family attend either a single school or two adjacent schools. Average number of people a single person is in a direct contact with: 57.

Families scenario, however, instead of the 300 small families, there are 13 groups of friends. Groups of friends consist of 10 groups of students, each consisting of approximately 50 students drawn at random from all schools; and 3 groups of teachers with 5, 7 and 12 teachers each. The teachers are chosen at random from all the teachers in all of the schools. Average number of people a single person is in a direct contact with: 76.

In every experiment, we evaluate the 5 policies that were presented in section III. The policies are referred to as: No-policy, symptom-based, Rand(B), RFG(B) and Optimization(B). The policies that apply tests are examined with different test budgets.

Initially, on day-1, all people are in the state “susceptible”. From this initial configuration, a day-by-day simulation runs for a total duration of either 150 days for the small scenarios (Single-School scenarios) and 300 days for larger scenarios (Multischool scenarios).

Each scenario-policy-budget combination runs in a separate simulation, for which we record the metrics described in section IV. Due to the stochastic nature of the simulation, we repeat the simulation to achieve a statistical significance of the metrics. Specifically, for the small scenarios (Single- School scenarios) each simulation is repeated 50 times, and for the larger scenarios (Multischool scenarios) the simulation is repeated 10 times. We note that the Multischool scenarios have a regular structure (i.e., 7 schools consisting of 4 classes each). Thus, a simulation of a Multischool scenario is actually a simulation of 7 schools with some interactions between the schools. Indeed, simulations of Multischool scenarios exhibit smaller variance in the measured metrics across the 10 runs of the large scenarios compared to 50 runs of the smaller scenarios (i.e., Single-School).. All the recorded metrics are averaged across the repeating runs, and we report their mean values as well as standard deviations.

In order to make our results more realistic, we added two experiments: (1) Measure the effect of errors in PCRtests, and (2) measure the effect of retesting of quarantined people. Both these experiments were chosen in order to test the robustness of our optimization based policy. To show the impact of test errors, we introduced an error probability for tests into our simulation (based on numbers from the literature, as discussed in Section II-D), and compared the measures for the Multischool-Families scenario. Effects of retesting of quarantined people was simulated using the Multischool-Families scenario. The default testing policy we chose for quarantined person was Retest(4, 2) (i.e., starting from day 4 of quarantine, the person is tested once every 2 days until found negative). The less strict retesting rule we chose is Retest(9, 7). We dedicate section VI-D for the comparison between these two rules, and the impact they have on controlling the epidemic.

To gain an intuition regarding the effect of the policies on the morbidity, we present plots that show the daily number of infected people. To this end, we simulate all 5 policies in a Multischool-Families scenario with a budget of B = 40 daily tests, no test errors, and with a re-testing rule of Retest(4, 2). The simulations indicate that the more sophisticated policies exhibit a reduction in the total number of infected people (Fig. 4) as well as in the peak of morbidity (Fig. 5). Compared to the symptom-based policy, the optimized policy Optimization(40) reduced the total morbidity roughly by half, and the peak morbidity by roughly 40%.

In this section we compare the four metrics (total morbidity, peak morbidity, GQE, mPQE) with respect to the 5 policies. Our goal is to learn which policy is better in terms of morbidity reduction and in terms of quarantine efficiency.

Fig. 6 shows that, to achieve the same bound on total morbidity, the OPTIMIZATION-based policy requires roughly B=4 of the daily budget of tests compared to both Rand(B) and the RFG(B) policies (for small population refer to a budget [TeX:] $$B \approx 10,$$ for large population refer to a budget[TeX:] $$B \approx 15 \text { ). }$$

The reduction of the peak morbidity was also consistently better for the OPTIMIZATION strategy in all the scenarios. As can be seen in Fig. 7, the peak number of infected people is reduced by 5%-50% by the OPTIMIZATION policy (compared to the other policies).

The reduction in the morbidity is less profound in the Single-School-Mobility scenario rather than in the Single- School scenario and similarly for Multischool-Friends compared to Multischool-Families. Indeed, the connectivity of the community-graph for Single-School-Mobility is higher than

the connectivity-graph of Single-School. The same observation holds for the Multischool-Friends community-graph (which introduces large groups of friends that span across all the schools in the community) compared to the communitygraph of Multischool-Families. A stronger connectivity of the community graph results in (i) requirement of a larger test-budget in order to achieve a control over the disease (ii) lower personal quarantine efficiency.

It is easy to achieve low morbidity by increasing the number of quarantined people. We quantify the efficiency of quarantining using the intersection-over-union metrics. The GQE metric presented on Fig. 8 represents the global efficiency of the quarantine decisions, and these results show

that RAND and OPTIMIZATION policies are similarly efficient. The OPTIMIZATION and the RFG policies are especially prevalent in lower test budgets, whereas the RAND policy shows a competitive efficiency when using larger budgets in smaller communities (150 people). This is explained by the bias the OPTIMIZATION has towards the more risky people, whereas the RAND policy uniformly samples the people regardless of their risk factors. When the budget is large enough the uniform sampling pays off as it helps identifying the infected people that were less likely to become infected.

The mPQE metric, as shown on Fig. 9, is the highest for the OPTIMIZATION policy. The mPQE metric represents a fair efficiency metric with respect to the individuals. The mPQE metric values are generally higher than the the values observed for GQE due to the people that never became contagious, and hence they were easily not quarantined and contributed a perfect score of 1.0 to the mean value. The fact that the OPTIMIZATION policy leads both in morbidity reduction and global and personal efficiency indicates the superiority of Optimization over the other policies. Namely, the OPTIMIZATION policy manages to reduce the morbidity while maintaining individual fairness and community-level efficiency.

We present the results of Multischool-Families scenario simulation with 5 different policies in presence of realistic test errors. The simulation followed the error probabilities as defined in section II-D. Fig. 10 shows the total morbidity comparison between the simulation of error-free testing and testing with errors. The plots demonstrate that the superiority We present the results of Multischool-Families scenario simulation with 5 different policies in presence of realistic test errors. The simulation followed the error probabilities as defined in section II-D. Fig. 10 shows the total morbidity comparison between the simulation of error-free testing and testing with errors. The plots demonstrate that the superiority

of the Optimization policy is sustained in the presence of testing errors.

The releasing from the quarantine in our previous experiments was based on the Retest(4, 2) re-testing rule. In this section we compare the total morbidity and the global quarantine efficiency (GQE) achieved by the Retest(4, 2) rule against a Retest(9, 2) rule.

Results presented in Fig. 12 show that, as expected, reducing re-testing of quarantined does not affect the morbidity. However, it does degrade the efficiency, as can be seen from the difference between Figs. 12(c) and 12(d). This can also be explicitly viewed in a form of increased isolation days incurred for the healthy people (Fig. 11).

The complexity of the running time can be decomposed into two components: (i) The simulation overhead which accounts

TABLE III

OPTIMIZATION | RFG | RAND | Symptom-based | nopolicy | |
---|---|---|---|---|---|

Single-School (150 people) | 0.08 | 0.05 | 0.04 | 0.03 | 0.02 |

Multischool (1000 people) | 1.99 | 1.70 | 1.64 | 1.39 | 1.18 |

for infection probability computation for each person and the maintenance of the illness states; (ii) the policy overhead, which accounts for the selection of candidates for testing from the non-quarantined people and the performing the repeat testing of the quarantined people.

The Simulation overhead is dominated by the infection probability computation which is [TeX:] $$\mathcal{O}(|\mathcal{X}| \cdot \Delta),$$ where [TeX:] $$\Delta$$ denotes the average number of people that each individual interacts with.

The policy overhead for the RAND policy is [TeX:] $$\mathcal{O}(|\mathcal{X}|)$$ since only a random choice of candidates for testing is required. The policy overhead for RFG policy increases this to [TeX:] $$\mathcal{O}(|\mathcal{X}| \text {. } (|\mathcal{D}|+\log |\mathcal{X}|))$$ due to weights computation (13) and sorting. The complexity of the OPTIMIZATION policy, which relies on the same weight computation as RFG, further increases due to the need to solve a linear program. The running time of the simulation is reported in Table III.

Two key parameters of a community which have a high impact on the spread of the infection are average distance between pairs of people over the community graph (average number of hops) and the small-set expansion-factor (i.e., for a small random set U of nodes, [TeX:] $$|U|$$ plus the number of neighbors of U divided by [TeX:] $$|U|).$$ The lower the average distance and the higher the expansion factor compared to the size of the community - the faster the contagion.

Table IV summarizes these parameters for the 4 communitygraphs that we considered. The expansion factors of each community with respect to group sizes [TeX:] $$|U| \in\{5,10,20,50\}$$ were computed by taking the average of expansion factors of 100 randomly selected subgroups U. The 2 smaller communities (i.e. the 150-people Single-School and Single-School- Mobility) exhibit a much lower average distance between two random people, and their expansion factor suggests that a random set of 5 people has an immediate connection to approximately 125 people (out of the total 150). In this case, the contagion happens extremely fast, rendering various policies less effective. On the other hand, 2 larger communities (i.e. the 1000-people Multischool-*) have a higher average distance and they do not expand small subsets to almost the entire population size. Therefore, the contagion becomes more manageable in the Multischool-* communities and this explains the overall more profound contribution of the proposed testing and isolation policies, as was observed in this section.

We remark that graphs such as preferential attachment [35] graphs and stochastic block graphs have high expansion and small average distance. Indeed, the main contribution of social distancing or limiting meetings to small numbers of people is in reducing the average distance and expansion factor parameters.

We consider a realistic simulation of COVID-19 contagion over a community-graph. With a limited daily budget of PCR-tests, it is beneficial to rely on the structure of the community-graph to select testees. This has been consistently observed throughout our quantitative comparison between policies which demonstrated that the Optimization policy is the most effective in reducing peak/total morbidity as well as maximizing quarantine efficiency. Namely, the policies that disregard the community structure (nopolicy and Symptombased, which do not perform tests; and Rand which applies tests randomly regardless of the grouped structure of the community) performed worse both in terms of quarantine efficiency and in terms of morbidity reduction. The success of the RFG and Optimization stems from the community structure-aware weight functions, according to which the policies rank the people for testing. Further superiority of the Optimization policy over the Rand is achieved thanks to the constraint that forces a fair coverage (via testing) of all the groups in the community. The fair coverage mitigates outbreaks across the community.

In addition, we show that our conclusions are robust to realistic PCR testing errors, and we describe the relation

between the effectiveness of the testing policies and the connectivity metrics (average distance and expansion factor) of the communities at hand.

During peak morbidity in Israel, the daily budget of tests reached 0:5 2% of the population. It seems that exceeding this budget is not feasible for large populations. The community-graph models the interactions between people, and therefore, can help perform investigations of “chains-ofcontagion”. A common policy is to test or quarantine people that have interacted with positive people. We note that such a policy may require too many tests (i.e., testing much more than 1% of the population per day). The proposed policies (RFG,OPTIMIZATION) carry out such epidemiological investigations indirectly. Indeed, the presence of a positive individual in a group increases the weight of the group members, and hence, the likelihood of these individuals to be selected for testing.

We suggest two directions for further research based on learning. The first direction deals with the problem that the accumulation of data regarding the features of individuals and groups is costly, time-consuming, and error-prone. Further work should consider methods for extracting such features from available sources such as location from phones, registration upon entry to groups, and filling of online forms. Determining the weights of such features can be a great contribution to the overall fidelity of the simulator environment, and worth investigating as well. The second direction suggests to employ our simulator as an environment simulation for training a reinforcement-learning agent. Our hope is that such an agent can outperform the OPTIMIZATION-policy.

Konstantin Berestizshevsky received his B.Sc. in Electrical Engineering and Computer Science in 2014 and the M.Sc. in Electrical Engineering in 2016, both from the Tel-Aviv University. He is currently working on his Ph.D. in Tel Aviv University. His main interests are efficient Deep Learning models and applications of Deep Learning in various fields including recommender systems, computer vision, smart power grid and analytical chemistry.

Guy Even received his B.Sc. degree in 1988 in Mathematics and Computer Science from the Hebrew University. Received his M.Sc. and D.Sc. in Computer Science from the Technion in 1991 and 1994, respectively. Dr. Even spent his Post-Doctorate in the University of the Saarland during 1995-1997. Since 1997, he is a faculty member in the School of Electrical Engineering in Tel-Aviv University. Prof. Even is interested in algorithms and their applications in various fields. He has published papers on the theory of VLSI, approximation algorithms, computer arithmetic, online algorithms, frequency assignment, scheduling, packetrouting, linear-programming decoding of LDPC codes, and data structures. He is on the editorial board of Theory of Computing Systems. Together with Moti Medina, Dr. Even wrote a digital hardware textbook titled Digital Logic Design: A Rigorous Approach published in 2012 by Cambridge University Press.

Moni Shahar received his B.Sc. degree in 1993 in Mathematics and Physics. He received his M.Sc. in Computer Science in 1997 and Ph.D. in Electrical Engineering in 2005, all from Tel-Aviv University. In the last 25 years he has held a variety of algorithmic leadership positions in the high-tech industry. His work spans a variety of areas including machine vision, NLP, algorithmic finance, machine learning and applied physics. In parallel to his industrial job, he teaches in the Department of Statistics and has published over 20 scientific papers. Currently he is the scientific manager of the AI and Data Science Center of Tel-Aviv University (TAD).

- 1 B. Tang et al., "The Effectiveness of Quarantine and Isolation Determine the Trend of the COVID-19 Epidemics in the Final Phase of the Current Outbreak in China,"
*International J. Infectious Diseases*, vol. 95, pp. 288-293, 2020.custom:[[[-]]] - 2 S. E. F. Yong et al., "Connecting Clusters of COVID-19: An Epidemiological and Serological Investigation,"
*The Lancet Infectious Diseases*, vol. 20, no. 7, pp. 809-815, 2020.custom:[[[-]]] - 3 N. Ahmed et al., "A Survey of COVID-19 Contact Tracing Apps,"
*IEEE Access*, vol. 8, pp. 134577-134601, 2020.custom:[[[-]]] - 4 P. Poletti et al., "Association of Age With Likelihood of Developing Symptoms and Critical Disease Among Close Contacts Exposed to Patients With Confirmed SARS-CoV-2 Infection in Italy,"
*JAMA Netw. Open*, vol. 4, no. 3, pp. e211085-e211085, Mar, 2021.custom:[[[-]]] - 5 H. W. Hethcote, "The Mathematics of Infectious Diseases,"
*SIAM review*, vol. 42, no. 4, pp. 599-653, 2000.doi:[[[10.1137/S0036144500371907]]] - 6 L. Peng, W. Yang, D. Zhang, C. Zhuge, L. Hong,
*Epidemic Analysis of COVID-19 in China by Dynamical Modeling*, arXiv preprint arXiv:2002.06563, 2020.custom:[[[-]]] - 7 I. Z. Kiss et al.,
*Mathematics of Epidemics on Networks*, Cham: Springer, vol. 598, 2017.custom:[[[-]]] - 8 J. M. Carcione, J. E. Santos, C. Bagaini, J. Ba, "A simulation of a covid-19 epidemic based on a deterministic seir model,"
*Frontiers Public Healthp. 230*, vol. 8, 2020.custom:[[[-]]] - 9
*P. Silva, 2020. (Online). Available:*, https://towardsdatascience.com/agent-based-simulation-of-covid19-health-and-economical-effects-6aa4ae0ff397 - 10
*H. Stevens, 2020. (Online). Available:*, https://www.washingtonpost.com/graphics/2020/world/corona-simulator/ - 11 K. Simler, "Outbreak,"
*2020. (Online). Available: https://meltingasphalt. com/interactive/outbreak/ . (Online). Available: https://meltingasphalt. com/interactive/outbreak/*, 2020.custom:[[[-]]] - 12
*Y . S. By Joe Fox and A. E. Fe, 2020. (Online). Available:*, https://www.washingtonpost.com/graphics/2020/health/coronavirus-how-epidemics-spread-and-end/ - 13 M. E. Newman, "Spread of Epidemic Disease on Networks,"
*Physical review Ep. 016128*, vol. 66, no. 1, 2002.custom:[[[-]]] - 14 Á. Bodó, G. Y. Katona, P. L. Simon, "SIS Epidemic Propagation on Hypergraphs,"
*Bulletin Mathematical Biology*, vol. 78, no. 4, pp. 713-735, 2016.custom:[[[-]]] - 15 I. Iacopini, G. Petri, A. Barrat, V. Latora, "Simplicial Models of Social Contagion,"
*Nature Commun.*, vol. 10, no. 1, pp. 1-9, 2019.custom:[[[-]]] - 16 G. F. de Arruda, G. Petri, Y. Moreno, "Social Contagion Models on Hypergraphs,"
*Physical Review Researchp. 023032*, vol. 2, no. 2, 2020.custom:[[[-]]] - 17 Y. Deng, S. Shen, Y. V orobeychik, "Optimization Methods for Decision Making in Disease Prevention and Epidemic Control,"
*Mathematical Biosciences*, vol. 246, no. 1, pp. 213-227, 2013.custom:[[[-]]] - 18 E. A. Meirom, H. Maron, S. Mannor, G. Chechik, "How to Stop Epidemics: Controlling Graph Dynamics with Reinforcement Learning and Graph Neural Networks,"
*arXiv preprint arXiv:2010.05313*, 2020.custom:[[[-]]] - 19 V. Kompella et al., "Reinforcement Learning for Optimization of COVID-19 Mitigation Policies,"
*arXivpreprintarXiv:2010.10560*, 2020.custom:[[[-]]] - 20 M. Levine-Tiefenbrun et al.,
*Association of COVID-19 RT-qPCR Test False-Negative Rate with Patient Age, Sex and Time Since Diagnosis*, medRxiv, 2020. (Online). Available: https://www.medrxiv.org/content/ early/2020/11/17/2020.10.30.2935, 2022.custom:[[[-]]] - 21 S. Zhao et al., "Estimating the Generation Interval and Inferring the Latent Period of Covid-19 from the Contact Tracing Data,"
*Epidemicsp. 100482*, vol. 36, 2021.custom:[[[-]]] - 22
*World health organization.*, (Online). Available: https://www.cdc.gov/coronavirus/2019-ncov/if-you-aresick/quarantine.html, (Online). Available: https://www.cdc.gov/coronavirus/-ncov/if-you-aresick/quarantine.html, 2019.custom:[[[-]]] - 23
*World health organization.*, (Online). Available: https://www.who.int/emergencies/diseases /novel-coronavirus2019/question-and-answers-hub/q-a-detail/coronavirus-disease-covid-19, (Online). Available: https://www.who.int/emergencies/diseases /novel-coronavirus/question-and-answers-hub/q-a-detail/coronavirus-disease-covid-19, 2019.custom:[[[-]]] - 24 D. P. Oran, E. J. Topol, "Prevalence of Asymptomatic SARS-CoV2 Infection: A Narrative Review,"
*Annals Internal Medicine*, vol. 173, no. 5, pp. 362-367, 2020.custom:[[[-]]] - 25 M. Al-Qahtani et al., "The Prevalence of Asymptomatic and Symptomatic COVID-19 in A Cohort of Quarantined Subjects,"
*International J. Infectious Diseases*, vol. 102, pp. 285-288, 2021.custom:[[[-]]] - 26 J. M. Bartlett, D. Stirling,
*A Short History of the Polymerase Chain Reaction*, PCR protocols. Springer, pp. 3-6, 2003.custom:[[[-]]] - 27 X. Wu et al., "A Follow-up Study Shows that Recovered Patients with Re-positive PCR Test in Wuhan May Mot be Infectious,"
*BMCmedicine*, vol. 19, no. 1, pp. 1-7, 2021.custom:[[[-]]] - 28
*A. N. Cohen and B. Kessel, medRxiv, 2020. (Online). Available:*, https://www.medrxiv.org/content/early/2020/05/20/2020.04.26.20080911 - 29 P. Ashcroft, S. Lehtinen, D. C. Angst, N. Low, S. Bonhoeffer,
*Quantifying the Impact of Quarantine Duration on COVID-19 Transmission*, Elife, p. e63704, vol. 10, 2021.custom:[[[-]]] - 30 P. Amar, "Pandæsim: An Epidemic Spreading Stochastic Simulator,"
*Biologyp. 299*, vol. 9, no. 9, 2020.custom:[[[-]]] - 31 F. D. Sahneh, A. Vajdi, H. Shakeri, F. Fan, C. Scoglio, "GEMFsim: A Stochastic Simulator for the Generalized Epidemic Modeling Framework,"
*J. Comput. Sci.*, vol. 22, pp. 36-44, 2017.doi:[[[10.1016/j.jocs.2017.08.014]]] - 32 A. Kuzdeuov et al., "A Network-based Stochastic Epidemic Simulator: Controlling COVID-19 with Region-specific Policies,"
*IEEE J. Biomed. Health Inform.*, vol. 24, no. 10, pp. 2743-2754, 2020.custom:[[[-]]] - 33 P. H. Nardelli et al., "Models for the Modern Power Grid,"
*European Physical J. Special Topics*, vol. 223, no. 12, pp. 2423-2437, 2014.custom:[[[-]]] - 34 A. Varga, R. Hornig, "An Overview of the OMNeT++ Simulation Environment," in
*Proc. ACM Simutools*, 2008;pp. 1-10. custom:[[[-]]] - 35 R. Albert, A.-L. Barabási,
*Statistical Mechanics of Complex Networks*, Reviews Modern Physics, p. 47, vol. 74, no. 1, 2002.custom:[[[-]]]