論文の概要: Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks

• arxiv url: http://arxiv.org/abs/2202.08296v1
• Date: Wed, 16 Feb 2022 19:03:45 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-18 16:41:47.932646
• Title: Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks
• Title（参考訳）: 確率的拡散モデルを用いたネットワーク上のエピデミックスプレッドの制御
• Authors: Amy Babay, Michael Dinitz, Aravind Srinivasan, Leonidas Tsepenekas, Anil Vullikanti
• Abstract要約: 我々はMinINFに対する2つのビクリテリア近似アルゴリズムを提案し、この問題に対する最初の非自明な近似を与える。 1つ目は、Kager citekarger:mathor99の切断されたスペーサー化結果に基づいており、送信確率があまり小さくない場合に機能する。 2つ目はサンプル平均近似(SAA)に基づくアルゴリズムで、Chung-Luランダムグラフモデルについて解析する。
• 参考スコア（独自算出の注目度）: 20.24727293398521
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The spread of an epidemic is often modeled by an SIR random process on a social network graph. The MinINF problem for optimal social distancing involves minimizing the expected number of infections, when we are allowed to break at most $B$ edges; similarly the MinINFNode problem involves removing at most $B$ vertices. These are fundamental problems in epidemiology and network science. While a number of heuristics have been considered, the complexity of these problems remains generally open. In this paper, we present two bicriteria approximation algorithms for MinINF, which give the first non-trivial approximations for this problem. The first is based on the cut sparsification result of Karger \cite{karger:mathor99}, and works when the transmission probabilities are not too small. The second is a Sample Average Approximation (SAA) based algorithm, which we analyze for the Chung-Lu random graph model. We also extend some of our results to tackle the MinINFNode problem.
• Abstract（参考訳）: 流行の拡散は、しばしばソーシャルネットワークグラフ上のSIRランダムプロセスによってモデル化される。 最適なソーシャルディスタンシングのためのmininf問題は、最大でb$エッジでブレークすることを許された場合、期待される感染数を最小化することであり、同様にmininfnodeの問題は、最大$b$頂点を取り除くことである。 これらは疫学とネットワーク科学の根本的な問題である。 多くのヒューリスティックが検討されているが、これらの問題の複雑さは一般には未解決である。 本稿では,この問題に対する最初の非自明な近似を与えるmininfの2つのbicriteria近似アルゴリズムを提案する。 1つ目は、Karger \cite{karger:mathor99} のカットスカラー化結果に基づいており、送信確率が小さすぎると機能する。 2つ目はサンプル平均近似(SAA)に基づくアルゴリズムで、Chung-Luランダムグラフモデルについて解析する。 MinINFNode問題に取り組むために、いくつかの結果も拡張しています。

関連論文リスト

• Learning general Gaussian mixtures with efficient score matching [16.06356123715737]
  我々は、$d$次元で$k$ガウシアンの混合を学習する問題を研究する。 我々は、下層の混合成分について分離を前提としない。 我々は、ターゲット混合物から$dmathrmpoly(k/varepsilon)$サンプルを抽出し、サンプル-ポリノミカル時間で実行し、サンプリング器を構築するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-29T17:30:36Z)
• Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
  勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。 次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
  論文  参考訳（メタデータ） (2024-04-18T17:57:53Z)
• Semantic Strengthening of Neuro-Symbolic Learning [85.6195120593625]
  ニューロシンボリックアプローチは一般に確率論的目的のファジィ近似を利用する。 トラクタブル回路において,これを効率的に計算する方法を示す。 我々は,Warcraftにおける最小コストパスの予測,最小コスト完全マッチングの予測,スドクパズルの解法という3つの課題に対して,アプローチを検証した。
  論文  参考訳（メタデータ） (2023-02-28T00:04:22Z)
• Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
  ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。 本稿では,2種類のミニマックスアルゴリズムを提案する。 そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
  論文  参考訳（メタデータ） (2023-02-08T01:42:45Z)
• Finite Sample Identification of Wide Shallow Neural Networks with Biases [12.622813055808411]
  入力-出力対の有限標本からネットワークのパラメータを同定することは、しばしばエンプテラー-学生モデル(enmphteacher-student model)と呼ばれる。 本稿では,このような幅の広い浅層ネットワークに対して,構成的手法と有限標本同定の理論的保証を提供することにより,そのギャップを埋める。
  論文  参考訳（メタデータ） (2022-11-08T22:10:32Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Causal Inference Despite Limited Global Confounding via Mixture Models [4.721845865189578]
  そのようなモデルの有限$k$-mixtureは、図式的により大きなグラフで表される。 空でないDAGの混合を学習するための最初のアルゴリズムを与える。
  論文  参考訳（メタデータ） (2021-12-22T01:04:50Z)
• Distributed Sparse Regression via Penalization [5.990069843501885]
  エージェントのネットワーク上の線形回帰を、(集中ノードを持たない)無向グラフとしてモデル化する。 推定問題は、局所的なLASSO損失関数の和とコンセンサス制約の2次ペナルティの最小化として定式化される。 本稿では, ペナル化問題に適用した近似勾配アルゴリズムが, 集中的な統計的誤差の順序の許容値まで線形に収束することを示す。
  論文  参考訳（メタデータ） (2021-11-12T01:51:50Z)
• Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
  現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。 ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。 本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-06T19:08:53Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。