論文の概要: Perfect Clustering for Sparse Directed Stochastic Block Models

• arxiv url: http://arxiv.org/abs/2601.16427v1
• Date: Fri, 23 Jan 2026 03:53:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-26 14:27:27.531936
• Title: Perfect Clustering for Sparse Directed Stochastic Block Models
• Title（参考訳）: スパース指向確率ブロックモデルのための完全クラスタリング
• Authors: Behzad Aalipur, Yichen Qin,
• Abstract要約: スパース指向SBMにおけるコミュニティ検出のための非スペクトル2段階手法を提案する。 提案手法はまず,非対称設定に適した近傍平滑化スキームを用いて有向確率行列を推定する。 提案手法は,有向スペクトル法とスコア法が劣化した状況下で確実に動作可能であることを示す。
• 参考スコア（独自算出の注目度）: 1.3464152928754485
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Exact recovery in stochastic block models (SBMs) is well understood in undirected settings, but remains considerably less developed for directed and sparse networks, particularly when the number of communities diverges. Spectral methods for directed SBMs often lack stability in asymmetric, low-degree regimes, and existing non-spectral approaches focus primarily on undirected or dense settings. We propose a fully non-spectral, two-stage procedure for community detection in sparse directed SBMs with potentially growing numbers of communities. The method first estimates the directed probability matrix using a neighborhood-smoothing scheme tailored to the asymmetric setting, and then applies $K$-means clustering to the estimated rows, thereby avoiding the limitations of eigen- or singular value decompositions in sparse, asymmetric networks. Our main theoretical contribution is a uniform row-wise concentration bound for the smoothed estimator, obtained through new arguments that control asymmetric neighborhoods and separate in- and out-degree effects. These results imply the exact recovery of all community labels with probability tending to one, under mild sparsity and separation conditions that allow both $γ_n \to 0$ and $K_n \to \infty$. Simulation studies, including highly directed, sparse, and non-symmetric block structures, demonstrate that the proposed procedure performs reliably in regimes where directed spectral and score-based methods deteriorate. To the best of our knowledge, this provides the first exact recovery guarantee for this class of non-spectral, neighborhood-smoothing methods in the sparse, directed setting.
• Abstract（参考訳）: 確率的ブロックモデル(SBM)の厳密なリカバリは、非指向的な設定ではよく理解されているが、特にコミュニティの数が多様化するにつれて、直接的かつ疎結合なネットワークのためには、まだ開発が進んでいない。 指向性SBMのスペクトル法は、非対称で低度なレシエーションの安定性を欠くことが多く、既存の非スペクトルアプローチは、主に非指向性または密集性の設定に焦点を当てている。 本研究は,コミュニティ数の増加にともなうスパース指向SBMにおけるコミュニティ検出のための,完全に非スペクトル2段階の手順を提案する。 この手法はまず非対称な設定に合わせた近傍平滑化スキームを用いて有向確率行列を推定し、次に推定行に$K$-meansクラスタリングを適用し、スパース非対称ネットワークにおける固有値あるいは特異値分解の制限を回避する。 我々の理論的な主な貢献は、非対称な近傍を制御し、内外効果を分離する新しい議論を通じて得られる滑らかな推定子に対する一様行ワイド濃度である。 これらの結果は、わずかに間隔と分離条件の下で、1 に傾向のある全てのコミュニティラベルの正確な回復を示唆し、$γ_n \to 0$ と $K_n \to \infty$ の両方を許容する。 高配向、スパース、非対称ブロック構造を含むシミュレーション研究は、有向スペクトル法とスコア法が劣化する状況下で、提案手法が確実に機能することを実証している。 我々の知る限り、これはスパース・ディレクティブ・セッティングにおけるこのタイプの非スペクトル・近傍平滑化手法に対する最初の正確なリカバリ保証を提供する。

関連論文リスト

• Nonparametric Kernel Clustering with Bandit Feedback [9.68728390492671]
  バンディットフィードバックによるクラスタリングは、クラスタリングアルゴリズムがアイテムをシーケンシャルにクエリしてノイズの多い観察を受信する、一連のアイテムを分割する問題を指す。 我々はカーネルベースのアプローチを導入し、非パラメトリック問題をヒルベルトカーネル空間(RKHS)への平均埋め込みをカーネルに従ってクラスタ化するタスクとして再構築する。 本稿では,アーム分布の最大平均誤差(MMD)とRKHSのばらつきに依存する問題に対して,信号対雑音比の概念を導入する。
  論文  参考訳（メタデータ） (2026-01-12T13:36:07Z)
• Statistical Inference for Fuzzy Clustering [7.416766339318596]
  ファジィ$c$-means (FCM) は、混合メンバーシップを可能にし、不確実性と段階的な遷移をよりよく捉える。 我々は,クラスタサイズ不均衡の可能性のある設定のための,重み付きファジィ$c$-means (WFCM) のための新しいフレームワークを開発した。
  論文  参考訳（メタデータ） (2026-01-06T02:11:01Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  本稿では,クラスタリング結果を導出するための正規制約のみを緩和するグラフベースのクラスタリングアルゴリズムを提案する。 二重制約を勾配に変換するために、非負の制約をクラス確率パラメータに変換する。
  論文  参考訳（メタデータ） (2025-09-23T09:14:39Z)
• Gaussian Mixture Model with unknown diagonal covariances via continuous sparse regularization [0.6627152091494143]
  我々は、コンポーネントの数とそのパラメータを同時に推定するために、Beurling-LASSOフレームワークを使用します。 重要な理論的貢献は、混合成分上の明示的な分離条件の同定である。
  論文  参考訳（メタデータ） (2025-09-16T09:42:44Z)
• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。 本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
  論文  参考訳（メタデータ） (2024-05-24T21:09:19Z)
• Random Forest Weighted Local Fréchet Regression with Random Objects [18.128663071848923]
  本稿では,新しいランダム森林重み付き局所Fr'echet回帰パラダイムを提案する。 最初の方法は、これらの重みを局所平均として、条件付きFr'echet平均を解くことである。 第二の手法は局所線形Fr'echet回帰を行い、どちらも既存のFr'echet回帰法を大幅に改善した。
  論文  参考訳（メタデータ） (2022-02-10T09:10:59Z)
• Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
  本稿では,d-uniform hypergraph block model(d-HSBM)の正確な回復の基本的な限界について検討する。 精度の高いしきい値が存在し、正確な回復がしきい値の上に達成でき、その下には不可能であることを示す。
  論文  参考訳（メタデータ） (2021-05-11T03:39:08Z)
• Log-Likelihood Ratio Minimizing Flows: Towards Robust and Quantifiable Neural Distribution Alignment [52.02794488304448]
  そこで本研究では,対数様比統計量と正規化フローに基づく新しい分布アライメント手法を提案する。 入力領域の局所構造を保存する領域アライメントにおいて,結果の最小化を実験的に検証する。
  論文  参考訳（メタデータ） (2020-03-26T22:10:04Z)

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

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