論文の概要: CBAG: An Efficient Genetic Algorithm for the Graph Burning Problem
- arxiv url: http://arxiv.org/abs/2208.01008v1
- Date: Mon, 1 Aug 2022 17:34:07 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-02 13:18:40.779634
- Title: CBAG: An Efficient Genetic Algorithm for the Graph Burning Problem
- Title（参考訳）: CBAG:グラフバーニング問題に対する効率的な遺伝的アルゴリズム
- Authors: Mahdi Nazeri, Ali Mollahosseini and Iman Izadi
- Abstract要約: グラフ燃焼問題の解法として,Centrality BAsed Genetic-algorithm (CBAG) という効率的な遺伝的アルゴリズムを提案する。
グラフバーニング問題の特徴を考慮し,新しい染色体表現法と評価法を提案する。
この結果から,提案アルゴリズムは従来の最先端の中央値と比較して性能が向上していることが明らかとなった。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Information spread is an intriguing topic to study in network science, which
investigates how information, influence, or contagion propagate through
networks. Graph burning is a simplified deterministic model for how information
spreads within networks. The complicated NP-complete nature of the problem
makes it computationally difficult to solve using exact algorithms.
Accordingly, a number of heuristics and approximation algorithms have been
proposed in the literature for the graph burning problem. In this paper, we
propose an efficient genetic algorithm called Centrality BAsed
Genetic-algorithm (CBAG) for solving the graph burning problem. Considering the
unique characteristics of the graph burning problem, we introduce novel genetic
operators, chromosome representation, and evaluation method. In the proposed
algorithm, the well-known betweenness centrality is used as the backbone of our
chromosome initialization procedure. The proposed algorithm is implemented and
compared with previous heuristics and approximation algorithms on 15 benchmark
graphs of different sizes. Based on the results, it can be seen that the
proposed algorithm achieves better performance in comparison to the previous
state-of-the-art heuristics. The complete source code is available online and
can be used to find optimal or near-optimal solutions for the graph burning
problem.
- Abstract（参考訳）: 情報拡散は、情報、影響、感染がネットワークを介してどのように伝播するかを研究するネットワーク科学の研究において興味深いトピックである。
グラフバーニングは、情報のネットワーク内での拡散方法の単純化された決定論的モデルである。
この問題の複雑なNP完全性は、正確なアルゴリズムを用いて計算的に解くのを困難にしている。
したがって、グラフ燃焼問題に関する文献では、多くのヒューリスティックスと近似アルゴリズムが提案されている。
本稿では,グラフバーニング問題を解決するために,Centrality BAsed Genetic-algorithm (CBAG) と呼ばれる効率的な遺伝的アルゴリズムを提案する。
グラフバーニング問題の特異性を考慮して,新規な遺伝操作者,染色体表現および評価法を提案する。
提案アルゴリズムでは、染色体初期化過程のバックボーンとして、よく知られた相互性中心性を用いる。
提案アルゴリズムは, 異なるサイズの15個のベンチマークグラフ上で, 従来のヒューリスティックスおよび近似アルゴリズムと比較した。
この結果から,提案アルゴリズムは従来の最先端ヒューリスティックスと比較して性能が向上していることがわかる。
完全なソースコードはオンラインで利用可能であり、グラフバーニング問題に対する最適あるいはほぼ最適のソリューションを見つけるために使用できる。
関連論文リスト
- Recombination vs Stochasticity: A Comparative Study on the Maximum Clique Problem [0.393259574660092]
最大傾き問題(英: maximum clique problem、MCP)は、グラフ理論と計算複雑性の基本的な問題である。
様々なメタヒューリスティックがMPPを近似するために使われており、遺伝的アルゴリズムやメメティックアルゴリズム、アリコロニーアルゴリズム、欲求アルゴリズム、タブアルゴリズム、シミュレートされたアニーリングなどがある。
以上の結果から,モンテカルロのアルゴリズムはランダム検索を用いてグラフを生成するが,速度と能力の両面で遺伝的アルゴリズムを上回っていることが示唆された。
論文 参考訳（メタデータ） (2024-09-26T12:50:00Z) - A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。
我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
論文 参考訳（メタデータ） (2024-03-21T11:57:16Z) - Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。
最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。
データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
論文 参考訳（メタデータ） (2024-03-11T06:34:05Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - Improved Exact and Heuristic Algorithms for Maximum Weight Clique [1.2074552857379273]
最大重量傾き問題の解法として,精度の向上とラベリングアルゴリズムを提案する。
提案アルゴリズムは, 局所グラフ構造を用いた新しいデータ削減規則を用いて, 成功した手法をインターリーブする。
我々は,アルゴリズムを合成および実世界のグラフで評価し,ほとんどの入力において,その技術の現状よりも優れていることを示す。
論文 参考訳（メタデータ） (2023-02-01T14:02:06Z) - Graph Matching via Optimal Transport [11.93151370164898]
グラフマッチング問題の解決は、運用研究、コンピュータビジョン、神経科学などへの応用により、ますます重要になっている。
現在の最先端のアルゴリズムは、非常に大きなグラフのマッチングには非効率であるが、精度は高い。
我々は,最新のグラフマッチングアルゴリズム "FAQ" (Vogelstein, 2015) を改良した GOAT を,その線形和割り当てステップを Cuturi (2013) の "Lightspeed Optimal Transport" メソッドに置き換える。
論文 参考訳（メタデータ） (2021-11-09T19:18:18Z) - Graph Signal Restoration Using Nested Deep Algorithm Unrolling [85.53158261016331]
グラフ信号処理は、センサー、社会交通脳ネットワーク、ポイントクラウド処理、グラフネットワークなど、多くのアプリケーションにおいてユビキタスなタスクである。
凸非依存型深部ADMM(ADMM)に基づく2つの復元手法を提案する。
提案手法のパラメータはエンドツーエンドでトレーニング可能である。
論文 参考訳（メタデータ） (2021-06-30T08:57:01Z) - Self-Supervised Deep Graph Embedding with High-Order Information Fusion
for Community Discovery [3.6002285517472767]
提案アルゴリズムは,複数の深部グラフ畳み込みニューラルネットワークを学習するために,自己教師機構とグラフの高次情報を用いている。
複数のグラフ畳み込みニューラルネットワークの出力を融合して、グラフの属性と構造情報を含むノードの表現を抽出する。
論文 参考訳（メタデータ） (2021-02-05T17:22:28Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。