論文の概要: Faster Algorithms for Generalized Mean Densest Subgraph Problem
- arxiv url: http://arxiv.org/abs/2310.11377v1
- Date: Tue, 17 Oct 2023 16:21:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-18 15:12:05.610638
- Title: Faster Algorithms for Generalized Mean Densest Subgraph Problem
- Title（参考訳）: 一般化平均デンストグラフ問題に対する高速アルゴリズム
- Authors: Chenglin Fan, Ping Li, Hanyu Peng
- Abstract要約: 標準的な剥離アルゴリズムは、0p 1$の場合にも21/p$-近似が得られることを示す。
本稿では,新しいより高速な一般化剥離アルゴリズム(GENPEEL++)を提案する。
- 参考スコア（独自算出の注目度）: 26.3881083827734
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The densest subgraph of a large graph usually refers to some subgraph with
the highest average degree, which has been extended to the family of $p$-means
dense subgraph objectives by~\citet{veldt2021generalized}. The $p$-mean densest
subgraph problem seeks a subgraph with the highest average $p$-th-power degree,
whereas the standard densest subgraph problem seeks a subgraph with a simple
highest average degree. It was shown that the standard peeling algorithm can
perform arbitrarily poorly on generalized objective when $p>1$ but uncertain
when $0<p<1$. In this paper, we are the first to show that a standard peeling
algorithm can still yield $2^{1/p}$-approximation for the case $0<p < 1$.
(Veldt 2021) proposed a new generalized peeling algorithm (GENPEEL), which for
$p \geq 1$ has an approximation guarantee ratio $(p+1)^{1/p}$, and time
complexity $O(mn)$, where $m$ and $n$ denote the number of edges and nodes in
graph respectively. In terms of algorithmic contributions, we propose a new and
faster generalized peeling algorithm (called GENPEEL++ in this paper), which
for $p \in [1, +\infty)$ has an approximation guarantee ratio $(2(p+1))^{1/p}$,
and time complexity $O(m(\log n))$, where $m$ and $n$ denote the number of
edges and nodes in graph, respectively. This approximation ratio converges to 1
as $p \rightarrow \infty$.
- Abstract（参考訳）: 大きなグラフの最も密度の高い部分グラフは、通常、平均次数が最も高い部分グラフを指し、~\citet{veldt2021generalized} によって$p$-means の高密度部分グラフの対象の族に拡張される。
$p$-mean の高密度部分グラフ問題は最も高い$p$-th-power のグラフを求めるが、標準的な高密度部分グラフ問題は単純な平均学位のグラフを求める。
その結果,標準剥離アルゴリズムは,0<p<1$のとき,0<p<1$のとき,一般目的に対して任意に粗悪な処理を行うことができた。
本稿では,標準的な剥離アルゴリズムが,0<p < 1$の場合に対して,まだ2^{1/p}$-approximationを得られることを示す最初の方法である。
(veldt 2021) は新たな一般化ピーリングアルゴリズム (genpeel) を提案し、これは$p \geq 1$ に対して近似保証比 $(p+1)^{1/p}$ と時間複雑性 $o(mn)$ を持ち、$m$ と $n$ はそれぞれグラフの辺数とノード数を表す。
アルゴリズム的貢献の観点からは、新しいより高速な一般化ピーリングアルゴリズム (genpeel++ と呼ばれる) を提案し、これは$p \in [1, +\infty)$ に対して近似保証比 $(2(p+1))^{1/p}$ と時間複雑性 $o(m(\log n))$ を持ち、ここで $m$ と $n$ はそれぞれグラフのエッジ数とノード数を表す。
この近似比は 1 に収束して $p \rightarrow \infty$ となる。
関連論文リスト
- 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) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳（メタデータ） (2023-04-17T10:38:08Z) - Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An
Index-based Approach [9.13755431537592]
本稿では,相関クラスタリング問題を$O(mtimesleft(2+ alpha (G) right)+n)$から$O(m+n)$に近似する複雑性を,完全符号グラフに対して$varepsilon$とする。
提案手法は,元のアルゴリズムと同じ出力を与え,そのアルゴリズムをフルダイナミックな設定で実装できるようにする。
論文 参考訳（メタデータ） (2023-01-01T10:57:36Z) - Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
カワラバヤシとソープは、単純なグラフ $G = (V,E)$ の最小カットに対して、ほぼ自明な時間決定論的アルゴリズムを与えた。
重み付きグラフの$(1+varepsilon)$-KTパーティションを見つけるために、線形に近い時間ランダム化アルゴリズムを与える。
論文 参考訳（メタデータ） (2021-11-02T05:26:10Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - The Generalized Mean Densest Subgraph Problem [30.33731479053404]
1つのパラメータ$p$でパラメータ化された、高密度なサブグラフ対象の新しいファミリーを導入する。
我々の目的は、標準の高密度部分グラフ問題と特別な場合の最大$k$-coreの両方をキャプチャする。
我々の研究の大きな貢献は、理論と実践の両方において、密接な部分グラフに対する様々な種類の剥離アルゴリズムの性能を分析することである。
論文 参考訳（メタデータ） (2021-06-02T02:58:35Z) - Adapting $k$-means algorithms for outliers [1.9290392443571387]
我々は、$k$-means問題に対して、複数の単純なサンプリングベースのアルゴリズムを、外れ値を持つ設定に適応する方法を示す。
我々のアルゴリズムは、目的関数に対して$O(varepsilon)$-approximationを行いながら、$(varepsilon)z$outliersを出力する。
論文 参考訳（メタデータ） (2020-07-02T14:14:33Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。