Effectiveness of contact tracing on networks with cliques

Contact tracing, the practice of isolating individuals who have been in contact with infected individuals, is an effective and practical way of containing disease spread. Here we show that this strategy is particularly effective in the presence of social groups: Once the disease enters a group, contact tracing not only cuts direct infection paths but can also pre-emptively quarantine group members such that it will cut indirect spreading routes. We show these results by using a deliberately stylized model that allows us to isolate the effect of contact tracing within the clique structure of the network where the contagion is spreading. This will enable us to derive mean-field approximations and epidemic thresholds to demonstrate the efficiency of contact tracing in social networks with small groups. This analysis shows that contact tracing in networks with groups is more efficient the larger the groups are. We show how these results can be understood by approximating the combination of disease spreading and contact tracing with a complex contagion process where every failed infection attempt will lead to a lower infection probability in the following attempts. Our results illustrate how contact tracing in real-world settings can be more efficient than predicted by models that treat the system as fully mixed or the network structure as locally treelike.

Figure 1

Illustration of $r$-regular $c$-clique network structures. Panels [(a)–(c)] highlight the immediate network vicinity of a focal (red) node within networks formed by 4-, 3-, and 2-cliques, respectively, where each node consistently has a degree of 6. These configurations are representative of the local topology repeated throughout the entire network. Panel (d) provides an example of a 4-regular 3-clique network, with each node having a degree of 4 and being part of two 3-cliques. Displayed are link stubs indicating connections to other nodes, demonstrating the typical local structure one would encounter in an extensive clique-based network. The shaded circular regions signify the proximity to a central node, which is marked in red. This shows the connectivity structure we examine using our $r$-regular clique-type networks.

Figure 2

Diagram of the SIRQ model showing the flow between compartments based on transition probabilities based on the stochastic dynamics introduced in Sec. 2b. Susceptible individuals become infected with probability $p$ and enter quarantine with probability $\alpha$. The $\mathrm{Q}$ compartment includes people in quarantine, either infected or susceptible. Those who are both infected and quarantined move to the ${\mathrm{Q}}_I$ subcompartment, while those who are only quarantined go to the ${\mathrm{Q}}_S$ subcompartment of $\mathrm{Q}$. Figure 3 depicts these two situations. Infected individuals who are not quarantined go to the $\mathrm{I}$ compartment and will recover deterministically in the subsequent time step.

Figure 3

Schematic of contact tracing and spreading without loops (a) and with local loops (b). Infections that would be successful are marked with solid red links, and successful contact tracing with dashed black links. After each exposure, a susceptible node isolates itself with probability $\alpha$ and becomes infected with probability $p$ independently. If no loops are considered, then the combination of infections and contact tracing can be reduced to a single link. There are four possible scenarios: nothing happens; the infection spreads to the neighbor, but contact tracing fails; the infection fails to spread, but contact tracing succeeds; or (a) both infections spread, and the contact tracing succeeds so that the node will be in subcompartment ${\mathrm{Q}}_I$. The last case is where we can benefit from contact tracing cutting indirect spreading paths thanks to the presence of clustering. (b) With local loops, an infection through a common neighbor of both nodes can be avoided. As the quarantine takes place close to the infection, it can prevent the infection from arriving at the neighbor through a local loop as the node is in subcompartment ${\mathrm{Q}}_S$.

Figure 4

Phase transitions from a disease-free equilibrium to an endemic state for 2-, 3-, and 4-clique networks with degree 6 as introduced in Sec. 2a. [(a)–(c)] The outbreak size $E$, normalized to the network size, is shown on the vertical axis for when (a) $\alpha =0$ (no contact tracing), (b) $\alpha =0.25$, and (c) $\alpha =0.5$, from top to bottom respectively. Note that the transition points are shifted slightly to the right for larger clique sizes, $c$, even when there is no contact tracing ($\alpha =0$), but this difference is substantially amplified for larger $\alpha$ values. (d) The coefficient of variation of outbreak sizes in an ensemble, $\chi$ normalized to unity for $\alpha =0.5$. We use $\chi$ to numerically detect the transition point as it peaks at the epidemic threshold. Results are based on Monte Carlo simulations introduced in Sec. 3a2.

Figure 5

