論文の概要: Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach

• arxiv url: http://arxiv.org/abs/2301.00384v1
• Date: Sun, 1 Jan 2023 10:57:36 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-03 16:04:39.105169
• Title: Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach
• Title（参考訳）: 動的完全符号付きグラフに対する相関クラスタリングアルゴリズム : インデックスベースアプローチ
• Authors: Ali Shakiba
• Abstract要約: 本稿では,相関クラスタリング問題を$O(mtimesleft(2+ alpha (G) right)+n)$から$O(m+n)$に近似する複雑性を,完全符号グラフに対して$varepsilon$とする。 提案手法は,元のアルゴリズムと同じ出力を与え,そのアルゴリズムをフルダイナミックな設定で実装できるようにする。
• 参考スコア（独自算出の注目度）: 9.13755431537592
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we reduce the complexity of approximating the correlation clustering problem from $O(m\times\left( 2+ \alpha (G) \right)+n)$ to $O(m+n)$ for any given value of $\varepsilon$ for a complete signed graph with $n$ vertices and $m$ positive edges where $\alpha(G)$ is the arboricity of the graph. Our approach gives the same output as the original algorithm and makes it possible to implement the algorithm in a full dynamic setting where edge sign flipping and vertex addition/removal are allowed. Constructing this index costs $O(m)$ memory and $O(m\times\alpha(G))$ time. We also studied the structural properties of the non-agreement measure used in the approximation algorithm. The theoretical results are accompanied by a full set of experiments concerning seven real-world graphs. These results shows superiority of our index-based algorithm to the non-index one by a decrease of %34 in time on average.
• Abstract（参考訳）: 本稿では、相関クラスタリング問題を$O(m\times\left(2+ \alpha (G) \right)+n)$から$O(m+n)$に近似する複雑性を、$n$頂点と$m$正の辺を持つ完全符号グラフに対して$O(m+n)$に還元する。 提案手法は元のアルゴリズムと同じ出力を与え,エッジサインのフリップと頂点の加算/除去が許されるフルダイナミックな設定でアルゴリズムを実装できるようにする。 このインデックスの構築には、$o(m)$メモリと$o(m\times\alpha(g))$タイムがかかる。 また,近似アルゴリズムで用いられる非退化測度の構造的性質についても検討した。 理論的結果は、7つの実世界のグラフに関する完全な実験に付随する。 これらの結果は,インデックスベースアルゴリズムが非インデックス型アルゴリズムよりも平均で %34 の低下で優れていることを示している。

関連論文リスト

• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。 我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。 提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
  論文  参考訳（メタデータ） (2024-08-03T20:08:02Z)
• Dynamic Spectral Clustering with Provable Approximation Guarantee [7.6676757797831225]
  本論文は, クラスタ構造が緩やかな条件下では, 最終グラフ$G_T$のクラスタはスペクトルクラスタリングアルゴリズムの動的変種によってよく近似できることを示した。 合成と実世界の両方のデータセットに関する実験的研究により、我々の設計したアルゴリズムの実用性がさらに裏付けられる。
  論文  参考訳（メタデータ） (2024-06-05T11:16:55Z)
• 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)
• Dynamic algorithms for k-center on graphs [3.568439282784197]
  エッジ更新を行う動的グラフ上での$k$-center問題に対する最初の効率的なアルゴリズムを提供する。 完全に動的な$(2+epsilon)$-approximationアルゴリズムを$k$-center問題に対して提案する。
  論文  参考訳（メタデータ） (2023-07-28T13:50:57Z)
• 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)
• 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)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。 アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。 理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
  論文  参考訳（メタデータ） (2021-11-12T07:08:13Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions [9.29659220237395]
  本稿では,相関クラスタリングの解法を提案する。 我々は高効率な時間と空間の複雑さを持つサブ線形アルゴリズムを得る。 提案手法の主な要素はスパース線グラフ分解への新規な接続である。
  論文  参考訳（メタデータ） (2021-09-29T16:25:02Z)
• Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time [1.5644420658691407]
  エッジ重み付きグラフ上での階層的凝集クラスタリング(HAC)アルゴリズムについて検討する。 階層的な集合グラフクラスタリングのためのアルゴリズムフレームワークを定義する。 提案手法は,ポイントデータセットのクラスタリングを20.7～76.5倍の速度で高速化できることを示す。
  論文  参考訳（メタデータ） (2021-06-10T09:29:05Z)
• Random Graph Matching with Improved Noise Robustness [2.294014185517203]
  本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。 我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。 これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
  論文  参考訳（メタデータ） (2021-01-28T02:39:27Z)

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

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