The health emergency is the first challenge each country is facing in the fight to SARS-CoV-2. The next challenge, even more critical, is the safe reactivation of the production processes to prevent economic and social crises. Although the specialists agree that the study of a vaccine will have success, its distribution to the whole population will require more than one year, thus forcing a long coexistence with the virus. During this time, it will be crucial to understand how the infection is spreading across the population and take the best countermeasures to contain it without further lockdowns. The epidemic models currently used provide a macro-scale description of the spread, which allows forecasting the hospitals' load during the lockdown, but are partially ineffective when preventing the lockdown. An effective tool to partially analyse the current virus spread situations and identify the presence of infected individuals is the use of swabs, which have been used extensively. Nonetheless, the limited availability and the time required to test a large number of subjects makes them only a partial answer to the reconstruction of the disease transmission among the population. The scientific community agrees that contact-tracing applications could provide micro-scale data useful to contain the infection by driving the choice of the daily swab selection process. These applications can generate millions of punctual data that are combined with the clinical data available to ATS to reconstruct infection chains and networks, so as to identify potentially infected people. 1 At the moment, only direct contacts with the proven positive subjects are tested for SARS-CoV-2, while a more accurate analysis can suggest testing those subjects which have a high probability of being infected but only had indirect contact with the positive one. However, dealing with millions of data is unaffordable for humans and, therefore, Artificial Intelligence (AI) techniques are commonly considered the most promising technology for such tasks. Indeed, AI is capable of producing predictive models from data and reasoning on them to suggest where and when to use swabs to test for infected people. However, the potential of these techniques is not fully understood yet. More importantly, their applicability is limited by the severe European privacy regulation that requires the information on the individuals to only reside on their personal devices in an anonymized fashion. As a result, most of the current research regarding the spread of the SARS-CoV-2 is focused on the analysis of the behaviour of the disease by using epidemic models with or without the countermeasures used by the different nations. Conversely, to the best of our knowledge, few works study decisional methods, leading the individuals' choice to be tested during the daily tests for SARS-CoV-2.
Original contributions. In this work, we present an AI-based algorithm, namely PPTO, capable, in a distributed fashion as to avoid the violation of the privacy regulation, of identifying two classes of people whose roles are prominent in the infection: asymptomatic and presymptomatic subjects. The former ones are an important fraction of the infected people, and their identification is difficult, while the latter can transmit it with high probability. Our algorithm exploits a recently developed micro-scale epidemic model Ferretti et al. (2020) to reconstruct the infection chains from tracing app data and ranks the individuals according to the likelihood of being infected, so that the limited amount of daily tests available to the healthcare authorities can be used effectively. Furthermore, we evaluate the algorithm in a synthetic setting.
A large effort has been put in the modeling of the disease with predictive models depending on the different areas of diffusion of the virus, e.g., Girardi et al. (2020) and Gaeta (2020) for Italy, Toubiana and Bouaud (2020) for France, and Chen et al. (2020) for China. We mention other interesting works: Li et al. (2020) study the evolution over time of the virus behaviour, Hsiang et al. (2020) and Liu et al. (2020) analyse the effect of different contagion containment countermeasures, and Peak et al. (2020) analyse the monitor monitoring strategies. Staszkiewicz et al. (2020) provide a broader study to identify the main factors influencing the virus spread over the different countries, showing that the spread and mortality are determined by the number of connections among the continent (e.g., the airline traffic) and by some local characteristics of the country (e.g., the availability of medical personnel and the average air pollution). The aforementioned studies are mainly based on data regarding the number of infected individuals and on mathematical epidemic models describing the macro evolution a generic disease. These epidemic models provide a macro-scale description of the spread, which allows to forecast the hospitals' load during the lockdown, but are partially ineffective to prevent a new lockdown. Most importantly, they do not provide any support to design the best strategies to choose the individuals to test. Moreover, they do not take into account explicitly the data on the contacts between individuals, which are the main cause of the disease spread for the SARS-CoV-2 virus.
Prasse et al. study the evolution of the disease over the network, using a large-scale approximation of the contacts, in which every city is represented as a node of a graph. This way we might take decision on a macro-scale, i.e., how many test distribute in the different areas, but no suggestions on the single individuals are provided. The goal of the work by Shaghaghian and Coates (2017) is to infer the path that an infection has traversed in order to reach an arbitrary node in the SIR (Susceptible Infected Recovered) epidemiological model. This approach does not provide a clear decision on the tests to perform. Using message passing algorithms and statistical inference by maximum likelihood approach (see the work by Lokhov et al. However, most of the proposed solutions are not viable since they requires that the information about the contacts between couple of individuals are stored and elaborated in a centralized manner. This constitutes a problem in terms of privacy, since a single attack to such a centralized unit would compromise the information about the contacts among the entire population. An alternative solution is the use of tracing apps, which can be used to identify the individuals with the most likelihood of being infected and their selection for the SARS-CoV-2 swab test (see Ahmed et al. (2020) for an extensive review). It has been proven that this strategy would greatly reduce the contagion curve Yasaka et al. (2020) . Nonetheless, even the use of specific apps raised some privacy concerns Tang (2020), e.g., the one developed for Singapore, namely TraceTogether. Therefore, in the last apps adopted by governments a specific protocol, namely PACT Chan et al. (2020) , is adopted. Using the guidelines provided by this protocol, the contact tracing apps are only allowed to exchange some identification codes, which should be changed frequently, between devices owned by individuals who entered in contact between each others. From the technological point of view Apple and Google are developing the guidelines for Bluetooth-based contact tracing apps. 2 This allows the people using these apps to preserve the personal information about the contacts she/he had in the past days and, at the same time, allow the authorities to determine which are the people who have been the most exposed to infected individuals. The method we are going to design is based on such apps and is in line with the PACT protocol and uses apps in line with the Apple-Google technological guidelines.
In this work, we use a new epidemic model that allows us to simulate the spread in a fine-grained fashion. In this model, namely SAPSR, at each time t ∈ {1, . . . , T }, the individuals of a population U are partitioned into 5 classes:
• S t : Susceptible individuals that did not contract the virus before t; • A t : Asymptomatic individuals that contracted the virus before t and will not manifest any symptom during the whole development of the disease; • P t : Presymptomatic individuals that contracted the virus before t without manifesting any symptom, but they will manifest some symptoms from some time τ ≥ t; • Y t : Symptomatic individuals that contracted the virus before t and present some symptom; • R t : Recovered individuals that were either asymptomatics or symptomatics before t, but that at t are not infected anymore. This category, at t, cannot infect other people and are immune to the disease.
The separation between asymptomatic and presymptomatic individuals in epidemic models is proposed by Ferretti et al. (2020) to capture properly the SARS-CoV-2 outbreak dynamics, as the virus transmission is mainly conveyed by these two classes of individuals. Indeed, symptomatic people are less likely to spread the contagion since they usually are promptly isolated as symptoms occur, while asymptomatics and presymptomatics have frequent contacts with susceptibles individuals, which consequently are more likely infected by individuals from these classes. However, once a contact occurs, symptomatics have the largest probability to infect a new individual, followed by presymptomatics and asymptomatics, who have the lowest probability of passing the disease. Therefore, the probability of spreading the disease should be differentiated among the three classes.
Our model describing contacts and contagions among individuals is as follows. The set of possible contacts occurring among different individuals is described by a graph G c (U, E c ), where the nodes U represents the entire population and E c is the set of undirected edges indicating if two nodes may have a contact. We associate a weight w u,v (t) to each edge in E c denoting the probability that two nodes u and v have a contact at time t. The rationale behind the choice of setting a different value for each pair of nodes is that some individuals pairs has recurrent and frequent contacts (e.g., family members, colleagues, and friends), while others have only sporadic encounters (e.g., people using public transportation). Notice that in the current study we focus on the transmission of the virus by direct contact between couples of people, i.e., occurred by exchanging respiratory droplets, since it has been shown that the virus can only survive few hours outside the human body Khadka et al. (2020) . However, this approach can be easily generalized to models and settings that include environemental contagions.
A contact between two individuals u and v is denoted with c u,v (t), and it is defined as a tuple (l u,v , r u,v , t), where l u,v denotes the distance between u and v, r u,v denotes the duration of the contact, and t is the time the contact between u and v occurred. 3 Let us denote with w u,v the probability that a specific contact between u and v occurs, and with C = {c u,v (t)} the set of all the contacts occurred between pair of nodes over a predefined time span, e.g., over two weeks. The contagion probability p(u, v, l u,v , r u,v ) between two individuals u and v depends on the state of the two nodes (one of them should be susceptible and one should have contracted the SARS-CoV-2), and on the duration r u,v and distance l u,v of the contact. More specifically, once a susceptible node u ∈ S t gets infected, it is removed from the population S t and it is included either in A t or P t according to the value of the probability of being symptomatic α s (u).
If an individual becomes asymptomatic at a specific time t 0 , she/he will remain in the asymptomatic population A t for a time span of t ∈ (t 0 , t 0 + τ u ), where τ u is the time required by an asymptomatic u to recover from the virus, i.e., to result not infected anymore, and may vary for each specific individual. Subsequently, at time t 0 + τ u , she/he will be included in the recovered population R t0+τu . Conversely, if an individual becomes presymptomatic at time t 0 , she/he will remain in the population P t for t ∈ (t 0 , t 0 + τ u ), and at time t + u , she/he will be included in the symptomatic population Y t+ u , where u denotes the incubation time that might be different for each individual.
Now we describe how the containment measures affect the contact and contagion probabilities among individuals. At each time t, a set of K t nodes can be tested. Each test v t ∈ V t is defined by a tuple (u, o u,t ), where u is the node tested Input: population sets S0, A0, P0, Y0, R0, contacts graph G c , time horizon T , tests policy P Output:
and o u,t ∈ {POSITIVE, NEGATIVE, WAITING} is the test outcome. The probability of getting a false negative is β f (u t ) and depends on the population to which u belongs.
Notice that the model we presented is flexible enough to be applied to infections others than the SARS-CoV-2 one. Indeed, modifying the contagion probabilities p(u, v, l u,v , r u,v ) as well as the false negative rate β(u t ), one might model also a large class of outbreaks.
In Algorithm 1, we provide a high level description about how our the interaction between couples of individuals is modeled. We are given with the initial populations S 0 , A 0 , P 0 , Y 0 , and R 0 , the contact graph G c , and a given time horizon T for which we apply a testing policy P, i.e., a strategy to select the individuals to test to limit the spread. At first, we initialize the set V of the individuals we already tested for SARS-CoV-2, the set C of the contacts occurred so far, and the set D containing the information stored by all the devices. Initially, they are all empty. At each time t, we determine if a new contact occurred between each pair of individuals, which are stored in C new , and the corresponding data D u and D v are stored in the devices of the two individuals u and v (detailed in Algorithm 2). For each of the new contacts in C new we determine if a contagion between the involved nodes occurred (detailed in Algorithm 3), and update the populations S t , A t , P t , Y t , and R t depending if the contagion caused the creation of a new asymptomatic or presymptomatic infection and on the recovery of some of the individuals. Finally, we establish which are the nodes to be tested according to a tests policy P. The tested individuals, in case of positive outcome, will be isolated and, therefore, will not have contacts with other individuals in the following period.
Contract tracing apps represent one the main tools that the governments adopted to tackle this outbreak. Though in some countries these tools can collect fine grained data including, beyond contacts, personal and GPS information, most of the European countries developed solutions that aim also at preserving privacy by introducing some constraints on how data can be collected. These constraints brought the development of different solutions that exploit Bluetooth technologies and security protocols to preserve users privacy. In what follows, we focus on the general schema followed by Immuni, the official Italian contact tracing application. 4 The data update procedure occurring on each individual's device is detailed in Algorithm 2. It generates for each contact a random code, a.k.a. token, h u,t and h v,t for each individual involved in a contact. Subsequently, it updates the data stored in each individual's device D u and D v with an entry listing the time t the contact occurred, the tokens of the two individuals and the distance l u,v and duration r u,v of the contact. To summarize, each entry d ∈ D u in a user's u device database is a tuple d = (t, h u,t , h v,t , l u,v , r u,v ) characterizing the contact she/he has had in the past.
The evolution of the populations set describing the virus evolution is detailed in Algorithm 3. At first if checks if any new contact in C new generated a new infected individual, according to the contagion probability p(u, v, l u,v , r u,v ). According to the response of the individuals, i.e., she/he can be categorized as a presymptomatic or an asymptomatic patient, she/he is moved from the susceptible set S to either the set P or A, respectively. After that, we check if any presymptomatic u ∈ P showed some symptoms and, therefore, is moved to the symptomatic set Y . Finally, the contagion evolves by moving the status of all the asymptomatics and symptomatics who recovered to the set R.
Given a population U and a time horizon T ∈ N, ideally, we aim at finding, at each day t ∈ {1, . . . , T }, a subset X t ⊂ U of K t nodes to isolate to minimize the total number of infected over the time horizon T . However, solving such a problem would require a complete knowledge of the contact network C in terms of contacts and contagion probabilities. Unfortunately, in our scenario, this information is not available since the structure of the network changes Algorithm 2 updateDevicesData(D u , D v , c u,v,t ) Input: devices data Du, Dv, new contact cu,v,t Output: updated data (Du, Dv) hu,t ← RandomToken() hv,t ← RandomToken() Du ← Du ∪ {(t, hu,t, hv,t, lu,v, ru,v)} Dv ← Dv ∪ {(t, hv,t, hu,t, lu,v, ru,v)} Algorithm 3 contagionStep(C new , S, A, P, Y, R) Input: new contacts set Cnew, population sets S, A, P , Y , R Output: updated populations sets S,
over time, and due to the privacy policies of the contact tracing apps. Indeed, we are able only to exploit the data coming from the different devices D u in a decentralized fashion, since collecting centralized contacts data is forbidden . A natural reformulation of the problem when this information is lacking consists in assuming that all the individuals might have contacts with each other individuals, or, formally, that the contact graph is complete G c .
As a consequence, we are allowed only to use as available data the device database D u , and the probability of getting infected for each contact between individuals p (u, v, d u,v , r u,v ) . We reformulate the problem of minimizing the virus spread as the task of finding, at a time step t, the subset of nodes X t ∈ U with the K t largest probability of being contagious. Furthermore, assuming that an individual can be isolated if she/he has evident symptoms or after resulting positive from a test, and that the symptomatic individuals are known, the problem can be formally cast as the one of selecting the nodes that with largest probability of being contagious p c (u):
where | · | denotes the cardinality operator. In what follows, we describe the algorithm able to estimate the probabilities p c (u), inducing the policy P to perform the swab tests for SARS-CoV-2.
We start by introducing the assumptions required by our method. Our solution aim at exploiting a huge amount of data collected by the devices of the individuals to select the individuals which are most likely infected. The effectiveness of this method is strictly related to the individuals collaboration. Indeed, as shown by some previous study, it is necessary that a large portion of the individuals uses the contact tracing applications. Moreover, we require that all the individuals that present symptoms or results to be positive to a test communicate it to the local authorities, so that this information can be exploited to send notifications to high-risk individuals.
Input: number of available tests K, number of iterations N , current time step t, time window tw, set of newly positive discovered individuals Qt, contacts of the positive individuals ci Output: individuals to test Xt for n ∈ {1, . . . , N } do Sample randomly node i ∈ Qt sendRequest(n, ci, t)
The key idea of our method, namely Privacy Preserving Test Optimization (PPTO), is to exploit all devices to find the solution of the problem in Equation 1. Indeed, a distributed computation of the solution satisfies the privacy requirements imposed by the privacy-preserving policy of the governments. Starting from the devices of symptomatic (positive) individuals, we aim at identifying asymptomatic and presymptomatic individuals by reconstructing infection trajectories, i.e., path of infection occurred by contacts between couple of people, exploiting the contact tracing apps data. The algorithm assign at each user a score representing the infection risk level and indicating how many times a monte carlo-simulated infection trajectory included its device. Finally, given a limited amount of K available tests, the algorithm will suggests a set X t of the K individuals with the highest score.
In Algorithm 4 we provide a the core algorithm of our method, while Algorithm 5 we provide the operations required by the devices to allow a decentralized manner. The PPTO algorithm takes as input the number of available tests K, the number of iterations N , the current time step t and a time window t w for which we have to look for contagious people during the past time steps. The definition of the iteration N is required to limit the computational effort of the algorithm we run. Moreover, the algorithm required to have the set of nodes Q t that recently, i.e., in the last t w time steps, resulted to be positive in a test and communicated it to the authorities together with her/his the set of tokens used in the recent past, i.e., for each node i ∈ Q t , we need c i = {h i,j } t j=t−tw . Then, for N iterations, the algorithm samples a positive infected node i from Q t and simulate trajectories starting from it. A simulation is started by sending a request (sendRequest(n, c i , t)) to the device associated to the token c i . This request message provides also the information about the index of the current iteration n and the time instant t from which we want to start a trajectory. Each device i receives all the requests sent to the network, but only if the token transmitted in the request message is included in device dataset D i , then the score g is incremented, a flag f n associated to the current iteration n is set to True and the trajectory is propagated backward and forward to other network nodes, where the details of these procedures are described in Algorithm 6 and Algorithm 7, respectively. Finally, once a stop condition is satisfied, e.g., after a pre-specified time has passed, each device u communicates its score s to a central unit, so that it can communicate the set X t of K individuals with the largest score.
Using Algorithm 6 the trajectory is propagated backward to one of the contacts c ∈ C B , with c = (t , h u,t , h v,t , l u,v , r u,v ), that occurred for all time steps j ∈ {t − t w , . . . , t} according to a probability mass function γ(c). This function represents an unnormalized probability that a node is infected and is defined using the duration, distance, and order in which each contacts occurred:
where c = (t , h u,t , h v,t , l u,v , r u,v ). Finally, according to the probability distribution induced by γ(c) a single contactĉ is selected and a request is sent for the tokenĥ corresponding to the current device fromĉ.
In Algorithm 7 the trajectory is forward propagated to the contacts c occurred at time j ∈ {t, . . . , t + t w } according to the contagion probability p c (l u,v , r u,v ). More specifically, we send the token of the current device h present in the contact c if after the contagion occurred, i.e., we model this event as a Bernoulli variable with expected value p c (l u,v , r u,v )).
Here, we present an empirical evaluation of our method in different settings generated by a simulated environment and we compare its performance with the ones obtained with the following baseline testing policies:
Input: number of iterations N , starting time step t, time window tw Output: score g Initialize score g ← 0 h u,t , h v,t , lu,v, ru,v) , d ∈ Du | h v,t = h ∧ fn = F alse then fn ← T rue g ← g + 1 backwardTrajectory(t , n, tw) forwardTrajectory(t , n, tw) x = randomCode() s = (x, g) sendScore(s) Algorithm 6 backwardTrajectory(t , n, t w ) Input: starting time t , iteration index n, time window tw C B ← {d = (j, hu,j, hv,j, lu,v, ru,v) 
Extract the tokenĥ corresponding to the current device fromĉ sendRequest(n,ĥ) Algorithm 7 forwardTrajectory(t , n, t w ) Input: starting time tx, iteration index n, time window tw C F = {d = (j, hu,j, hv,j, lu,v, ru,v) , d ∈ Di : t < j < t + tw} for c ∈ C F do simulate a contagion with probability pc (lu,v, ru,v) if the contagion occurred then Extract the token h corresponding to the current device from c sendRequest(n, h)
• TS: test all the newly symptomatics individuals. If all the available test are not exploited, then the nodes to be tested are selected randomly.
• TSDC: test the infected nodes and their direct contacts . If all the available tests are not exploited, then the nodes to be tested are selected randomly.
We consider a setting with |U | = 10000 individuals, |E C | = 500000 and w u,v is set s.t., for each ìndividual u ∈ U , the average number of daily contacts is 10. We assume that the number of daily available tests is K = 100 and we set, at day t = 0, an initial number of infected nodes |Y 0 | = 5. At each day t, we test K individuals, and we assume that the tests results are available after one or two days with equal probability. In Table 2 we report the value of all the parameters we used for our model but we remark that some of the true parameters values are still unknown from the scientific community and therefore simulated data could not fit real ones. In this experiment, for sake of simplicity, we sample τ from a Uniform distribution U(τ min , τ max ) and we assume ot be sampled from a uniform distribution U( min , max ). In Figure 1 , we show the evolution populations |A t |, |P t |, |Y t |, |R t | without any containment measure, i.e., in a setting with K = 0. We notice that after 30 days, the asymptomatic, presymptomatic and symptomatic populations reach the 33%, 2.48 and the 2.3% of the whole population, while only the 0.35% of the individuals have recovered from the desease. In Figure 2 , we show how the number of infected individuals grow depending on the testing policy we adopt. Although, in these settings, there is not any policy that allows to stop the spread, we notice significant differencies in the containment of the spread depending on the policy we perform. More precisely, the adoption of our approach would bring to a reduction of the number of infected of the 50% if compared with TS approach, while it would determine a reduction of the 20% of the infected individuals if compared with the TSDC approach. 
In this paper we presented a novel algorithm for the identification of individuals that have high probability to spread the infection during the SARS-CoV-2 outbreak. We showed how to use the so called contact tracing apps and the data stored therein, to provide with a suggestions on the individuals to test for the positivity of the virus. This is crucial task for the containment of the contagion, due to the limited number of available tests the public healt organization are able to perform each day. Our algorithm suggests the set of individuals that should be tested to limit the spread by an innovative AI-based algorithm which communicate only by means of token generated by the different devices, thus preserving the private information of the app users.
As immediate future work, we will evaluate our method in realistic scenarios comparing it with tests policies currently employed by governments. However, simulating realistic scenarios is a hard task since the true values of some of the parameters of our epidemic model are still unknowkn to the scientific community, such as the probability of being asymptomatic, the contagion probability given a contact. For this reason, beyond exploiting information provided by new works in the scientific literature, we will design methods to estimate them by combining aggregated data about this epidemics. Furthermore, a further improvement will be the development of a framework in which these parameters can be estimated online gathering information trough the tests.
In this work, we focused on designing an algorithm that satisfies the privacy requirements. However, in real world scenarios, though this approach is designed to preserve privacy, some malicious users could attack the system to falsify the outcome of the algorithm. This issue, together with other securities aspects, should be further investigated to make this method usable in practice. Moreover, it would be interesting to compare our method with other state-of-the-art AI solutions that exploits centralized datasets to infer the probability of each individual of being contagious, and provide an analysis of the trade-off between privacy requirements satisfaction and effectiveness on the epidemics containment. u, v, l, r) probability of a contagion from u to v probability pc(u) probability of being contagious for u wu,v probability a contact between u and v lu,v distance of the contact between u and v ru,v duration of the contact between u and v C B set of contacts occurred between individuals α(u) probability of being asymptomatic for u Vt tests set v ∈ Vt tuple (u, ou,t) representing a test ou,t ∈ V test result β(u) false negative test probability β(u) false negative test probability N algorithm iterations Du device of individual u d ∈ Du tuple in device dataset hu,t ∈ d token sent by user u to user v hv,t ∈ d token received by user u from user v 0.02 p(u ∈ Pt, v ∈ St, l = 0, r ∈ {0, 1}) 0.05 p(u ∈ Yt, v ∈ St, l = 0, r ∈ {0, 1}) 0.07 p(u ∈ At, v ∈ St, l = 1, r ∈ {0, 1}) 0.03 p(u ∈ Pt, v ∈ St, l = 1, r ∈ {0, 1}) 0.06 p(u ∈ Yt, v ∈ St, l = 1, r ∈ {0, 1}) 0.08 α 0.1 β(u ∈ At) 0.4 β(u ∈ Pt) 0.2 β(u ∈ Yt) 0.05 τmin 5 τmax 15 min 1 max 12