論文の概要: Scalable Community Detection via Parallel Correlation Clustering
- arxiv url: http://arxiv.org/abs/2108.01731v1
- Date: Tue, 27 Jul 2021 04:33:37 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-08 11:07:33.263403
- Title: Scalable Community Detection via Parallel Correlation Clustering
- Title（参考訳）: 並列相関クラスタリングによるスケーラブルなコミュニティ検出
- Authors: Jessica Shi, Laxman Dhulipala, David Eisenstat, Jakub {\L}\k{a}cki,
Vahab Mirrokni
- Abstract要約: グラフクラスタリングとコミュニティ検出は、現代のデータマイニングの中心的な問題である。
本稿では,地上の真実に基づいて,高品質なアルゴリズムを設計する。
- 参考スコア（独自算出の注目度）: 1.5644420658691407
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph clustering and community detection are central problems in modern data
mining. The increasing need for analyzing billion-scale data calls for faster
and more scalable algorithms for these problems. There are certain trade-offs
between the quality and speed of such clustering algorithms. In this paper, we
design scalable algorithms that achieve high quality when evaluated based on
ground truth. We develop a generalized sequential and shared-memory parallel
framework based on the LambdaCC objective (introduced by Veldt et al.), which
encompasses modularity and correlation clustering. Our framework consists of
highly-optimized implementations that scale to large data sets of billions of
edges and that obtain high-quality clusters compared to ground-truth data, on
both unweighted and weighted graphs. Our empirical evaluation shows that this
framework improves the state-of-the-art trade-offs between speed and quality of
scalable community detection. For example, on a 30-core machine with two-way
hyper-threading, our implementations achieve orders of magnitude speedups over
other correlation clustering baselines, and up to 28.44x speedups over our own
sequential baselines while maintaining or improving quality.
- Abstract（参考訳）: グラフクラスタリングとコミュニティ検出は、現代のデータマイニングの中心的な問題である。
このような問題に対する高速でスケーラブルなアルゴリズムのために、数十億規模のデータコールを分析する必要性が高まっている。
このようなクラスタリングアルゴリズムの品質とスピードにはある種のトレードオフがある。
本稿では,基礎的真理に基づいて評価することで高品質を実現するスケーラブルなアルゴリズムを考案する。
We developed a generalized sequence and shared-Memory parallel framework based on the LambdaCC objective (introduceed by Veldt et al。
これはモジュラリティと相関クラスタリングを含んでいる。
我々のフレームワークは、数十億のエッジの大規模なデータセットにスケールする高度に最適化された実装で構成され、未重み付きグラフと重み付きグラフの両方で、地上の真実データと比較して高品質なクラスタを得る。
実験的な評価から,このフレームワークは,スケーラブルなコミュニティ検出の速度と品質の間の最先端のトレードオフを改善していることを示す。
例えば、双方向のハイパースレッディングを備えた30コアマシンでは、他の相関クラスタリングベースラインよりも1桁のスピードアップを実現し、品質を維持したり改善したりしながら、独自のシーケンシャルベースライン上で最大28.44倍のスピードアップを実現しています。
関連論文リスト
- Evolvable Agents, a Fine Grained Approach for Distributed Evolutionary
Computing: Walking towards the Peer-to-Peer Computing Frontiers [0.0]
本稿では,分散進化計算における自己適応的移動率を用いた微粒化手法を提案する。
我々は,プロセッサ数の増加に伴って,ソリューションの品質とアルゴリズムの速度がどう変化するかを比較することで,アプローチの生存可能性を分析する。
この実験により,本手法はアイランドモデルよりも優れたスケーラビリティを示し,実験中の3つのテスト関数の平均値に対して等価なロバスト性を示す。
論文 参考訳（メタデータ） (2024-01-30T18:11:31Z) - Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。
提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。
フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
論文 参考訳（メタデータ） (2023-08-13T18:12:28Z) - Large-scale Fully-Unsupervised Re-Identification [78.47108158030213]
大規模未ラベルデータから学ぶための2つの戦略を提案する。
第1の戦略は、近傍関係に違反することなく、それぞれのデータセットサイズを減らすために、局所的な近傍サンプリングを行う。
第2の戦略は、低時間上限の複雑さを持ち、メモリの複雑さを O(n2) から O(kn) に k n で還元する新しい再帰的手法を利用する。
論文 参考訳（メタデータ） (2023-07-26T16:19:19Z) - Efficient Forecasting of Large Scale Hierarchical Time Series via
Multilevel Clustering [26.236569277576425]
本稿では階層的に集約された時系列データをクラスタリングする問題に対する新しいアプローチを提案する。
集約されたレベルごとに時系列をグループ化し、同時にローカル情報とグローバル情報を活用する。
論文 参考訳（メタデータ） (2022-05-27T17:13:05Z) - Cluster-and-Conquer: A Framework For Time-Series Forecasting [94.63501563413725]
本稿では,高次元時系列データを予測するための3段階フレームワークを提案する。
当社のフレームワークは非常に汎用的で,各ステップで時系列予測やクラスタリングが利用可能です。
単純な線形自己回帰モデルでインスタンス化されると、いくつかのベンチマークデータセットで最先端の結果が得られる。
論文 参考訳（メタデータ） (2021-10-26T20:41:19Z) - ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering
using Nearest-Neighbor Chain [6.824747267214373]
本稿では並列階層クラスタリング(HAC)アルゴリズムを設計するためのParChainフレームワークを提案する。
従来の並列HACアルゴリズムと比較して、我々の新しいアルゴリズムは線形メモリしか必要とせず、大規模データセットにスケーラブルである。
我々のアルゴリズムは、既存のアルゴリズムでは処理できない数千万のポイントでデータセットのサイズにスケールすることができる。
論文 参考訳（メタデータ） (2021-06-08T23:13:27Z) - Interpretable Clustering on Dynamic Graphs with Recurrent Graph Neural
Networks [24.017988997693262]
ノードとノードのクラスタメンバーシップ間の接続が時間とともに変化する可能性がある動的グラフにおけるノードのクラスタリングの問題を検討する。
まず,ノード間の重み付き接続に基づいてノードをクラスタ化し,その重みが時間とともに一定速度で減少する,簡易な崩壊ベースのクラスタリングアルゴリズムを提案する。
本稿では,各クラスタの最適減衰率を特徴付け,真のクラスタのほぼ完全回復を実現するクラスタリング手法を提案する。
論文 参考訳（メタデータ） (2020-12-16T04:31:19Z) - (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time
Warping [57.316437798033974]
本研究では,トラジェクトリの集中型クラスタリングの問題について考察する。
我々はDTWの連続バージョンを距離測定として使用することを提案し、これをCDTW(Continuous dynamic time warping)と呼ぶ。
一連の軌道から中心を計算し、その後反復的に改善する実践的な方法を示す。
論文 参考訳（メタデータ） (2020-12-01T13:17:27Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳（メタデータ） (2020-10-22T15:58:35Z) - Learning to Cluster Faces via Confidence and Connectivity Estimation [136.5291151775236]
重複する部分グラフを多数必要とせず,完全に学習可能なクラスタリングフレームワークを提案する。
提案手法はクラスタリングの精度を大幅に向上させ,その上で訓練した認識モデルの性能を向上させるが,既存の教師付き手法に比べて桁違いに効率的である。
論文 参考訳（メタデータ） (2020-04-01T13:39:37Z) - Clustering with Fast, Automated and Reproducible assessment applied to
longitudinal neural tracking [3.817161834189992]
C-FARは階層的クラスタリングアルゴリズムを同時に評価する新しい手法である。
提案アルゴリズムは,複数の階層的クラスタリング木を入力として,人間のフィードバックに対して戦略的にペアを問合せし,これらの木に推薦された木の中から最適なクラスタリングを出力する。
私たちのフラッグシップアプリケーションは、スパイクソートにおけるクラスタアグリゲーションステップであり、ニューロンに録音中の波形(スパイク)を割り当てるタスクです。
論文 参考訳（メタデータ） (2020-03-19T01:33:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。