論文の概要: Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities

• arxiv url: http://arxiv.org/abs/2509.15822v1
• Date: Fri, 19 Sep 2025 09:53:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-22 18:18:11.117255
• Title: Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities
• Title（参考訳）: $\sqrt{n}$コミュニティを持つ確率ブロックモデルの相転移
• Authors: Alexandra Carpentier, Christophe Giraud, Nicolas Verzelen,
• Abstract要約: 統計物理学からの予測では、モデルブロック(SBM)におけるコミュニティの回復は、上述の時間で可能であり、上述のケステンスティグム(KS)しきい値のみである。 Chinら(2025)は、最近、スパース体制では、非バックトラックパスを数えることにより、KS閾値以下で、スパースタイムでのコミュニティの回復が可能であることを証明した。
• 参考スコア（独自算出の注目度）: 51.320599504997745
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Predictions from statistical physics postulate that recovery of the communities in Stochastic Block Model (SBM) is possible in polynomial time above, and only above, the Kesten-Stigum (KS) threshold. This conjecture has given rise to a rich literature, proving that non-trivial community recovery is indeed possible in SBM above the KS threshold, as long as the number $K$ of communities remains smaller than $\sqrt{n}$, where $n$ is the number of nodes in the observed graph. Failure of low-degree polynomials below the KS threshold was also proven when $K=o(\sqrt{n})$. When $K\geq \sqrt{n}$, Chin et al.(2025) recently prove that, in a sparse regime, community recovery in polynomial time is possible below the KS threshold by counting non-backtracking paths. This breakthrough result lead them to postulate a new threshold for the many communities regime $K\geq \sqrt{n}$. In this work, we provide evidences that confirm their conjecture for $K\geq \sqrt{n}$: 1- We prove that, for any density of the graph, low-degree polynomials fail to recover communities below the threshold postulated by Chin et al.(2025); 2- We prove that community recovery is possible in polynomial time above the postulated threshold, not only in the sparse regime of~Chin et al., but also in some (but not all) moderately sparse regimes by essentially counting clique occurence in the observed graph.
• Abstract（参考訳）: 統計的物理学からの予測では、SBM(Stochastic Block Model)のコミュニティの回復は、上述の多項式時間で可能であり、上述のKS(Kesten-Stigum)しきい値のみが可能である。 この予想はリッチな文献を生み出し、KS閾値より上のSBMで非自明なコミュニティリカバリが可能であることを証明し、K$のコミュニティの数は、観測されたグラフのノードの数である$\sqrt{n}$より小さいままである。 KS閾値以下の低次多項式の失敗も、$K=o(\sqrt{n})$で証明された。 K\geq \sqrt{n}$, Chin et al (2025) が最近証明されたとき、sparse regime では、非バックトラックパスを数えることによって多項式時間におけるコミュニティの回復が KS しきい値より下にあることを証明した。 この画期的な結果は、多くのコミュニティの体制に新たなしきい値($K\geq \sqrt{n}$)を仮定する結果となった。 この研究では、K\geq \sqrt{n}$: 1- グラフの任意の密度において、低次多項式は、Chen et al (2025) によって仮定されたしきい値より下のコミュニティを回復できないことを証明している。

関連論文リスト

• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Low degree conjecture implies sharp computational thresholds in stochastic block model [3.7873597471903935]
  我々は(拡張)低次予想(対称ブロックモデルにおける[MW23]の最近の形式化)の影響について検討する。 我々は,Kesten-Stigum(KS)しきい値以下で,非リアルタイムアルゴリズムがコミュニティラベルを弱めに復元できることを確立した。 この結果から,ブロックモデルのパラメータの学習において,計算量と統計量との差があることが示唆された。
  論文  参考訳（メタデータ） (2025-02-20T20:21:03Z)
• Harnessing Multiple Correlated Networks for Exact Community Recovery [6.092631511453874]
  複数の相関ネットワークから潜在コミュニティ構造を学習する問題について検討する。 Gaudio、R'acz、Sridhar(COLT 2022)の最近の研究により、正確なコミュニティ回復のための正確な情報理論しきい値が決定された。
  論文  参考訳（メタデータ） (2024-12-03T19:56:52Z)
• Community Detection in the Multi-View Stochastic Block Model [47.43048484980115]
  本稿では,無神論的な観点から,複数の潜在的相関グラフ上でのコミュニティ検出の問題について考察する。 我々はまず,同じノードの集合上で相関グラフを生成するために設計された多視点情報ブロックモデル (MVSBM) と呼ばれるランダムグラフモデルを考案した。
  論文  参考訳（メタデータ） (2024-01-17T13:39:38Z)
• Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
  本稿では, 難易度の高い環境下での強化学習(RL)の基本的限界について検討する。 Emphmulti-steping POMDPs に対して、潜伏状態空間依存はサンプル複雑性において少なくとも$Omega(S1.5)$であることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:59:30Z)
• Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
  本稿では,d-uniform hypergraph block model(d-HSBM)の正確な回復の基本的な限界について検討する。 精度の高いしきい値が存在し、正確な回復がしきい値の上に達成でき、その下には不可能であることを示す。
  論文  参考訳（メタデータ） (2021-05-11T03:39:08Z)

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

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