Network-Informed Constrained Divisive Pooled Testing Assignments

Abstract

Frequent universal testing in a finite population is an effective approach to preventing large infectious disease outbreaks. Yet when the target group has many constituents, this strategy can be cost prohibitive. One approach to alleviate the resource burden is to group multiple individual tests into one unit in order to determine if further tests at the individual level are necessary. This approach, referred to as a group testing or pooled testing, has received much attention in finding the minimum cost pooling strategy. Existing approaches, however, assume either independence or very simple dependence structures between individuals. This assumption ignores the fact that in the context of infectious diseases there is an underlying transmission network that connects individuals. We develop a constrained divisive hierarchical clustering algorithm that assigns individuals to pools based on the contact patterns between individuals. In a simulation study based on real networks, we show the benefits of using our proposed approach compared to random assignments even when the network is imperfectly measured and there is a high degree of missingness in the data.

Keywords: divisive clustering; epidemiology; group testing; infectious disease; network analysis.

Figure 1

Values of the objective function Q(Z) (vertical axis) vs. the pool size K (horizontal axis) for (A) AH495, (B) AH2587, and (C) ERGM10000. Values of Q are given using Algorithm 1 based on the Laplacian eigenvectors, Algorithm 2 based on geodesic distances, and using random pool assignments.

Figure 2

Results from introducing missingness into the (A) AH495, (B) AH2587, or (C) ERGM10000 network by simulating two common network survey tools and varying the level of non-response. The horizontal axis corresponds to Q(Z), and vertical lines show either the average of 50 random pool assignments or results based on the true underlying network.