論文の概要: A Fast Maximum $k$-Plex Algorithm Parameterized by the Degeneracy Gap

• arxiv url: http://arxiv.org/abs/2306.13258v1
• Date: Fri, 23 Jun 2023 01:28:24 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-26 13:57:18.623531
• Title: A Fast Maximum $k$-Plex Algorithm Parameterized by the Degeneracy Gap
• Title（参考訳）: 縮退ギャップによってパラメータ化される高速最大$k$-plexアルゴリズム
• Authors: Zhengren Wang, Yi Zhou, Chunyu Luo, Mingyu Xiao
• Abstract要約: 最大$k$-plex問題は、グラフ検索やコミュニティ検出といったアプリケーションにおいて重要な問題であるが、計算的に難しい問題である。 入力インスタンスの新しいパラメータを$g_k(G)$とすることで、このギャップを埋めようとしている。 言い換えれば、入力グラフのサイズで実行時間を持ち、$g_k(G)$で指数関数的なアルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 20.97078451305375
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a graph, the $k$-plex is a vertex set in which each vertex is not adjacent to at most $k-1$ other vertices in the set. The maximum $k$-plex problem, which asks for the largest $k$-plex from a given graph, is an important but computationally challenging problem in applications like graph search and community detection. So far, there is a number of empirical algorithms without sufficient theoretical explanations on the efficiency. We try to bridge this gap by defining a novel parameter of the input instance, $g_k(G)$, the gap between the degeneracy bound and the size of maximum $k$-plex in the given graph, and presenting an exact algorithm parameterized by $g_k(G)$. In other words, we design an algorithm with running time polynomial in the size of input graph and exponential in $g_k(G)$ where $k$ is a constant. Usually, $g_k(G)$ is small and bounded by $O(\log{(|V|)})$ in real-world graphs, indicating that the algorithm runs in polynomial time. We also carry out massive experiments and show that the algorithm is competitive with the state-of-the-art solvers. Additionally, for large $k$ values such as $15$ and $20$, our algorithm has superior performance over existing algorithms.
• Abstract（参考訳）: グラフが与えられると、$k$-plex は、各頂点が集合内の少なくとも$k-1$の他の頂点に隣接しない頂点集合である。 与えられたグラフから最大$k$-plexを求める最大$k$-plex問題は、グラフ検索やコミュニティ検出のようなアプリケーションにおいて、重要だが計算上困難な問題である。 これまでのところ、効率に関する十分な理論的説明のない経験的アルゴリズムは数多く存在する。 このギャップを、入力インスタンスの新たなパラメータである$g_k(G)$、与えられたグラフの縮退境界と最大$k$-plexのサイズの間のギャップを定義し、$g_k(G)$でパラメータ化された正確なアルゴリズムを提示することによって橋渡ししようとする。 言い換えれば、入力グラフのサイズで時間多項式を実行し、$g_k(G)$で指数関数的に$k$を定数とするアルゴリズムを設計する。 通常、$g_k(G)$は、実世界のグラフにおいて$O(\log{(|V|)})$で束縛され、アルゴリズムが多項式時間で実行されることを示す。 また,大規模実験を行い,そのアルゴリズムが最先端の解法と競合することを示した。 さらに、15ドルや20ドルといった大きな$kの値の場合、我々のアルゴリズムは既存のアルゴリズムよりも優れた性能を持つ。

関連論文リスト

• Efficient Top-k s-Biplexes Search over Large Bipartite Graphs [4.507351209412066]
  二部グラフ解析において、$s$-ビスプレックスの列挙は基本的な問題である。 実世界のデータエンジニアリングでは、すべての$sビプレックスを見つけることは必要でも、計算的にも安価でもない。 単純な2n列挙アルゴリズムを破るMVBPを提案する。 FastMVBPは、いくつかのインスタンスで最大3桁のベンチマークアルゴリズムより優れている。
  論文  参考訳（メタデータ） (2024-09-27T06:23:29Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。 クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。 我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
  論文  参考訳（メタデータ） (2024-02-09T19:01:48Z)
• On the instance optimality of detecting collisions and subgraphs [7.055459105099637]
  グラフや関数における部分構造検出問題のラベルなしインスタンス最適性について検討する。 アルゴリズムが任意の入力に対して満足する$A$を許容すれば、問題は$g(n)$-instanceOptimationである。 この結果から,グラフや関数のサブ構造検出問題において,ラベルなしのインスタンス最適性を三分したことが示唆された。
  論文  参考訳（メタデータ） (2023-12-15T20:50:03Z)
• Algoritmo de Contagem Qu\^antico Aplicado ao Grafo Bipartido Completo [0.0]
  Groverのアルゴリズムは、$O(sqrtN/k)$ stepsを使って$N$要素を持つ、順序のないデータベースで$k$要素を見つけることができる。 この研究は、他のグラフのマーク要素の値$k$を推定するために量子カウントアルゴリズムを使用する問題に取り組む。
  論文  参考訳（メタデータ） (2023-12-05T21:15:09Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
  論文  参考訳（メタデータ） (2023-02-22T20:21:25Z)
• Classical algorithms for Forrelation [2.624902795082451]
  1対の$n$-bit Boolean 関数 $f$ と $g$ が与えられたとき、$f$ と $g$ のフーリエ変換の間の相関を推定する。 この問題は、クエリの複雑さの観点から最大の量子スピードアップをもたらすことが知られている。 グラフに基づく回帰問題は、任意の二部グラフに対して時間$O(n)$で解けることを示す。
  論文  参考訳（メタデータ） (2021-02-13T17:25:41Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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