論文の概要: Multiple Node Immunisation for Preventing Epidemics on Networks by Exact
Multiobjective Optimisation of Cost and Shield-Value
- arxiv url: http://arxiv.org/abs/2010.06488v1
- Date: Tue, 13 Oct 2020 15:49:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-08 00:41:40.151836
- Title: Multiple Node Immunisation for Preventing Epidemics on Networks by Exact
Multiobjective Optimisation of Cost and Shield-Value
- Title（参考訳）: コストとシールド値の多目的最適化によるネットワーク上のエピデミクス防止のための複数ノード免疫
- Authors: Michael Emmerich, Joost Nibbeling, Marios Kefalas, Aske Plaat
- Abstract要約: 本稿では,複数のノードを選択して削除する問題に対処する。
複数ノード選択に関するこれまでの作業と比較すると、コストと利益の間のトレードオフが考慮されている。
この論文の主な貢献は、もし時間が許せば、正確で問題固有の手法が使われるべきであるという洞察である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The general problem in this paper is vertex (node) subset selection with the
goal to contain an infection that spreads in a network. Instead of selecting
the single most important node, this paper deals with the problem of selecting
multiple nodes for removal. As compared to previous work on multiple-node
selection, the trade-off between cost and benefit is considered. The benefit is
measured in terms of increasing the epidemic threshold which is a measure of
how difficult it is for an infection to spread in a network. The cost is
measured in terms of the number and size of nodes to be removed or controlled.
Already in its single-objective instance with a fixed number of $k$ nodes to be
removed, the multiple vertex immunisation problems have been proven to be
NP-hard. Several heuristics have been developed to approximate the problem. In
this work, we compare meta-heuristic techniques with exact methods on the
Shield-value, which is a sub-modular proxy for the maximal eigenvalue and used
in the current state-of-the-art greedy node-removal strategies. We generalise
it to the multi-objective case and replace the greedy algorithm by a quadratic
program (QP), which then can be solved with exact QP solvers. The main
contribution of this paper is the insight that, if time permits, exact and
problem-specific methods approximation should be used, which are often far
better than Pareto front approximations obtained by general meta-heuristics.
Based on these, it will be more effective to develop strategies for controlling
real-world networks when the goal is to prevent or contain epidemic outbreaks.
This paper is supported by ready to use Python implementation of the
optimization methods and datasets.
- Abstract（参考訳）: 本論文の一般的な問題は,ネットワーク上に広がる感染を抑えるために,頂点(ノード)サブセットを選択することである。
本稿では,1つの重要なノードを選択する代わりに,複数のノードを選択して削除する問題を扱う。
複数ノード選択に関する以前の作業と比較すると、コストと利益のトレードオフが考慮される。
この効果は、感染がネットワークに広がるのがどれほど難しいかの尺度である、流行の閾値を増加させることによって測定される。
コストは、削除または制御されるノードの数とサイズによって測定される。
固定数の$k$ノードを持つ単一目的のインスタンスでは、複数の頂点免疫問題はNPハードであることが既に証明されている。
この問題を近似するためにいくつかのヒューリスティックが開発された。
本研究ではメタヒューリスティック手法を,最大固有値のサブモジュラープロキシであるShield-valueの正確な手法と比較し,現在最先端のノード除去戦略で使用されている。
我々はこれを多目的の場合に一般化し, greedyアルゴリズムを二次プログラム (qp) で置き換える。
この論文の主な貢献は、時間が許せば、厳密で問題特異的な近似が使われるべきであるという洞察であり、一般的なメタヒューリスティックスによって得られるパレートフロント近似よりもはるかに良いものであることが多い。
これらのことから、感染予防や感染拡大防止を目標に、現実世界のネットワークを制御するための戦略の開発がより効果的になる。
本稿では,pythonによる最適化手法とデータセットの実装について述べる。
関連論文リスト
- Reinforcement Learning for Node Selection in Branch-and-Bound [52.2648997215667]
現在の最先端セレクタは手作りのアンサンブルを使用して、ナイーブなサブノードセレクタと、個々のノードデータに依存する学習ノードセレクタを自動的に切り替える。
孤立ノードではなく木の状態全体を考慮しながら強化学習(RL)を用いる新しいシミュレーション手法を提案する。
論文 参考訳（メタデータ） (2023-09-29T19:55:56Z) - A Fast Algorithm for Moderating Critical Nodes via Edge Removal [19.130541561303293]
対象ノードの情報集中度を最小限に抑えるために,ネットワークから$k$エッジを除去する問題について検討する。
ランダムウォークに基づくシュア補数近似や高速和推定などの新しい手法を用いて、3つの近似グリードアルゴリズムを提案する。
理論的解析を補完するため、100万以上のノードを持つ合成および実ネットワークに関する包括的な実験を行う。
論文 参考訳（メタデータ） (2023-09-09T13:54:34Z) - Multi-Agent congestion cost minimization with linear function
approximation [0.0]
この作業では、ソースノードからゴールノードにネットワークをトラバースする複数のエージェントについて検討する。
エージェントの目的は、最小限の全体的なコストで、分散的な方法でゴールノードへのパスを見つけることである。
本稿では,新しいマルチエージェント・コンジェクション・コスト最小化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-26T08:45:44Z) - A Large-scale Multiple-objective Method for Black-box Attack against
Object Detection [70.00150794625053]
我々は、真正の確率を最小化し、偽正の確率を最大化し、より多くの偽正の物体が新しい真正の有界箱を作らないようにする。
我々は、GARSDCと呼ばれるランダム・サブセット選択とディバイド・アンド・コンカーによる標準的な遺伝的アルゴリズムを拡張し、効率を大幅に改善する。
最先端攻撃法と比較して、GARSDCはmAPでは平均12.0、広範囲な実験ではクエリでは約1000倍減少する。
論文 参考訳（メタデータ） (2022-09-16T08:36:42Z) - Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。
本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。
ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
論文 参考訳（メタデータ） (2021-12-03T14:23:05Z) - Layer Adaptive Node Selection in Bayesian Neural Networks: Statistical
Guarantees and Implementation Details [0.5156484100374059]
スパースディープニューラルネットワークは、大規模研究において予測モデル構築に効率的であることが証明されている。
本稿では,スパイク・アンド・スラブ型ガウス先行法を用いて,訓練中のノード選択を可能にするベイズスパース解を提案する。
本研究は, 先行パラメータのキャラクタリゼーションとともに, 変動的後続一貫性の基本的な結果を確立する。
論文 参考訳（メタデータ） (2021-08-25T00:48:07Z) - An Uncertainty-Driven GCN Refinement Strategy for Organ Segmentation [53.425900196763756]
本研究では,不確実性解析とグラフ畳み込みネットワークに基づくセグメンテーション改善手法を提案する。
半教師付きグラフ学習問題を定式化するために、特定の入力ボリュームにおける畳み込みネットワークの不確実性レベルを用いる。
本手法は膵臓で1%,脾臓で2%向上し,最先端のCRF改善法よりも優れていた。
論文 参考訳（メタデータ） (2020-12-06T18:55:07Z) - Convex Polytope Trees [57.56078843831244]
コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。
木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
論文 参考訳（メタデータ） (2020-10-21T19:38:57Z) - Continuous Profit Maximization: A Study of Unconstrained Dr-submodular
Maximization [4.649999862713523]
我々は、整数格子上の領域である連続利益(CPM-MS)問題を形成する。
格子に基づく二重グリードアルゴリズムを導入し, 定数近似を求める。
本稿では,格子型反復プルーニング手法を提案し,探索空間を効果的に縮小することができる。
論文 参考訳（メタデータ） (2020-04-12T05:35:19Z) - Polynomial-Time Exact MAP Inference on Discrete Models with Global
Dependencies [83.05591911173332]
ジャンクションツリーアルゴリズムは、実行時の保証と正確なMAP推論のための最も一般的な解である。
本稿では,ノードのクローン化による新たなグラフ変換手法を提案する。
論文 参考訳（メタデータ） (2019-12-27T13:30:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。