論文の概要: Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps
- arxiv url: http://arxiv.org/abs/2306.13258v3
- Date: Tue, 14 Nov 2023 06:45:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-15 18:53:27.838122
- Title: Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps
- Title(参考訳): 小型縮退ギャップを用いた高速最大$k$-Plexアルゴリズム
- Authors: Zhengren Wang, Yi Zhou, Chunyu Luo, Mingyu Xiao, Jin-Kao Hao
- Abstract要約: 最大$k$-plex問題は、グラフマイニングやコミュニティ検出といったアプリケーションでは重要であるが、計算的に困難である。
我々は、入力グラフのサイズで最悪のランニング時間を持ち、$g_k(G)$で指数関数的な$g_k(G)$でパラメータ化された正確なアルゴリズムを示す。
我々はさらに議論を、より小さなパラメータ$cg_k(G)$、コミュニティの世代境界と最大$k$-plexのサイズの間のギャップにまで拡張します。
- 参考スコア(独自算出の注目度): 30.06993761032835
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given a graph, a $k$-plex is a set of vertices 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 the given graph, is an
important but computationally challenging problem in applications such as graph
mining and community detection. So far, there are many practical algorithms,
but without providing theoretical explanations on their efficiency. We define a
novel parameter of the input instance, $g_k(G)$, the gap between the degeneracy
bound and the size of the maximum $k$-plex in the given graph, and present an
exact algorithm parameterized by this $g_k(G)$, which has a worst-case running
time polynomial in the size of the input graph and exponential in $g_k(G)$. In
real-world inputs, $g_k(G)$ is very small, usually bounded by $O(\log{(|V|)})$,
indicating that the algorithm runs in polynomial time. We further extend our
discussion to an even smaller parameter $cg_k(G)$, the gap between the
community-degeneracy bound and the size of the maximum $k$-plex, and show that
without much modification, our algorithm can also be parameterized by
$cg_k(G)$. To verify the empirical performance of these algorithms, we carry
out extensive experiments to show that these algorithms are competitive with
the state-of-the-art algorithms. In particular, for large $k$ values such as
$15$ and $20$, our algorithms dominate the existing algorithms. Finally,
empirical analysis is performed to illustrate the effectiveness of the
parameters and other key components in the implementation.
- Abstract(参考訳): グラフが与えられたとき、$k$-plex は各頂点が集合内の少なくとも $k-1$ の他の頂点に隣接しない頂点の集合である。
与えられたグラフから最大$k$-plexを求める最大$k$-plex問題は、グラフマイニングやコミュニティ検出といったアプリケーションにおいて、重要ではあるが計算上困難な問題である。
今のところ、実用的なアルゴリズムは数多く存在するが、その効率に関する理論的説明は提供されていない。
入力のインスタンスの新たなパラメータである$g_k(G)$、与えられたグラフの退化境界と最大$k$-plexのサイズの間のギャップを定義し、この$g_k(G)$でパラメータ化された正確なアルゴリズムを示す。
実世界の入力では、$g_k(G)$は非常に小さく、通常$O(\log{(|V|)})$で束縛されている。
さらに、より小さなパラメータである$cg_k(G)$、コミュニティ縮退境界と最大$k$-plexの大きさのギャップまで議論を拡大し、多くの修正がなければ、我々のアルゴリズムは$cg_k(G)$でパラメータ化できることを示す。
これらのアルゴリズムの実証性能を検証するため、我々は、これらのアルゴリズムが最先端のアルゴリズムと競合することを示す広範な実験を行った。
特に15ドルや20ドルといった大きな$k$の場合、我々のアルゴリズムは既存のアルゴリズムを支配しています。
最後に、実験分析を行い、実装におけるパラメータやその他の重要なコンポーネントの有効性を説明する。
関連論文リスト
- 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) - 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) - Verification and search algorithms for causal DAGs [11.038866111306728]
クレーム因果グラフの正しさを確認するために、最小サイズの原子介入のセットを特徴づける。
我々は,ノード依存の介入コストと境界サイズ介入の設定に対して,その結果を一般化する。
この結果は、一般の未重み付きグラフ上での検証サイズに対する非自明な近似を保証する最初のアルゴリズムである。
論文 参考訳(メタデータ) (2022-06-30T15:52:30Z) - Classical algorithms and quantum limitations for maximum cut on
high-girth graphs [6.262125516926276]
すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。
1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
論文 参考訳(メタデータ) (2021-06-10T16:28:23Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。