Adaptive group testing strategy for infectious diseases using social contact graph partitions

Abstract

Mass testing is essential for identifying infected individuals during an epidemic and allowing healthy individuals to return to normal social activities. However, testing capacity is often insufficient to meet global health needs, especially during newly emerging epidemics. Dorfman's method, a classic group testing technique, helps reduce the number of tests required by pooling the samples of multiple individuals into a single sample for analysis. Dorfman's method does not consider the time dynamics or limits on testing capacity involved in infection detection, and it assumes that individuals are infected independently, ignoring community correlations. To address these limitations, we present an adaptive group testing (AGT) strategy based on graph partitioning, which divides a physical contact network into subgraphs (groups of individuals) and assigns testing priorities based on the social contact characteristics of each subgraph. Our AGT aims to maximize the number of infected individuals detected and minimize the number of tests required. After each testing round (perhaps on a daily basis), the testing priority is increased for each neighboring group of known infected individuals. We also present an enhanced infectious disease transmission model that simulates the dynamic spread of a pathogen and evaluate our AGT strategy using the simulation results. When applied to 13 social contact networks, AGT demonstrates significant performance improvements compared to Dorfman's method and its variations. Our AGT strategy requires fewer tests overall, reduces disease spread, and retains robustness under changes in group size, testing capacity, and other parameters. Testing plays a crucial role in containing and mitigating pandemics by identifying infected individuals and helping to prevent further transmission in families and communities. By identifying infected individuals and helping to prevent further transmission in families and communities, our AGT strategy can have significant implications for public health, providing guidance for policymakers trying to balance economic activity with the need to manage the spread of infection.

Figure 1

A demonstration of social contact network partition.

Figure 2

(A) The two-stage testing design that is adapted from Dorfman’s method. (B) Adjusting the testing order according to previous testing results, the point prevalence, and the topological connectivity of each group.

Figure 3

Algorithm for dividing the vertices of the given undirected graph into k sets while maximizing the number of edges within each set.

Figure 4

Algorithm for adjusting the testing priority of groups adaptively based on the point prevalence and previous test results.

Figure 5

The adaptive testing strategy, given as a processing cycle over time.

Figure 6

(A) Agent based Infectious disease transmission model. (B) The exponential distribution for modeling the infectious heterogeneity. (C) Distinct periods of the enhanced SEIR model.

Figure 7

Simulation results of our strategies and baselines using six network generation models. The total population is 1000. AGT outperforms all competing strategies in protecting more susceptible individuals, reducing outbreak size, and reducing secondary transmissions.

Figure 8

Simulation results of our strategies and baselines on the Chung-Lu network model (CL). The total population is 1000. The left figure reports the number of infected individuals per day. The right figure shows the number of uninfected individuals per day. The shaded region around each line is the corresponding 95% confidence interval. AGT steadily reduces the number of infections, decreases the outbreak size, and protects more susceptible individuals.

Figure 9

Effectiveness of AGT and baselines on the CL network with varying transmission settings. AGT demonstrates a higher percentage of uninfected individuals and a lower total number of tests, indicating its effectiveness in minimizing infections while optimizing testing resources. The performance in controlling secondary infections remains stable, and the maximum outbreak size can be effectively controlled to the initial outbreak size (5) within a $\lambda$ range of 6–14. Additionally, AGT exhibits superior performance at higher transmission rates, achieving better control of outbreaks with lower resource consumption.

Figure 10

Testing performance for varying testing capacities on different network models. The larger test capacity provides better performance in all measurements. The differences are not significant after it exceeds 15%.

Figure 11

Testing performance for different network models based on varying group sizes. The optimal group size is not consistent for different network structures. Smaller groups perform better on lowering the outbreak size than larger ones, while larger group size can save more testing resources.

Figure 12

Simulation results of our strategies and baselines using seven real contact networks. Group testing strategies (Strategy 2, 3, 4, and its variation) outperform Individual Testing (IT) (Strategy 1), saving 76.08–88.41% of testing resources. However, the difference among different group testing strategies is insignificant. Notably, the variant designed for high-density networks shows significant reduction only on the SFHH network.

Figure 13

Simulation results of our strategies and baselines based on varying population scales. The initial outbreak size is set at 1% of each population, and the test capacity is set at 15% of the corresponding population. Our proposed strategy outperforms the other strategies in terms of reducing the total number of tests and outbreak size.