論文の概要: Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps
- arxiv url: http://arxiv.org/abs/2306.13258v2
- Date: Tue, 7 Nov 2023 08:41:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-08 22:33:30.361409
- 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$の場合、我々のアルゴリズムは既存のアルゴリズムを支配しています。
最後に、実験分析を行い、実装におけるパラメータやその他の重要なコンポーネントの有効性を説明する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。