Each 3-clique can have four life stages or diffusion patterns with at least one infected node. Section 3a3 considers both recovered and quarantined nodes in the $\mathrm{R}$ compartment. Using a 6-regular 3-clique network, we observe that a $Z_1$ node can form a $Z_2$ motif with two $Z_1$ nodes and a $Z_3$ motif with four $Z_1$ nodes. A $Z_2$ node can also create a $Z_4$ motif with two $Z_1$ nodes. Nodes in the $Z_1$, $Z_2$, and $Z_4$ motifs can transition to an infection-annihilated states such as $\{\mathrm{R},\mathrm{S},\mathrm{S}\}$ which are not shown here. In Sec. 4, we assume that both quarantined and susceptible nodes are in the $\mathrm{S}$ compartment, while only recovered individuals are in the $\mathrm{R}$ compartment.

Figure 6

The impact of contact tracing in clique networks on mitigating epidemic spread: This figure illustrates the decline in the effective reproduction number, $R_e$, with the contact tracing parameter, $\alpha$, across networks with various clique configurations. Specifically, we examine cliques of sizes $c=2,3,4$ with $r=6$ and transmission probability $p=0.5$ in panel (a), and cliques of sizes $c=6,11,16$ when $r=30$ and $p=0.1$ in panel (c). Networks with larger cliques achieve the critical threshold of $R_e=1$ with less contact tracing effort. When $c=2$, the influence of contact tracing on $R_e$ aligns linearly with $\alpha$, according to Eq. (1). In scenarios involving larger cliques, this relationship turns concave and is further intensified as the clique size increases or the transmission probability decreases. The dotted lines are from the mean-field calculations introduced in Sec. 3a3, and the markers are from Monte Carlo simulations described in Sec. 3a2. Panels (b) and (d) show a relative difference of $R_e$ to the linear case when $c=2$ ($R_e^{\mathrm{lin}}$). Figure 13 shows similar results to panel (a) for different $p$ values. The larger the transmission probability, the larger the differences between the curves of other networks with cliques.

Figure 7

Phase diagram showing that increasing the clique size increases the epidemic threshold and effectiveness of contact tracing. (a) The critical curves where $R_e=1$ in the $\alpha p$ plane for $c\in \{2,3,4\}$. The lines indicate the results of the mean-field approximations described in Sec. 3a, and the markers show results for simulations described in Sec. 3a2. The shaded area is the subcritical region for $c=2$ where the infection eventually dies out after a finite number of generations for any clique size. (b) The same phase diagram in $\alpha p_e$ plane, where $p_e=p(1-\alpha )$ is the effective transmission probability defined in Eq. (2). The larger markers in the right end in panel b indicate extreme points from Eq. (4). The inset in panel b shows the relative maximum increase in the effective epidemic threshold for different networks with cliques. Each point in the inset is the ratio of the $p_e$ values at the endpoints of each curve outside the inset, such that $I_c=p_e\left({\alpha }_{\max }\right)/p_e\left({\alpha }_{\min }\right)$.

Figure 8

Critical curves rescaled as effective branching factors for treelike networks $(r-1)p_e$. Panel (a) is the same as panel Fig. 7, but on the vertical axis, the effective transmission probabilities are multiplied by the excess degree. Further, results are shown for a larger network where $r=12$. The red curves marked with stars are for the case that there $c=2$ and the network is treelike, therefore Eq. (1) holds such that $R_e=p_e\overline{d}=p_e(r-1)=1$ for any $\alpha$ value. For $c>2$, this equation does not hold. The right end markers on panel a indicate extreme points from Eq. (5). The inset shows the relative maximum increase in the effective epidemic threshold for different networks with cliques. Each point in the inset is the ratio of the $p_e$ values at the endpoints of each curve outside the inset, such that $I_c=p_e\left({\alpha }_{\max }\right)/p_e\left({\alpha }_{\min }\right)$. (b) This panel shows how $(1-r)p_e$ changes when we have networks with different degrees, $r=6$ to $r=18$, and maximal connectivity-preserving clique size (i.e., when $n_c=2$).

Figure 9

Spreading process in a 6-regular 3-clique network under the extreme case of $p=1$, where the infection propagates severely through the cliques. In this scenario, (a) an active node (infected but not in quarantine) can transmit the disease to other nodes in its adjacent cliques, (b) resulting in new infections. The number of new infections caused by an active node is not equal to the total number of members in the cliques that the node belongs to, which is $n_c(c-1)$, but rather the number of members in the cliques attached to that node, excluding the clique that infection is coming from, which is $(n_c-1)(c-1)=2\times 2$. For further details on the network structure and spreading dynamics, refer to Secs. 2a and 2b.

