論文の概要: Heuristic algorithms for the stochastic critical node detection problem

• arxiv url: http://arxiv.org/abs/2512.01497v1
• Date: Mon, 01 Dec 2025 10:18:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-02 19:46:34.798192
• Title: Heuristic algorithms for the stochastic critical node detection problem
• Title（参考訳）: 確率臨界ノード検出問題に対するヒューリスティックアルゴリズム
• Authors: Tuguldur Bayarsaikhan, Altannar Chinchuluun, Ashwin Arulselvan, Panos Pardalos,
• Abstract要約: ネットワークが与えられた場合、クリティカルノード検出問題は、ネットワーク接続を妨害するノードのサブセットを見つける。 本稿では,特定の確率によってエッジの存在が与えられる臨界ノード検出問題のバージョンについて考察する。 本稿では,問題に対する学習に基づく手法を提案し,既存のアルゴリズムと比較する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a network, the critical node detection problem finds a subset of nodes whose removal disrupts the network connectivity. Since many real-world systems are naturally modeled as graphs, assessing the vulnerability of the network is essential, with applications in transportation systems, traffic forecasting, epidemic control, and biological networks. In this paper, we consider a stochastic version of the critical node detection problem, where the existence of edges is given by certain probabilities. We propose heuristics and learning-based methods for the problem and compare them with existing algorithms. Experimental results performed on random graphs from small to larger scales, with edge-survival probabilities drawn from different distributions, demonstrate the effectiveness of the methods. Heuristic methods often illustrate the strongest results with high scalability, while learning-based methods maintain nearly constant inference time as the network size and density grow.
• Abstract（参考訳）: ネットワークが与えられた場合、クリティカルノード検出問題は、ネットワーク接続を妨害するノードのサブセットを見つける。 多くの現実世界のシステムは自然にグラフとしてモデル化されているため、交通システム、交通予知、疫病対策、生物学的ネットワークなど、ネットワークの脆弱性を評価することが不可欠である。 本稿では,特定の確率によってエッジの存在が与えられる臨界ノード検出問題の確率的バージョンについて考察する。 本稿では,問題に対するヒューリスティックスと学習に基づく手法を提案し,既存のアルゴリズムと比較する。 異なる分布から引き出されたエッジ生存確率を持つ小規模から大規模のランダムグラフ上で実験結果から,本手法の有効性が示された。 ヒューリスティックな手法はしばしば高いスケーラビリティを持つ最強の結果を示すが、学習ベースの手法はネットワークサイズと密度が大きくなるにつれてほぼ一定間隔の推論時間を維持できる。

関連論文リスト

• Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound [3.0567348883549816]
  ニューラルネットワークの確率的検証問題は、入力の確率分布の下で、ニューラルネットワークの出力分布を正式に解析することに関わる。 本稿では,ニューラルネットワークの出力に対する確率の下位および上位境界を反復的に精算するアルゴリズムに基づいて,これらの問題を解決するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-27T18:00:03Z)
• A Fast Algorithm for Moderating Critical Nodes via Edge Removal [19.130541561303293]
  対象ノードの情報集中度を最小限に抑えるために,ネットワークから$k$エッジを除去する問題について検討する。 ランダムウォークに基づくシュア補数近似や高速和推定などの新しい手法を用いて、3つの近似グリードアルゴリズムを提案する。 理論的解析を補完するため、100万以上のノードを持つ合成および実ネットワークに関する包括的な実験を行う。
  論文  参考訳（メタデータ） (2023-09-09T13:54:34Z)
• Cycle Consistency-based Uncertainty Quantification of Neural Networks in Inverse Imaging Problems [10.992084413881592]
  ディープニューラルネットワークの多くの応用には不確実性推定が不可欠である。 サイクル整合性に基づく逆問題に使用されるディープニューラルネットワークに対する不確実性定量化手法を示す。
  論文  参考訳（メタデータ） (2023-05-22T09:23:18Z)
• A Systematic Evaluation of Node Embedding Robustness [77.29026280120277]
  本研究では,ノード埋め込みモデルのランダムおよび逆毒攻撃に対する経験的ロバスト性を評価する。 ネットワーク特性とノードラベルを用いて計算したエッジの追加,削除,再切り替えの戦略を比較した。 その結果,ノード分類はネットワーク再構成とは対照的に,高い性能劣化に悩まされていることがわかった。
  論文  参考訳（メタデータ） (2022-09-16T17:20:23Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。 本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。 ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
  論文  参考訳（メタデータ） (2021-12-03T14:23:05Z)
• Community detection using low-dimensional network embedding algorithms [1.052782170493037]
  我々はDeepWalkとnode2vecという2つの主要なアルゴリズムが、標準ネットワークモデルのためのコミュニティを回復する際の性能を厳格に理解している。 固定された共起窓を考えると、非追跡確率の低いランダムウォークを用いた node2vec は、多くのスペーサーネットワークで成功することを示す。
  論文  参考訳（メタデータ） (2021-11-04T14:57:43Z)
• Bayesian Attention Belief Networks [59.183311769616466]
  注意に基づくニューラルネットワークは、幅広いタスクにおいて最先端の結果を得た。 本稿では,非正規化注意重みをモデル化してデコーダネットワークを構築するベイズ的注意信念ネットワークについて紹介する。 提案手法は, 精度, 不確実性推定, ドメイン間の一般化, 敵攻撃において, 決定論的注意と最先端の注意よりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-09T17:46:22Z)
• Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning [50.24174211654775]
  本論文では,アトリビュートネットワーク上の異常検出のためのコントラスト型自己監視学習フレームワークを提案する。 このフレームワークは、新しいタイプのコントラストインスタンスペアをサンプリングすることで、ネットワークデータからのローカル情報を完全に活用します。 高次元特性と局所構造から情報埋め込みを学習するグラフニューラルネットワークに基づくコントラスト学習モデルを提案する。
  論文  参考訳（メタデータ） (2021-02-27T03:17:20Z)
• ESPN: Extremely Sparse Pruned Networks [50.436905934791035]
  簡単な反復マスク探索法により,非常に深いネットワークの最先端の圧縮を実現することができることを示す。 本アルゴリズムは,シングルショット・ネットワーク・プルーニング法とロッテ・ティケット方式のハイブリッド・アプローチを示す。
  論文  参考訳（メタデータ） (2020-06-28T23:09:27Z)

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

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