論文の概要: Improving Critical Node Detection Using Neural Network-based
Initialization in a Genetic Algorithm
- arxiv url: http://arxiv.org/abs/2402.00404v1
- Date: Thu, 1 Feb 2024 07:53:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-02 16:00:32.477481
- Title: Improving Critical Node Detection Using Neural Network-based
Initialization in a Genetic Algorithm
- Title（参考訳）: 遺伝的アルゴリズムを用いたニューラルネットワーク初期化による臨界ノード検出の改善
- Authors: Chanjuan Liu, Shike Ge, Zhihan Chen, Wenbin Pei, Enqiang Zhu, Yi Mei,
Hisao Ishibuchi
- Abstract要約: CNP-1aの主な目的は、ネットワークから限られた数のノードを削除した後、残りのネットワークにおけるペアワイズ接続を最小限にすることである。
CNP-1aを解く効率を改善するために、K2GAという知識誘導型遺伝的アルゴリズムが提案されている。
提案した知識誘導型遺伝的アルゴリズムの有効性は,26の実世界の複雑なネットワーク上での実験により検証された。
- 参考スコア（独自算出の注目度）: 3.5877750256097465
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Critical Node Problem (CNP) is concerned with identifying the critical
nodes in a complex network. These nodes play a significant role in maintaining
the connectivity of the network, and removing them can negatively impact
network performance. CNP has been studied extensively due to its numerous
real-world applications. Among the different versions of CNP, CNP-1a has gained
the most popularity. The primary objective of CNP-1a is to minimize the
pair-wise connectivity in the remaining network after deleting a limited number
of nodes from a network. Due to the NP-hard nature of CNP-1a, many
heuristic/metaheuristic algorithms have been proposed to solve this problem.
However, most existing algorithms start with a random initialization, leading
to a high cost of obtaining an optimal solution. To improve the efficiency of
solving CNP-1a, a knowledge-guided genetic algorithm named K2GA has been
proposed. Unlike the standard genetic algorithm framework, K2GA has two main
components: a pretrained neural network to obtain prior knowledge on possible
critical nodes, and a hybrid genetic algorithm with local search for finding an
optimal set of critical nodes based on the knowledge given by the trained
neural network. The local search process utilizes a cut node-based greedy
strategy. The effectiveness of the proposed knowledgeguided genetic algorithm
is verified by experiments on 26 realworld instances of complex networks.
Experimental results show that K2GA outperforms the state-of-the-art algorithms
regarding the best, median, and average objective values, and improves the best
upper bounds on the best objective values for eight realworld instances.
- Abstract（参考訳）: 臨界ノード問題(cnp)は、複雑なネットワーク内の臨界ノードの同定に関する問題である。
これらのノードはネットワークの接続性を維持する上で重要な役割を担い、ネットワーク性能に悪影響を及ぼす可能性がある。
CNPは多くの実世界の応用のために広く研究されている。
CNPの様々なバージョンの中で、CNP-1aが最も人気がある。
CNP-1aの主な目的は、ネットワークから限られた数のノードを削除した後、残りのネットワークにおけるペアワイズ接続を最小限にすることである。
CNP-1aのNPハード性のため、この問題を解決するために多くのヒューリスティック・メタヒューリスティックアルゴリズムが提案されている。
しかし、既存のアルゴリズムのほとんどはランダムな初期化から始まり、最適な解を得るのに高いコストがかかる。
CNP-1aを解く効率を改善するために、K2GAという知識誘導型遺伝的アルゴリズムが提案されている。
標準的な遺伝的アルゴリズムフレームワークとは異なり、k2gaには2つの主要な構成要素がある: 可能な臨界ノードに関する事前知識を得るための事前訓練されたニューラルネットワークと、訓練されたニューラルネットワークによって与えられた知識に基づいて、最適な臨界ノードのセットを見つけるための局所探索を備えたハイブリッド遺伝的アルゴリズムである。
局所探索プロセスはカットノードベースの欲求戦略を利用する。
提案する知識誘導遺伝的アルゴリズムの有効性は,26実世界の複雑なネットワークにおける実験によって検証された。
実験結果から,K2GAは,8つの実世界のインスタンスにおいて,最適,中央値,平均目標値に関する最先端のアルゴリズムよりも優れ,最高の目標値の上限が向上していることがわかった。
関連論文リスト
- Neural Algorithmic Reasoning for Combinatorial Optimisation [20.36694807847833]
ニューラル推論の最近の進歩を活用して,CO問題の学習を改善することを提案する。
私たちは、COインスタンスでトレーニングする前に、関連するアルゴリズムでニューラルネットワークを事前トレーニングすることを提案します。
以上の結果から,この学習装置を用いることで,非アルゴリズム的情報深層学習モデルよりも優れた性能が得られることが示された。
論文 参考訳（メタデータ） (2023-05-18T13:59:02Z) - A Comprehensively Improved Hybrid Algorithm for Learning Bayesian
Networks: Multiple Compound Memory Erasing [0.0]
本稿では、新しいハイブリッドアルゴリズムMCME(multiple compound memory erasing)を提案する。
MCMEは、最初の2つの手法の利点を維持し、上記のCIテストの欠点を解消し、方向判別段階におけるスコアリング機能に革新をもたらす。
多くの実験により、MCMEは既存のアルゴリズムよりも優れた、あるいは類似した性能を示している。
論文 参考訳（メタデータ） (2022-12-05T12:52:07Z) - Towards Better Out-of-Distribution Generalization of Neural Algorithmic
Reasoning Tasks [51.8723187709964]
ニューラルネットワーク推論タスクのOOD一般化について検討する。
目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
論文 参考訳（メタデータ） (2022-11-01T18:33:20Z) - Improved Algorithms for Neural Active Learning [74.89097665112621]
非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。
本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
論文 参考訳（メタデータ） (2022-10-02T05:03:38Z) - Identifying critical nodes in complex networks by graph representation
learning [2.304938062591095]
影響は臨界ノードの採掘における主要な問題の一つである。
IMGNNは、ネットワーク内のノードの集中度を入力とし、最適な初期スプレッドラー内のノードを出力とするグラフ学習フレームワークである。
IMGNNは、ヒトベースのアルゴリズムよりも、固定感染規模で初期スプレッドラーのサイズを最小化するのに効率的である。
論文 参考訳（メタデータ） (2022-01-20T03:41:22Z) - Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。
本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。
ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
論文 参考訳（メタデータ） (2021-12-03T14:23:05Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Finite Versus Infinite Neural Networks: an Empirical Study [69.07049353209463]
カーネルメソッドは、完全に接続された有限幅ネットワークより優れている。
中心とアンサンブルの有限ネットワークは後続のばらつきを減らした。
重みの減衰と大きな学習率の使用は、有限ネットワークと無限ネットワークの対応を破る。
論文 参考訳（メタデータ） (2020-07-31T01:57:47Z) - Neural Bipartite Matching [19.600193617583955]
本稿では,ニューラルネットワークが複雑なアルゴリズムに適用される方法について述べる。
単一のGNNから生成された機能のみに基づいて、ニューラル実行によって実現される。
評価の結果,ネットワークがほぼ100%の時間で最適なマッチングを達成できることが示唆された。
論文 参考訳（メタデータ） (2020-05-22T17:50:38Z) - MSE-Optimal Neural Network Initialization via Layer Fusion [68.72356718879428]
ディープニューラルネットワークは、さまざまな分類と推論タスクに対して最先端のパフォーマンスを達成する。
グラデーションと非進化性の組み合わせは、学習を新しい問題の影響を受けやすいものにする。
確率変数を用いて学習した深層ネットワークの近傍層を融合する手法を提案する。
論文 参考訳（メタデータ） (2020-01-28T18:25:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。