Figure 10

Outbreak size in the subcritical regime as a function of $p$ across the three network structures while considering the influence of isolation probability, $\alpha$. Nine curves are grouped into three sets (from left to right) according to their isolation probabilities, with each set containing three curves with $\alpha =0.0,\alpha =0.25,$ and $\alpha =0.5$. These groupings demonstrate the influence of $\alpha$ on outbreak size in the subcritical regime. Increasing $\alpha$ or clique size reduces the outbreak size, as calculated by Eq. (7) and Eq. (8) using the next-generation matrix from mean-field approximation found in Sec. 3b. Markers represent the results of $50000$ simulations, while dotted lines depict the results of the mean-field calculations presented in Sec. 3a2.

Figure 11

Comparison of the mean-field approximation introduced in section Sec. 2b with the complex contagion approximation of Sec. 4. Panels are similar to the panels of Fig. 7. Here, markers are the results of the simulations described in Sec. 3a2. Our simulation results align with the bold curves, which are the results of the mean-field approximations of Sec. 3a. The thin curves result from the complex contagion approximation introduced in Sec. 4, which deviates slightly more from the other mean-field approximation when $\alpha$ increases. The complex contagion approximation gives the lower bound of critical transmission probability for all values of $\alpha$.

Figure 12

Outbreak size in the subcritical regime as a function of $p$ across the three network structures while considering the influence of isolation probability $\alpha$. Nine curves are grouped into three sets (from left to right) according to their isolation probabilities, with each set containing $\alpha =0,\alpha =0.25,$ and $\alpha =0.5$. These groupings demonstrate the influence of $\alpha$ on outbreak size in the subcritical regime. Increasing $\alpha$ or clique size reduces the outbreak size, as calculated by Eq. (7) and Eq. (8) using the next-generation matrix from mean-field approximation found in Sec. 4. Markers represent the results of $50000$ simulations, while dotted lines depict the results of the mean-field calculations presented in Sec. 3b.

Figure 13

How contact tracing on clique network reduces the effective reproduction number $R_e$ by increasing $\alpha$. Effective reproduction number for different networks with cliques with $r=6$ for transmission probabilities (a) $p=1.0$, (b) $p=0.75$, and (c) $p=0.5$. The dotted lines are from the mean-filed calculations introduced in Sec. 3a, and the markers are from Monte Carlo simulations described in Sec. 3a2. The yellow dashed lines, which overlap with the red curves with stars, represent Eq. (1), which match the cases where $c=2$ (treelike networks). The larger the transmission probability, the larger the differences between the curves of different networks with cliques. The larger the clique size, the less effort we need to quarantine people since networks with larger cliques reach $R_e=1$ for lower values of $\alpha$.

Figure 14

Number of motifs and the number of nonzero elements of $\mathbf{M}$ for given clique size $c$.

Figure 15

Schematic of the impact of the short-time quarantine. We track the number of susceptible, infected, and recovered nodes for the three main cliques we consider. we can note that the first instance where a previously quarantined susceptible node can meet an infected node appears in the 4-clique.

Figure 16

Differences in the critical regions obtained from the largest eigenvalues of the mean matrix for the original quarantine time (labeled Q) and the short quarantine time (labeled SQ). Inset shows a subset of parameter values from which the difference between the two quarantine times is more apparent.

Figure 17

Phase transitions from a disease-free equilibrium to an endemic state for 2-, 3-, and 4-clique networks with degree 6 as introduced in Sec. 2a. Nodes in quarantine can leave the $\mathrm{Q}$ compartment at every time step with probability ${\alpha }^{\prime }=0.4$. [(a)–(c)] The outbreak size $E$, normalized to the network size, is shown on the vertical axis for when (a) $\alpha =0$ (no contact tracing), (b) $\alpha =0.25$, and (c) $\alpha =0.5$, from top to bottom respectively. Note that the transition points are shifted slightly to the right for larger clique sizes, $c$, even when there is no contact tracing ($\alpha =0$), but this difference is substantially amplified for larger $\alpha$ values. Results are based on Monte Carlo simulations introduced in Sec. 3a2 and Appendix pp5.

Figure 18

Life stages or diffusion patterns of a 4-clique. Similar to Fig. 5 for a 3-clique. We can generate the next-generation matrix for any clique size with our code introduced in Appendix pp4.