東華大學圖書館 |

Group Testing in Structured and Dynamic Networks.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Group Testing in Structured and Dynamic Networks./
作者:	Arasli, Batuhan.
出版者:	Ann Arbor : ProQuest Dissertations & Theses, : 2023,
面頁冊數:	145 p.
附註:	Source: Dissertations Abstracts International, Volume: 84-12, Section: B.
Contained By:	Dissertations Abstracts International84-12B.
標題:	Electrical engineering. -
電子資源:	https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30247782
ISBN:	9798379754372

Group Testing in Structured and Dynamic Networks.
Arasli, Batuhan.

Group Testing in Structured and Dynamic Networks. - Ann Arbor : ProQuest Dissertations & Theses, 2023 - 145 p.

Source: Dissertations Abstracts International, Volume: 84-12, Section: B.

Thesis (Ph.D.)--University of Maryland, College Park, 2023.

This item must not be sold to any third party vendors.

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 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 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 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 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 ε-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.

ISBN: 9798379754372Subjects--Topical Terms:

649834
Electrical engineering.
Subjects--Index Terms:

Disease spread modeling

Group Testing in Structured and Dynamic Networks.
LDR:05606nmm a2200385 4500 001 2393601
005 20240414211449.5
006 m o d
007 cr#unu||||||||
008 251215s2023 ||||||||||||||||| ||eng d
020 $a 9798379754372
035 $a (MiAaPQ)AAI30247782
035 $a AAI30247782
040 $a MiAaPQ $c MiAaPQ
100 1 $a Arasli, Batuhan. $0 (orcid)0000-0002-5310-3834 $3 3763072
245 1 0 $a Group Testing in Structured and Dynamic Networks.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2023
300 $a 145 p.
500 $a Source: Dissertations Abstracts International, Volume: 84-12, Section: B.
500 $a Advisor: Ulukus, Sennur.
502 $a Thesis (Ph.D.)--University of Maryland, College Park, 2023.
506 $a This item must not be sold to any third party vendors.
520 $a 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 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 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 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 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 ε-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.
590 $a School code: 0117.
650 4 $a Electrical engineering. $3 649834
650 4 $a Biostatistics. $3 1002712
650 4 $a Health care management. $3 2122906
653 $a Disease spread modeling
653 $a Dynamic networks
653 $a Group testing
653 $a Pooled testing
690 $a 0544
690 $a 0769
690 $a 0308
710 2 $a University of Maryland, College Park. $b Electrical Engineering. $3 1018746
773 0 $t Dissertations Abstracts International $g 84-12B.
790 $a 0117
791 $a Ph.D.
792 $a 2023
793 $a English
856 4 0 $u https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30247782