エッジ故障グラフの下での相関によるグループ試験【JST・京大機械翻訳】

Nikpey Hesam; Kim Jungyeol; Chen Xingran; Sarkar Saswati; Bidokhti Shirin Saeedi

プレプリント

J-GLOBAL ID：202202206992668190 整理番号：22P0285079

エッジ故障グラフの下での相関によるグループ試験【JST・京大機械翻訳】

Group Testing with Correlation under Edge-Faulty Graphs

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (5件)： , , , ,
資料名：
発行年： 2022年02月04日プレプリントサーバーでの情報更新日： 2023年03月20日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

ネットワークにおけるグループ試験の応用において,例えばネットワーク上の病気拡散によって感染する個体の同定,ネットワークノード間の相関を利用することは,必要なテストの数を減らす基本的機会を提供した。相互作用がグラフGによって指定されるn相関ノードに関するグループ試験をモデル化して解析した。各エッジが確率1rで落下するGから形成されるエッジ故障ランダムグラフを通して相関をモデル化し,同じコンポーネントのすべてのノードは同じ状態を持つ。3種類のグラフ,すなわちサイクルとツリー,d正規グラフと確率的ブロックモデルまたはSBMを考察し,欠陥ノードを同定するために必要な試験の数に関して下限と上限を得た。結果は,ノードが独立で,n,r,およびターゲット誤差の項にあるときに必要な試験の数に関して表現される。特に,古典的グループテストアルゴリズムにおけるノードnの総数と独立ノードの等価数の間の比率によって提供される相関を利用する基本的改良を定量化した。より低い限界は,成分の予想数に必要な試験の数の強い依存性を示すことによって導かれる。この点に関して,著者らは,独立の興味の可能性がある”d-正規木”における成分サイズの分布のための新しい近似を確立し,d-正規グラフにおける成分の予想数に対する下限を導いた。上界は,ノードが同一状態にある可能性が高い高密度部分グラフを形成することによって見つかる。Gがサイクルまたはツリーであるとき,著者らはlog(1/r)の因子によって改良を示した。グリッドでは,ほぼ2nのエッジを持つグラフ,改善は(1-r)log(1/r)の因子で,樹木と比較して劇的な改善を示す。GがSBMのように多数のエッジを持つとき,改良はnでスケールできる。【JST・京大機械翻訳】

, , , , , , ,
, , , , , 【Automatic Indexing@JST】

グラフ理論基礎 , ネットワーク法 , その他のディジタル計算機方式

, , , ,

前のページに戻る