Algorithms for massive multi-hop contact tracing

In the proposed algorithm we directly use the concept of infectious path in order to estimate how many individuals among the population in our model are infectious at day d. Intuitively, these infectious paths represent how the pandemic is spreading through the population and we will exploit this concept of infectious paths to determine which node is infectious at day d. In order to accomplish this task, we define the concept of infectious bubble. To have a better understanding on the theorical definition of the infectious bubble, we introduce three examples in Figure 8 on temporal graph G that use infectious path to define the infectious bubbles.

Example 1, as in Figure 8(a): let u be a node which has tested positive at day d. Therefore we can say that u is red at time t ∈ d. If u has a contact with node v at time t′ with t < t′, then with probability λ node v contracts the disease at time t′. In this case, starting from time t′ node v can infect other nodes through further contacts. In this case we say that node v has node u inside its infectious bubble of radius h = 1, since there exists an infectious path starting from node u to node v at time t′ of length h = 1. Hence we say that u is a direct infectious contact for v.

Example 2, as in Figure 8(b): let instead u be a node that has been tested negative at day d. Therefore we can say that u remains green until it has a contact with another non-green node at time t′ with tstart < t′ and tstart being the initial time instant of day d. If u has a contact with node v at time t′′ with tstart < t′′, independently from the nature of v, there is no way that v contracts the disease from u if u was still green at time t′′. In this case we say that node v does not have node u inside its infectious bubble of radius h = 1, since there is no infectious path from node u to node v. Due to the fact that green nodes do not spread the disease, they do not count for infectious paths.

Example 3, as in Figure 8(c): let u be a node that has been tested positive at day d. Therefore we can say that u is red at time t ∈ d. Then let v and w be two other nodes in G. If u has a contact with node v at time t′ with t < t′, then with probability λ node v contracts the disease at time t′. Later, v has a contact with w at time t′′ with t′ < t′′. Let’s assume v shows no symptoms related to the disease at t′′. In this peculiar case v is not red nor green at time t′′ when it enters in contact with w. Due to v not showing any symptoms at time t′′ where v and w had an interaction, w is unsure whether a test for positivity to the disease is necessary. In fact, at t′′ node v could have been infectious but asymptomatic or not infectious at all. In the first case, w is a potential infectious node, and every contact it has with other nodes at time t′′′ with t′′ < t′′′ could result in a further spread of the disease. In this case we say that node w has node u inside its infectious bubble of radius h = 2, since there exists an infectious path made up of two temporal edges, the first starting from u to v at time t′ and the second one starting from v to w at time t′′, of length h = 2. Hence we say that u is an indirect infectious contact for w. [...]