GROUP TESTING IN STRUCTURED AND DYNAMIC NETWORKS

Abstract

We consider efficient infection identification algorithms based on group testing under the structured disease spread network and dynamically evolving disease spread network assumptions. Group testing is an efficient infection identification approach based on the idea of pooling the test samples. Group testing has been widely studied in various areas, such as screening and biology, communications, networks, data science, and information theory. In this dissertation, we study group testing applications over structured and dynamic networks, such as random graph-governed correlated connections of nodes and dynamically evolving network topologies under discrete time. First, we propose a novel infection spread model based on a random graph representing connections between $n$ individuals. The infection spreads via connections between individuals, resulting in a probabilistic cluster formation structure as well as non-i.i.d.~(correlated) infection statuses for individuals. We propose a class of \emph{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 \emph{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 exponentially split cluster formation trees, for zero-error construction, we prove that the required number of tests is $O(\log_2n)$. 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 the infection rate is high, contrasting the prevalent belief that group testing is useful only when the infection rate is low. Next, we study a dynamic infection spread model inspired by the discrete time SIR (susceptible-infected-recovered) model, where infections are spread via non-isolated infected individuals; while infection keeps spreading over time, limited capacity testing is performed at each time instant as well. In contrast to the classical, static group testing problem, the objective in our setup is not to find the minimum number of required tests to identify the infection status of every individual in the population but to \emph{control} the infection spread by detecting and isolating the infections over time by using the given, limited number of tests. To analyze the performance of the proposed algorithms, we focus on the average-case analysis of the number of individuals that remain non-infected throughout the process of controlling the infection. We propose two dynamic algorithms that both use a given limited number of tests to identify and isolate the infections over time while the infection spreads. The first algorithm is a dynamic randomized individual testing algorithm; in the second algorithm, we employ the group testing approach similar to the original work of Dorfman. By considering weak versions of our algorithms, we obtain lower bounds for the performance of our algorithms. Finally, we implement our algorithms and run simulations to gather numerical results and compare our algorithms and theoretical approximation results under different sets of system parameters. Finally, we consider the dynamic infection spread model based on the discrete SIR model, which assumes the disease to be spread over time via infected and non-isolated individuals. In our system, the main objective is not to minimize the number of required tests to identify every infection but instead to utilize the available, given testing capacity $T$ at each time instant to efficiently control the infection spread. We introduce and study a novel performance metric, which we coin as $\epsilon$-disease control time. This metric can be used to measure how fast a given algorithm can control the spread of a disease. We characterize the performance of the dynamic individual testing algorithm and introduce a novel dynamic SAFFRON-based group testing algorithm. We present theoretical results and implement the proposed algorithms to compare their performances.