2021/01/14 by Batuhan Arasli, Şennur Ulukuş, Arasli, Batuhan +1
Environmental Science · Immunology and Microbiology · Medicine · #Bacteriophages and microbial interactions #Computers and Society (cs.CY) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Electrical engineering #HIV Research and Treatment #Information Theory (cs.IT) #Networking and Internet Architecture (cs.NI) #SARS-CoV-2 detection and testing #Signal Processing (eess.SP) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2101.05792
openalex publication_date 2021/01/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose a novel infection spread model based on a random connection graph which represents connections between n individuals. Infection spreads via connections between individuals and this results in a probabilistic cluster formation structure as well as a non-i.i.d. (correlated) infection status for individuals. We propose a class of two-step sampled group testing algorithms where we exploit the known probabilistic infection spread model. We investigate the metrics associated with two-step sampled group testing algorithms. To demonstrate our results, for analytically tractable exponentially split cluster formation trees, we calculate the required number of tests and the expected number of false classifications in terms of the system parameters, and identify the trade-off between them. For such exponentially split cluster formation trees, for zero-error construction, we prove that the required number of tests is O(log2n). Thus, for such cluster formation trees, our algorithm outperforms any zero-error non-adaptive group test, binary splitting algorithm, and Hwang's generalized binary splitting algorithm. Our results imply that, by exploiting probabilistic information on the connections of individuals, group testing can be used to reduce the number of required tests significantly even when infection rate is high, contrasting the prevalent belief that group testing is useful only when infection rate is low.