In applications of group testing in networks, e.g. identifying individuals who are infected by a disease spread over a network, exploiting correlation among network nodes provides fundamental opportunities in reducing the number of tests needed. We model and analyze group testing on $n$ correlated nodes whose interactions are specified by a graph $G$. We model correlation through an edge-faulty random graph formed from $G$ in which each edge is dropped with probability $1-r$, and all nodes in the same component have the same state. We consider three classes of graphs: cycles and trees, $d$-regular graphs and stochastic block models or SBM, and obtain lower and upper bounds on the number of tests needed to identify the defective nodes. Our results are expressed in terms of the number of tests needed when the nodes are independent and they are in terms of $n$, $r$, and the target error. In particular, we quantify the fundamental improvements that exploiting correlation offers by the ratio between the total number of nodes $n$ and the equivalent number of independent nodes in a classic group testing algorithm. The lower bounds are derived by illustrating a strong dependence of the number of tests needed on the expected number of components. In this regard, we establish a new approximation for the distribution of component sizes in "$d$-regular trees" which may be of independent interest and leads to a lower bound on the expected number of components in $d$-regular graphs. The upper bounds are found by forming dense subgraphs in which nodes are more likely to be in the same state. When $G$ is a cycle or tree, we show an improvement by a factor of $log(1/r)$. For grid, a graph with almost $2n$ edges, the improvement is by a factor of ${(1-r) \log(1/r)}$, indicating drastic improvement compared to trees. When $G$ has a larger number of edges, as in SBM, the improvement can scale in $n$.
翻译:在网络中进行组测试验的应用(例如,识别由网络传播的疾病感染的个体)中,利用网络节点之间的相关性提供了基本的机会,以减少需要的测试次数。我们对 $n$ 个相关节点进行了群测试验建模和分析,这些节点之间的交互由图 $G$ 指定。我们通过在 $G$ 中生成故障边随机图来建模相关性,其中每条边以概率 $1-r$ 被删除,并且所有处于同一组件中的节点具有相同的状态。我们考虑三类图形:环和树、$d$-正则图和随机块模型(SBM),并获得了用于识别有缺陷节点所需的测试次数的下限和上限。我们的结果是针对节点独立时所需测试次数的 $n$、$r$ 和目标误差的函数。特别是,通过在经典群测试验算法中所有节点的总数 $n$ 和独立节点的等效数量之间的比率来量化利用相关性所提供的基本改进。通过说明测试次数所需的期望组件数量的强依赖关系,我们得出了下限。在这方面,我们建立了新的“$d$-正则树”组件大小分布的近似,这可能是独立的,并导致 $d$-正则图中期望组件数量的下限。我们通过在密集子图中形成节点更可能处于相同状态的算法来找到上限。当 $G$ 是环或树时,我们展示了 $log(1/r)$ 倍的改进。对于网格这样一个具有近 $2n$ 条边的图形,这种改进是 ${ (1-r)\log(1/r)}$ 倍,表明与树相比有极大的改进。当 $G$ 中的边数更多时,如在 SBM 中,该改进可以按比例增加 $n$。