Sparsity-Constrained Community-Based Group Testing

2024/03/19 by Sarthak Jain, Jain, Sarthak, Martina Cardone +3
Computer Science · Medicine · #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning and Algorithms #SARS-CoV-2 detection and testing

paper · pdf · doi:10.48550/arxiv.2403.12419

openalex publication_date 2024/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this work, we consider the sparsity-constrained community-based group testing problem, where the population follows a community structure. In particular, the community consists of F families, each with M members. A number k_f out of the F families are infected, and a family is said to be infected if k_m out of its M members are infected. Furthermore, the sparsity constraint allows at most ρ_T individuals to be grouped in each test. For this sparsity-constrained community model, we propose a probabilistic group testing algorithm that can identify the infected population with a vanishing probability of error and we provide an upper-bound on the number of tests. When k_m = Θ(M) and M ≫ log(FM), our bound outperforms the existing sparsity-constrained group testing results trivially applied to the community model. If the sparsity constraint is relaxed, our achievable bound reduces to existing bounds for community-based group testing. Moreover, our scheme can also be applied to the classical dilution model, where it outperforms existing noise-level-independent schemes in the literature.

Related

• Community aware group testing
• Group testing for overlapping communities
• Adaptive Group Testing on Networks with Community Structure: The Stochastic Block Model
• Near optimal sparsity-constrained group testing: improved bounds and algorithms
• Group Testing with Non-identical Infection Probabilities