The methods used to fight the spread of the contemporary COVID-19 epidemic have largely been the same as a hundred years ago during the Spanish flu [1, 2] . In particular, contact tracing has been used as a standard procedure that is well understood, both analytically and in network modeling approaches [3] [4] [5] [6] [7] . Some early papers even already considered the concept of recursive contact tracing, i.e. not only tracing direct contacts but also contacts of contacts and so on [8, 9] . However, lacking a technology to efficiently implement such a procedure, recursive contact tracing has thus far not been used.
However, the arrival of the SARS-CoV-2 epidemic, with its high asymptomatic transmission rate and the possibility of pre-symptomatic infections, presents new challenges that need addressing [10] [11] [12] . As such, a renewed interest in recursive contact tracing [13] [14] [15] [16] [17] [18] , as well as in digital contact tracing solutions [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] that could finally enable recursive contact tracing, has emerged in an effort to surpass the methods of a hundred years ago.
In this article, we introduce a simple model that considers an epidemic as a percolation problem, as is common in network epidemiology theory [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] , , in combination with a recursive contact tracing algorithm * lbaumgarten@itp.uni-bremen.de † bornholdt@itp.uni-bremen.de operating on the model. We will study the efficacy of recursive contact tracing and characterize the influence of a disease's asymptomatic transmission rate on the model's critical transition. Our model allows for arbitrary recursion depths, as has only been done in [14] , and our results, to the best of our knowledge, are the first to discuss the relationship of recursion depth and asymptomatic infection rate with regard to the critical transition.
We find a critical value in the fraction of nodes participating in the contact tracing (corresponding to tracing app usage) which depends on the asymptomatic transmission rate of the disease. Further we find a critical (maximum allowed) asymptomatic transmission rate as a function of the algorithm's recursion depth. We show that any disease with arbitrary basic reproduction number and finite asymptomatic rate can be stopped by a sufficiently large recursion depth. Finally, we validate our calculations using simulations on infection trees and networks with different degree distributions, as degree distribution can have a significant impact on an epidemic [34, 36, 38, [40] [41] [42] [43] [44] . Let us now start by defining the model.
We consider an SIR (susceptible, infected, removed) model with N nodes and an arbitrary degree distribution p(k) in which a proportion Φ of nodes take part in contact tracing ("use a contact tracing app"). Nodes in the network are infected with a virus with symptomatic rate Θ and basic reproduction number R 0 . It is known that in such a network, if we fix R 0 , the disease has a transmissibility [36] . Carriers of the disease will be able to infect their susceptible neighbors with probability T one time step after being infected themselves and be immune and non-contagious afterwards.
If an infectious person is symptomatic and uses the contact tracing app, this will trigger an alarm on the app and warn neighboring nodes of the chance of being infected, sending them into quarantine for their one infectious time step so they effectively skip the infectious state and jump directly to the recovered stage.
We can consider higher degrees of recursivity r for the app, meaning how many time steps in the past the app will consider to guess who might currently be infected. For r = 0, only the node's direct neighbors are sent into quarantine. For r = 1 in addition to those nodes who are quarantined for r = 0, any node with a distance of exactly three to the symptomatic node is quarantined, for r = 2 any node with a distance of five is quarantined, and so on. This is illustrated in Figure 1 . The algorithm disregards any possible immunities due to nodes having already been infected previously, but it does consider breaks in the infection chain that are caused by the app's own quarantining algorithm, i.e., if a node was quarantined at time t, the app does not consider this node a possible infection spreader at that time step. Given a vector S of symptomatically infected nodes at time t 0 ,
the vector of nodes U using the app, the vectors Q(t) of quarantined nodes and P (t) of not quarantined nodes at time steps t ≤ t 0 , and the adjacency matrix A, the vector of quarantined nodes at t = t 0 + 1 can be calculated by
Multiplications with P (·) ensure that a considered node in the backtracking chain was neither quarantined at its supposed time of infection nor at the time it could have infected its neighbors, and multiplications with U ensure that all nodes in the backtracking chain use the app. We now calculate the probability that an infected node is correctly put into quarantine by our algorithm. For this, we assume an infinitely large network, with a low enough fraction of the population being infected that an infected node is only quarantined as a result of its own infection chain and not coincidentally swept up in the quarantine caused by a different infection. We assume that the clustering in the network is negligible so that we can consider the infection chain effectively as a tree. For r = 0, both the infected node and the infecting node must be part of the network and the infecting node needs to be symptomatic. Therefore, a first approximation of the probability P r=0 q of an infected node being correctly put into quarantine is simply
However, because the infecting node cannot have been quarantined, its probability of using the app is
as the amount of nodes using the app with the ability to infect other nodes is reduced by a factor (1 − P r=0 q ), and therefore
For higher degrees of recursion, the chance of being quar- Red arrows indicate the spread of the infection, while black lines indicate non-infectious connections between nodes. The time t indicated on the right hand side marks the time at which infected nodes are infectious-or, in the case of the uninfected nodes, the latest time at which the app would consider them to be possibly infectious. While nodes could reappear in later time steps, e.g. the node in the t = 0 row could also be shown in the t = 2 row as it is connected to (most of) the nodes in the t = 1 row, we only show nodes once for visual clarity. At time t = 1 a symptomatic node triggers an alarm on the app. For recursion depth r = 0, only its nearest neighbors are quarantined. These quarantined nodes cannot infect any other nodes, as indicated by the blocked outgoing connections. For r = 1, the app considers every nearest neighbor of the symptomatic node as a possible origin of the symptomatic node's infection, and therefore quarantines all nodes that the infection could have spread to within two time steps from these nearest neighbors. This results in every node with a distance of exactly three to the symptomatic node being quarantined, so long as the connection is not interrupted by a node not using the app or by a node that was in quarantine itself at its time of infection or in the time step after infection, as shown on the right hand side. This can, of course, also include nodes which have not yet actually been in contact with any infected nodes, as shown by the leftmost nodes in the t = 1 and t = 2 rows. Note that, although the infection chain is shown in a tree-like structure for visual clarity, these nodes can be part of a network of arbitrary structure.
antined is increased
with P 0 = Θ
Here, in every part of the sum, the chance of a node having already been quarantined due to a lower recursion level is excluded via (1 − P i ), and a factor Φ is added for the chance of the next upstream node using the app. The factor Φ represents the chance of a node using the app if the next downstream node has not been quarantined, and needs to be used for nodes that are two or more levels above the currently regarded node in the infection tree. The chance of such a node using the app regardless of the behavior of its downstream nodes is Φ . The chance of a downstream node, which is using the app, of a node that is also using the app not being quarantined is approximately 1 − P r q ΦΦ . Since we assume both infecting node and infected node to be using the app, the factor ΦΦ is removed from P r q . This approximation disregards that the upstream node not being quarantined also influences the chance of its downstream node being quarantined. Then the chance of an upstream node using the app, given that its downstream node is using the app and has not been quarantined is
Next, we need to calculate the chance P i of a node being quarantined due to the i'th recursion step, given that its r nearest upstream nodes are using the app. For simplicity's sake, we start with P 1 . Here, a leaf node i is quarantined due to the first recursion step if any of the downstream nodes of i's second degree upstream node, which we call j, have been infected, use the app, and are symptomatic. The chance of one node fulfilling these conditions is Φ ΘT . Since just one node needs to cause an alarm on the app, the chance of being quarantined is
where n is the average number of j's downstream nodes minus one. We subtract one, since one of j's downstream nodes is i's direct upstream node and would already have caused i to be quarantined in the zero'th recursion step, if it were symptomatic. Since the chance of a node of degree k being infected is proportional to kp(k) [42] , the average number of downstream nodes minus one is
where we subtract two from k because of the one downstream node that is not considered and j's upstream node. Therefore,
We indicate how many connections are removed when calculating n via the variable x.
For the second recursion step, at least one of the downstream nodes of j's upstream node, which we call l, must fulfill the condition of P 1 , meaning that any one of their downstream nodes must be infected, using the app, and symptomatic. This chance is given by
Here, in P 1 (x), we do not discount one of each node's downstream nodes, since these nodes are not upstream nodes of node i, and therefore all of their downstream nodes need to be considered. Thus, we use P 1 (1) instead of P 1 (2). Also, we useΦ, because nodes that are using the app and symptomatically infected would have already caused a quarantine in a previous time step and can therefore not be part of the considered tree. Similarly, the equation for following recursion steps is
Summarizing these calculations, the chance of a leaf node being quarantined with a recursion degree of r is
and
Note that (17) is a self-consistent equation, since Φ and Φ contain P r q .
It is easy to see that the upper limit of P r q is
so contact tracing by recursive backtracking is strictly worse than vaccinating a fraction Φ of the population.
Since such a vaccination strategy is already insufficient to stop an epidemic on an infinitely large scale-free network with a degree distribution p(k) ∝ k −γ with γ ≤ 3 [42] , recursive backtracking can also not stop such an epidemic for Φ < 1.
However, there is still something that can be learned from taking a closer look at scale-free networks. For γ ≤ 3, the sum k k=2 k 2 p(k) in the exponent of the P i 's diverges, therefore P 1 → 1 (if ΦΘT > 0), and P r q becomes
We can see that all infected nodes that can be caught by the algorithm will already be detected in the first recursion step. Luckily, real world networks are not infinitely large, so the sum mentioned previously will not diverge, so recursive backtracking will be able to stop epidemics for Φ < 1.
For such networks, we expect the observation made for infinitely large scale-free networks to be still be relevant, i.e., the closer a real world network is to an infinitely large scale-free network, the less will the epidemic threshold Φ c be affected by recursion depths past r = 1.
In Figure 2 , we show the reduction of the reproduction number R = R 0 (1 − P r q ) as a function of Φ for different degree distributions and recursion depths. For degree distributions we choose a simple Erdős-Rényi (ER) network with average degree k = 4, a Barabási-Albert (BA) network with average degree k = 4 and a cutoff at κ = 1000, i.e. p(k) = 0 for k > κ, and as a realistic example, a scale-free network with exponential cutoff p(k) ∝ k −2 exp k 94.2 that produces an epidemic threshold comparable to that of urban networks for SARS [45] . We choose the transmissibility T so that all networks have a realistic basic reproduction number for the SARS-CoV-2 virus, R 0 = 3, and we choose Θ = 0.5. We see that the degree distribution only has a minuscule effect on P r q , and that increasing the recursion depth past r = 1, while having the largest effect for ER networks (outer two lines in the inset), still barely decreases the critical value Φ c . We can also calculate the critical value Φ c as a function of the symptomatic rate Θ, as is shown in Figure 3 . There is a large visible difference between the classic contract tracing method with r = 0 and recursive contact tracing, even for relatively large values of Θ. While for r > 0 the recursion depth has little influence on Φ c for large values of the symptomatic rate Θ, we see that there is a critical value Θ c , depending on the recursion depth, below which, even with Φ = 1, an epidemic cannot be stopped. This critical value is approximately halved when going from the classical method r = 0 to r = 1, meaning that recursive contact tracing is an effective method to combat diseases with high asymptomatic rates which would not have been able to be stopped by previous contact tracing methods. The critical value Θ c is shown in Figure 4 as a function of the recursion depth for different values of R 0 . The critical value Θ c exponentially decreases with r, with Θ c → 0 for r → ∞. Therefore, any disease with a symptomatic rate Θ > 0 and arbitrarily large basic reproduction number R 0 can be stopped via recursive contact tracing, given a sufficiently large recursion depth and app usage rate. 
To test the accuracy of our calculations in section II, we simulate infection trees with recursive backtracking. The simulation starts with a single infected node, and each time step for each infected, unquarantined leaf node k − 1 downstream nodes are added, with k proportional to kp(k). These new leaf nodes are infected with probability T and symptomatic with probability Θ. Then, according to the rules described in section II, infected leaf nodes may be quarantined, causing them to not receive any downstream nodes. We let these dynamics run for 100 time steps or until there were 10000 new infected leaf nodes added in a time step, at which point we consider the epidemic out of control. In Figure 5 , we show the fraction of trees in which the epidemic is not stopped within 100 time steps, the fraction of quarantined nodes, and the average reproduction number R for trees using an ER degree distribution or a BA degree distribution with a cutoff κ = 1000. We see a very good agreement between our calculation and simulations for recursions r = 1, see Figure 5 . We have also verified that our calculations and simulations agree very well for larger recursion depths.
Next, we move away from the tree structure and use networks instead. In these networks, we start with ten initially infected nodes, which are chosen with a probability proportional to kp(k), and we let the dynamics run until no new nodes are infected within a time step. Figure 6 shows the fraction of infected nodes, the fraction of nodes that have ever been quarantined, and the maximum fraction of nodes that has been quarantined at one point in time for ER networks with different recursion depths. For the network size N → ∞, we see that the fractions of infected and quarantined nodes drop to zero at the theoretical critical value Φ c . For higher recursion depths and relatively small networks, the infected fraction is already kept quite low below the theoretical critical value because a large fraction of nodes is being quarantined and therefore the assumption we made in section II that nodes are not coincidentally swept up in unrelated infection trees does not hold anymore; however, this lower infected fraction comes at the cost of wrongly quarantining a relatively large fraction of nodes. Also, this effect is mitigated for larger network sizes N . For BA networks, especially for large networks, the infection dies out quickly even for low values of Φ, because the infection dynamics are dominated by the strongly connected hub nodes which, after some time, will be in the recovered state, and therefore the effective degree distribution for the infection is quickly cut off for larger k. Additionally, in a BA network the first few nodes which are added to the network and later are likely to grow into the strongest connected nodes are likely to connect to each other and have common neighbors, meaning that the assumption we made in section II of low clustering does not hold, which reduces the number of susceptible nodes adjacent to an infected large spreader i because its neighbors are likely to have already been infected by i's own infecting node. Both these effects lower the basic reproduction number R 0 below the theoretical value given by equation (1) .
Considering the problem of epidemic spreading of an infectious disease with a finite asymptomatic transmission rate, such as the current epidemics caused by the SARS-CoV-2, we have introduced a combined infection model of nodes taking susceptible, infected, or recovered states with a recursive contact tracing algorithm for quarantining, equivalent to an app used by a network's nodes to stop a pandemic in our model. We have calculated the odds of an infected node being quarantined by the contact tracing algorithm, as well as the resulting theoretical critical values for the app usage rate above which an infection does not percolate through the network, and the minimum symptomatic rate beneath which a disease cannot be stopped, depending on the algorithm's recursion depth, the disease's basic reproduction number, and the contact network's underlying degree distribution.
We found that the critical app adoption rate and critical symptomatic rate are both significantly lower for an algorithm using recursive contact tracing, even with a low recursion depth, than for the classically employed, non-recursive method of direct contact tracing. In fact, any disease with a finite symptomatic rate and arbitrary basic reproduction number can be stopped if the app usage rate and recursion depth are large enough, meaning that recursive contact tracing can be an effective method for controlling diseases with large asymptomatic transmission rates which could not have been stopped with previous contact tracing methods. Our critical app adoption rate of over 95% may seem unusually high at first glance compared to some other results [5, 20, 24, 26] , with other estimates generally lying between 56% and 95% [46] ; however, this is simply caused by our model's harsh assumptions, such as a very high basic reproduction number R 0 = 3, a relatively high asymptomatic rate of 50%, no infection prevention measures, such as random testing or social distancing, apart from contact tracing, no distinguishing between the infectivity of symptomatic and asymptomatic disease carriers (symptomatic carriers are often assumed to self-quarantine and therefore infect fewer people), and a lack of manual contact tracing even for symptomatic infected individuals who are not using the app. Our results are comparable to those of other models making harsh assumptions [14, 16, 23] .
Further, we found that, while higher recursion depths can stop diseases with a high asymptomatic rate, for low asymptomatic rates, recursion depths higher than one show very little improvement in the critical app usage rate while falsely quarantining more uninfected nodes, implying that for such diseases recursion depths larger than one are mostly not useful. Also, the contact network's degree distribution was shown to have little impact on these critical values, so recursive contact tracing is not only viable for Erdős-Rényi graphs, as tested in previous studies, but also for more realistic scale-free-like networks, i.e. scale-free networks with a cutoff. We have ensured the accuracy of our theoretical calculations using simulations on infection trees and networks with different degree distributions. We found very good agreement between our calculations and simulations for any degree distribution on infection trees and for Erdős-Rényi networks. For Barabási-Albert networks, the simulation's critical values lay below the calculated ones because quarantining the most connected nodes quickly changes the network's degree distribution and because the effect of clustering, as highly connected nodes in Barabási-Albert networks are likely to be connected to each other, was not considered in the calculations.
The calculations presented here are viable for a simple model, but we believe that the qualitative conclusions should be applicable to the real world as well. Future research should expand this simple model to be more realistic and possibly fit the infection profiles of real diseases, as well as consider the effect of clustering on the model's critical values.