論文の概要: Finding Nontrivial Minimum Fixed Points in Discrete Dynamical Systems
- arxiv url: http://arxiv.org/abs/2301.04090v4
- Date: Sun, 18 Feb 2024 19:24:19 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-21 07:36:58.005693
- Title: Finding Nontrivial Minimum Fixed Points in Discrete Dynamical Systems
- Title（参考訳）: 離散力学系における非自明な最小固定点の探索
- Authors: Zirou Qiu, Chen Chen, Madhav V. Marathe, S. S. Ravi, Daniel J.
Rosenkrantz, Richard E. Stearns, Anil Vullikanti
- Abstract要約: 影響を受けるノードの最小数でシステムの非自明な固定点を求めるという新しい最適化問題を定式化する。
この計算難易度に対処するため,この問題を効率的に解決できる特別な事例をいくつか挙げる。
大規模ネットワーク上での問題を解くため,グリーディ選択法とともに汎用的なフレームワークを提案する。
- 参考スコア（独自算出の注目度）: 31.214315560851926
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Networked discrete dynamical systems are often used to model the spread of
contagions and decision-making by agents in coordination games. Fixed points of
such dynamical systems represent configurations to which the system converges.
In the dissemination of undesirable contagions (such as rumors and
misinformation), convergence to fixed points with a small number of affected
nodes is a desirable goal. Motivated by such considerations, we formulate a
novel optimization problem of finding a nontrivial fixed point of the system
with the minimum number of affected nodes. We establish that, unless P = NP,
there is no polynomial time algorithm for approximating a solution to this
problem to within the factor n^1-\epsilon for any constant epsilon > 0. To cope
with this computational intractability, we identify several special cases for
which the problem can be solved efficiently. Further, we introduce an integer
linear program to address the problem for networks of reasonable sizes. For
solving the problem on larger networks, we propose a general heuristic
framework along with greedy selection methods. Extensive experimental results
on real-world networks demonstrate the effectiveness of the proposed
heuristics.
- Abstract（参考訳）: ネットワーク化された離散力学システムは、協調ゲームにおけるエージェントによる伝染と意思決定の拡散をモデル化するためにしばしば用いられる。
このような力学系の固定点は、システムが収束する構成を表す。
望ましくない感染(噂や誤報など)の拡散においては、少数の影響を受けるノードを持つ固定点への収束が望ましい目標である。
このような考慮により、影響を受けるノード数が最小となるシステムの非自明な固定点を見つけるという、新しい最適化問題を定式化する。
p = np でない限り、この問題の解を任意の定数エプシロン > 0 の係数 n^1-\epsilon に近似する多項式時間アルゴリズムは存在しない。
この計算難易度に対処するため,この問題を効率的に解決できる特別な事例をいくつか挙げる。
さらに,適切な大きさのネットワークに対する問題に対処する整数線形プログラムを提案する。
大規模ネットワーク上での問題を解くために、欲求選択法とともに一般的なヒューリスティックな枠組みを提案する。
実世界のネットワークにおける広範囲な実験結果から,提案するヒューリスティックスの有効性が示された。
関連論文リスト
- Interacting Particle Systems on Networks: joint inference of the network
and the interaction kernel [8.535430501710712]
エージェント間の相互作用のルールを決定するネットワークとシステムの重み行列を推論する。
我々は2つのアルゴリズムを使用する: 1つは演算子回帰と呼ばれる新しいアルゴリズムで、最小2乗のデータを交互に更新する。
どちらのアルゴリズムも、識別可能性と適正性を保証するスケーラブルな条件である。
論文 参考訳（メタデータ） (2024-02-13T12:29:38Z) - Correctness Verification of Neural Networks Approximating Differential
Equations [0.0]
ニューラルネットワーク(NN)は部分微分方程式(PDE)の解を近似する
NNはシミュレーションソフトウェアツールの不可欠な部分となり、複雑な動的システムのシミュレーションを100回以上加速することができる。
この研究は、NN微分を有限差分近似として定義することにより、これらの関数の検証に対処する。
初めて、出力領域の事前知識のないNN関数のバウンダリング問題に取り組む。
論文 参考訳（メタデータ） (2024-02-12T12:55:35Z) - A Stable and Scalable Method for Solving Initial Value PDEs with Neural
Networks [52.5899851000193]
我々は,ネットワークの条件が悪くなるのを防止し,パラメータ数で時間線形に動作するODEベースのIPPソルバを開発した。
このアプローチに基づく現在の手法は2つの重要な問題に悩まされていることを示す。
まず、ODEに従うと、問題の条件付けにおいて制御不能な成長が生じ、最終的に許容できないほど大きな数値誤差が生じる。
論文 参考訳（メタデータ） (2023-04-28T17:28:18Z) - Accelerated Solutions of Coupled Phase-Field Problems using Generative
Adversarial Networks [0.0]
我々は,エンコーダデコーダに基づく条件付きGeneLSTM層を用いたニューラルネットワークに基づく新しいフレームワークを開発し,Cahn-Hilliardマイクロ構造方程式を解く。
トレーニングされたモデルはメッシュとスケールに依存しないため、効果的なニューラル演算子としての応用が保証される。
論文 参考訳（メタデータ） (2022-11-22T08:32:22Z) - Improved Training of Physics-Informed Neural Networks with Model
Ensembles [81.38804205212425]
我々は、PINNを正しい解に収束させるため、解区間を徐々に拡大することを提案する。
すべてのアンサンブルのメンバーは、観測されたデータの近くで同じ解に収束する。
提案手法は, 得られた解の精度を向上させることができることを示す。
論文 参考訳（メタデータ） (2022-04-11T14:05:34Z) - Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。
本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。
ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
論文 参考訳（メタデータ） (2021-12-03T14:23:05Z) - Optimal Transport Based Refinement of Physics-Informed Neural Networks [0.0]
我々は、最適輸送(OT)の概念に基づく偏微分方程式(PDE)の解法として、よく知られた物理情報ニューラルネットワーク(PINN)の改良戦略を提案する。
PINNの解法は、完全接続された病理のスペクトルバイアス、不安定な勾配、収束と精度の難しさなど、多くの問題に悩まされている。
本稿では,既存の PINN フレームワークを補完する OT-based sample を用いて,Fokker-Planck-Kolmogorov Equation (FPKE) を解くための新しいトレーニング戦略を提案する。
論文 参考訳（メタデータ） (2021-05-26T02:51:20Z) - dNNsolve: an efficient NN-based PDE solver [62.997667081978825]
ODE/PDEを解決するためにデュアルニューラルネットワークを利用するdNNsolveを紹介します。
我々は,dNNsolveが1,2,3次元の幅広いODE/PDEを解くことができることを示す。
論文 参考訳（メタデータ） (2021-03-15T19:14:41Z) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。
このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文 参考訳（メタデータ） (2020-10-31T21:35:42Z) - Multipole Graph Neural Operator for Parametric Partial Differential
Equations [57.90284928158383]
物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。
線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。
実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
論文 参考訳（メタデータ） (2020-06-16T21:56:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。