論文の概要: Maximum Likelihood Estimation on Stochastic Blockmodels for Directed Graph Clustering

• arxiv url: http://arxiv.org/abs/2403.19516v1
• Date: Thu, 28 Mar 2024 15:47:13 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-29 15:44:37.885278
• Title: Maximum Likelihood Estimation on Stochastic Blockmodels for Directed Graph Clustering
• Title（参考訳）: グラフクラスタリングのための確率的ブロックモデルの最大近似推定
• Authors: Mihai Cucuringu, Xiaowen Dong, Ning Zhang,
• Abstract要約: 我々は、有向ブロックモデルにおいて、基盤となるコミュニティを推定するものとしてクラスタリングを定式化する。 本稿では,2つの効率的かつ解釈可能な有向クラスタリングアルゴリズム,スペクトルクラスタリングアルゴリズム,半定値プログラミングに基づくクラスタリングアルゴリズムを紹介する。
• 参考スコア（独自算出の注目度）: 22.421702511126373
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the directed graph clustering problem through the lens of statistics, where we formulate clustering as estimating underlying communities in the directed stochastic block model (DSBM). We conduct the maximum likelihood estimation (MLE) on the DSBM and thereby ascertain the most probable community assignment given the observed graph structure. In addition to the statistical point of view, we further establish the equivalence between this MLE formulation and a novel flow optimization heuristic, which jointly considers two important directed graph statistics: edge density and edge orientation. Building on this new formulation of directed clustering, we introduce two efficient and interpretable directed clustering algorithms, a spectral clustering algorithm and a semidefinite programming based clustering algorithm. We provide a theoretical upper bound on the number of misclustered vertices of the spectral clustering algorithm using tools from matrix perturbation theory. We compare, both quantitatively and qualitatively, our proposed algorithms with existing directed clustering methods on both synthetic and real-world data, thus providing further ground to our theoretical contributions.
• Abstract（参考訳）: 本稿では,有向確率ブロックモデル(DSBM)の基盤となるコミュニティを推定するためにクラスタリングを定式化する,統計レンズによる有向グラフクラスタリング問題について検討する。 我々はDSBM上で最大推定(MLE)を行い、観測されたグラフ構造から最も確率の高いコミュニティ割り当てを確かめる。 統計学的視点に加えて、このMLE定式化と、エッジ密度とエッジ配向という2つの重要なグラフ統計を共同で考える新しいフロー最適化ヒューリスティックの等価性を確立する。 指向性クラスタリングの新しい定式化に基づいて,2つの効率的かつ解釈可能な指向性クラスタリングアルゴリズム,スペクトルクラスタリングアルゴリズム,半定値プログラミングに基づくクラスタリングアルゴリズムを導入する。 本稿では,行列摂動理論のツールを用いたスペクトルクラスタリングアルゴリズムの誤クラスタ化頂点数に関する理論的上限を与える。 我々は,提案アルゴリズムを,合成データと実世界のデータの両方に有向クラスタリング手法を用いて定量的に定性的に比較し,理論的貢献のさらなる基盤を提供する。

関連論文リスト

• Regularized Projection Matrix Approximation with Applications to Community Detection [1.5033631151609534]
  本稿では,アフィニティ行列からクラスタ情報を復元することを目的とした正規化プロジェクション行列近似フレームワークを提案する。 本稿では,それぞれ有界,正,スパースなシナリオに対処する3つの異なるペナルティ関数を探索し,その問題を解決するために乗算器の交互方向法(ADMM)アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-05-26T15:18:22Z)
• Fuzzy K-Means Clustering without Cluster Centroids [79.19713746387337]
  ファジィK平均クラスタリングは教師なしデータ解析において重要な計算手法である。 本稿では,クラスタセントロイドへの依存を完全に排除する,ファジィK平均クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-07T12:25:03Z)
• Distributed Linear Regression with Compositional Covariates [5.085889377571319]
  大規模合成データにおける分散スパースペナル化線形ログコントラストモデルに着目する。 2つの異なる制約凸最適化問題を解くために2つの分散最適化手法を提案する。 分散化されたトポロジでは、通信効率の高い正規化推定値を得るための分散座標ワイド降下アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2023-10-21T11:09:37Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• Multi-View Clustering via Semi-non-negative Tensor Factorization [120.87318230985653]
  半負のテンソル因子分解(Semi-NTF)に基づく新しいマルチビュークラスタリングを開発する。 本モデルは、ビュー間の関係を直接考慮し、ビュー間の補完情報を利用する。 さらに,提案手法の最適化アルゴリズムを提案し,そのアルゴリズムが常に定常KKT点に収束することを数学的に証明する。
  論文  参考訳（メタデータ） (2023-03-29T14:54:19Z)
• A Modular Framework for Centrality and Clustering in Complex Networks [0.6423239719448168]
  本稿では,集中度とクラスタリングという2つの重要なネットワーク解析手法について検討する。 クラスタリングには情報フローベースのモデルが採用されている。 我々のクラスタリングは、エッジウェイトとノードの度合いの異なる解釈と相互作用と同様に、エッジ指向性に対応する柔軟性を自然に継承する。
  論文  参考訳（メタデータ） (2021-11-23T03:01:29Z)
• Spatially Coherent Clustering Based on Orthogonal Nonnegative Matrix Factorization [0.0]
  本稿では,クラスタメンバシップ行列の総変動(TV)正規化手順に基づく作業クラスタリングモデルを紹介する。 マトリックス支援レーザー脱離イオン化イメージング測定から得られた超スペクトルデータセット上の提案手法をすべて数値的に評価する。
  論文  参考訳（メタデータ） (2021-04-25T23:40:41Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  結合ネットワークトポロジ推論は、異種グラフ信号から複数のグラフラプラシア行列を学習する標準的な問題を表す。 新規な構造化融合正規化に基づく一般グラフ推定器を提案する。 提案するグラフ推定器は高い計算効率と厳密な理論保証の両方を享受できることを示す。
  論文  参考訳（メタデータ） (2021-03-05T04:42:32Z)
• Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit [10.8145995157397]
  高階クラスタリングは、マルチウェイデータセットの異種サブ構造を特定することを目的とする。 非計算と問題の性質は統計学と統計学の両方に重大な課題をもたらす。
  論文  参考訳（メタデータ） (2020-12-18T00:48:27Z)
• Clustering Ensemble Meets Low-rank Tensor Approximation [50.21581880045667]
  本稿では,複数のクラスタリングを組み合わせ,個々のクラスタリングよりも優れたパフォーマンスを実現するクラスタリングアンサンブルの問題について検討する。 本稿では,この問題をグローバルな視点から解くために,新しい低ランクテンソル近似法を提案する。 7つのベンチマークデータセットを用いた実験の結果,提案手法は12の最先端手法と比較して,クラスタリング性能のブレークスルーを達成した。
  論文  参考訳（メタデータ） (2020-12-16T13:01:37Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)

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

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