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$。

0
下载
关闭预览

相关内容

Graph Transformer近期进展
专知会员服务
61+阅读 · 2023年1月5日
【AAAI2023】图序注意力网络
专知会员服务
45+阅读 · 2022年11月24日
专知会员服务
50+阅读 · 2021年5月19日
Neural Eigenmap: 基于谱学习的结构化表示学习
PaperWeekly
1+阅读 · 2022年11月29日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
26+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
12+阅读 · 2022年11月21日
Arxiv
22+阅读 · 2022年3月31日
Arxiv
56+阅读 · 2021年5月3日
Arxiv
13+阅读 · 2019年11月14日
VIP会员
相关资讯
Neural Eigenmap: 基于谱学习的结构化表示学习
PaperWeekly
1+阅读 · 2022年11月29日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
26+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员