論文の概要: Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks

• arxiv url: http://arxiv.org/abs/2201.06877v1
• Date: Tue, 18 Jan 2022 11:16:40 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-19 21:52:32.851722
• Title: Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks
• Title（参考訳）: 複雑ネットワークにおける最小ノードセパレータ探索のための頻繁な項目セット駆動探索
• Authors: Yangming Zhou and Xiaze Zhang and Na Geng and Zhibin Jiang and Mengchu Zhou
• Abstract要約: 本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。 頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。 特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
• 参考スコア（独自算出の注目度）: 61.2383572324176
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Finding an optimal set of critical nodes in a complex network has been a long-standing problem in the fields of both artificial intelligence and operations research. Potential applications include epidemic control, network security, carbon emission monitoring, emergence response, drug design, and vulnerability assessment. In this work, we consider the problem of finding a minimal node separator whose removal separates a graph into multiple different connected components with fewer than a limited number of vertices in each component. To solve it, we propose a frequent itemset-driven search approach, which integrates the concept of frequent itemset mining in data mining into the well-known memetic search framework. Starting from a high-quality population built by the solution construction and population repair procedures, it iteratively employs the frequent itemset recombination operator (to generate promising offspring solution based on itemsets that frequently occur in high-quality solutions), tabu search-based simulated annealing (to find high-quality local optima), population repair procedure (to modify the population), and rank-based population management strategy (to guarantee a healthy population). Extensive evaluations on 50 widely used benchmark instances show that it significantly outperforms state-of-the-art algorithms. In particular, it discovers 29 new upper bounds and matches 18 previous best-known bounds. Finally, experimental analyses are performed to confirm the effectiveness of key algorithmic modules of the proposed method.
• Abstract（参考訳）: 複雑なネットワークにおいて最適なクリティカルノードの集合を見つけることは、人工知能と運用研究の両方の分野で長年の課題であった。 潜在的な応用としては、疫病対策、ネットワークセキュリティ、二酸化炭素排出量モニタリング、創発反応、薬物設計、脆弱性評価などがある。 本研究では,グラフを複数の異なる連結成分に分離する最小ノード分離器を,各成分に限定された数の頂点未満で見つける問題を考える。 そこで本研究では,データマイニングにおける頻繁なアイテムセットマイニングの概念を,よく知られたmemetic searchフレームワークに統合した,頻繁なアイテムセット駆動検索手法を提案する。 ソリューション構築と人口修復手順によって構築された高品質な人口から始まり、頻繁なアイテムセット再結合オペレータ(高品質なソリューションで頻繁に発生するアイテムセットに基づく有望な子孫ソリューションの生成)、タブサーチに基づくシミュレートアニーリング(高品質なローカルオプティマを見つける)、人口修復手順(人口変更)、ランクベースの人口管理戦略(健康な人口を保証するため)を反復的に採用する。 広く使用されている50のベンチマークインスタンスに対する広範な評価は、最先端のアルゴリズムを大幅に上回っていることを示している。 特に29の新たな上限を発見し、18の最もよく知られた境界と一致する。 最後に,提案手法の重要なアルゴリズムモジュールの有効性を検証する実験を行った。

関連論文リスト

• A Learning Search Algorithm for the Restricted Longest Common Subsequence Problem [40.64116457007417]
  RLCS問題(Restricted Longest Common Subsequence)はバイオインフォマティクスにおいて重要な応用である。 本稿では,将来性のある地域に向けて,探索プロセスを強化するための2つの新しいアプローチを提案する。 この論文の重要な貢献は、科学的な抽象が入力文字列として機能する実世界のインスタンスの生成である。
  論文  参考訳（メタデータ） (2024-10-15T20:02:15Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• Multivariate Time Series Anomaly Detection: Fancy Algorithms and Flawed Evaluation Methodology [2.043517674271996]
  本稿では、MVTS異常検出の文脈において、正常によいプロトコルが弱点を持つ可能性について論じる。 本稿では,PCA(Principal Components Analysis)に基づくシンプルな,かつ難しいベースラインを提案する。このベースラインは,最近のDeep Learning(DL)ベースのアプローチにおいて,一般的なベンチマークデータセットよりも驚くほど優れています。
  論文  参考訳（メタデータ） (2023-08-24T20:24:12Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。 標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。 我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。 本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
  論文  参考訳（メタデータ） (2023-04-01T15:50:18Z)
• 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)
• Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
  Multipartiteエンティティ解決は、複数のデータセットから1つのエンティティにレコードを統合することを目的としている。 代入問題を解くために、グリーディアルゴリズムと大規模近傍探索という2つの手順を適用する。 データベースのサイズが大きくなるにつれて、設計ベースのマルチスタートがより効率的であることを示す。
  論文  参考訳（メタデータ） (2021-12-06T20:34:55Z)
• 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)
• Mixed Membership Graph Clustering via Systematic Edge Query [22.77704627076251]
  この研究は、ほとんど不完全なグラフのクラスタリングノードを考慮する。 問題設定の下では、エッジに関する少数のクエリしか作成できないが、グラフ全体はオブザーバブルではない。 この問題は,限定アノテーションを用いた大規模データクラスタリング,限定された調査リソースによるコミュニティ検出,グラフトポロジ推論などに適用できる。
  論文  参考訳（メタデータ） (2020-11-25T19:19:05Z)
• Multilevel Image Thresholding Using a Fully Informed Cuckoo Search Algorithm [3.451622180162228]
  人口ベースメタヒューリスティックアルゴリズムは探索能力を向上させるために広く利用されている。 本稿では,リングトポロジに基づく完全情報戦略を用いて,cuckoo searchと呼ばれるメタヒューリスティックなメタヒューリスティックを改良する。
  論文  参考訳（メタデータ） (2020-05-31T13:22:27Z)

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

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