論文の概要: Discovering Locally Maximal Bipartite Subgraphs

• arxiv url: http://arxiv.org/abs/2211.10446v1
• Date: Fri, 18 Nov 2022 15:45:45 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-22 22:00:41.584374
• Title: Discovering Locally Maximal Bipartite Subgraphs
• Title（参考訳）: 局所的な最大二部グラフの発見
• Authors: Dominik D\"urrschnabel, Tom Hanika, Gerd Stumme
• Abstract要約: この研究において、この問題はより弱い概念であり、包含最大性を支持するために最大性制約を捨てる。 本稿では,これらの部分グラフを抽出し,その結果を大域問題の解と比較する3つの方法を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Induced bipartite subgraphs of maximal vertex cardinality are an essential concept for the analysis of graphs. Yet, discovering them in large graphs is known to be computationally hard. Therefore, we consider in this work a weaker notion of this problem, where we discard the maximality constraint in favor of inclusion maximality. Thus, we aim to discover locally maximal bipartite subgraphs. For this, we present three heuristic approaches to extract such subgraphs and compare their results to the solutions of the global problem. For the latter, we employ the algorithmic strength of fast SAT-solvers. Our three proposed heuristics are based on a greedy strategy, a simulated annealing approach, and a genetic algorithm, respectively. We evaluate all four algorithms with respect to their time requirement and the vertex cardinality of the discovered bipartite subgraphs on several benchmark datasets
• Abstract（参考訳）: 最大頂点濃度の誘導二部グラフは、グラフの分析に不可欠な概念である。 しかし、大きなグラフでそれらを発見することは計算が難しいことが知られている。 したがって、本研究ではこの問題のより弱い概念として、包含最大性を支持する最大性制約を廃止する。 そこで我々は,局所的な最大二部グラフの発見を目指す。 そこで我々は,このような部分グラフを抽出し,その結果をグローバル問題の解と比較するための3つのヒューリスティックなアプローチを提案する。 後者では,高速SAT-ソルバのアルゴリズム強度を用いる。 提案した3つのヒューリスティックは, それぞれ, グリーディ戦略, 模擬アニーリングアプローチ, 遺伝的アルゴリズムに基づく。 いくつかのベンチマークデータセット上で発見された2部グラフの時間要件と頂点濃度に関する4つのアルゴリズムすべてを評価する。

関連論文リスト

• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。 本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T04:40:05Z)
• Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
  クラスタ削除は、計算およびソーシャルネットワーク分析におけるNPハードグラフクラスタリングの目的である。 まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。 補助グラフにおいて最大等級を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
  論文  参考訳（メタデータ） (2024-04-24T18:39:18Z)
• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。 我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
  論文  参考訳（メタデータ） (2024-03-21T11:57:16Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。 ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。 本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
  論文  参考訳（メタデータ） (2023-06-21T17:03:22Z)
• Learning Heuristics for the Maximum Clique Enumeration Problem Using Low Dimensional Representations [0.0]
  本稿では,最大列挙問題の傾きを低減するために,入力グラフのプルーニング処理に学習フレームワークを用いる。 本手法の性能評価において,異なる頂点表現を用いることが果たす役割について検討する。 分類過程において局所的なグラフ特徴を用いることで,特徴の除去過程と組み合わせることで,より正確な結果が得られることが観察された。
  論文  参考訳（メタデータ） (2022-10-30T22:04:32Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Mining Large Quasi-cliques with Quality Guarantees from Vertex Neighborhoods [44.007522460918565]
  密度の高い部分グラフをマイニングすることは、グラフマイニングタスクのスペクトルにおいて重要なプリミティブである。 実世界のグラフから非自明な大きさのクランプと準クランプをマイニングすることは、しばしば難しい問題ではないことを示す。
  論文  参考訳（メタデータ） (2020-08-18T15:50:25Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets [82.74514886461257]
  min-max最適化アルゴリズムは周期サイクルや同様の現象が存在するため、はるかに大きな問題に遭遇する。 問題のどの点も引き付けないアルゴリズムが存在することを示す。 ほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほとんどである。
  論文  参考訳（メタデータ） (2020-06-16T10:49:27Z)

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

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