Fugu-MT 論文翻訳(概要): Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities (II)

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

arxiv url: http://arxiv.org/abs/2511.21526v1
Date: Wed, 26 Nov 2025 15:54:17 GMT
ステータス: 翻訳完了
システム内更新日: 2025-11-27 18:37:59.183542
Title: Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities (II)
Title（参考訳）: $\sqrt{n}$コミュニティを持つ確率ブロックモデルの相転移(II)
Authors: Alexandra Carpentier, Christophe Giraud, Nicolas Verzelen,
Abstract要約: コミュニティの$K$が$sqrtn$より小さい場合、Kesten-Stigumしきい値を超えれば、非自明なコミュニティリカバリが可能になる。また、適度にスパースな設定では、最適なアルゴリズムがスペクトル法と根本的に異なることを示す。
参考スコア（独自算出の注目度）: 51.320599504997745
License: http://creativecommons.org/licenses/by/4.0/
Abstract: A fundamental theoretical question in network analysis is to determine under which conditions community recovery is possible in polynomial time in the Stochastic Block Model (SBM). When the number $K$ of communities remains smaller than $\sqrt{n}$ --where $n$ denotes the number of nodes--, non-trivial community recovery is possible in polynomial time above, and only above, the Kesten--Stigum (KS) threshold, originally postulated using arguments from statistical physics. When $K \geq \sqrt{n}$, Chin, Mossel, Sohn, and Wein recently proved that, in the \emph{sparse regime}, community recovery in polynomial time is achievable below the KS threshold by counting non-backtracking paths. This finding led them to postulate a new threshold for the many-communities regime $K \geq \sqrt{n}$. Subsequently, Carpentier, Giraud, and Verzelen established the failure of low-degree polynomials below this new threshold across all density regimes, and demonstrated successful recovery above the threshold in certain moderately sparse settings. While these results provide strong evidence that, in the many community setting, the computational barrier lies at the threshold proposed in~Chin et al., the question of achieving recovery above this threshold still remains open in most density regimes. The present work is a follow-up to~Carpentier et al., in which we prove Conjecture~1.4 stated therein by: \\ 1- Constructing a family of motifs satisfying specific structural properties; and\\ 2- Proving that community recovery is possible above the proposed threshold by counting such motifs.\\ Our results complete the picture of the computational barrier for community recovery in the SBM with $K \geq \sqrt{n}$ communities. They also indicate that, in moderately sparse regimes, the optimal algorithms appear to be fundamentally different from spectral methods.
Abstract（参考訳）: ネットワーク解析における基本的な理論的問題は、確率ブロックモデル(SBM)の多項式時間において、どの条件下でコミュニティ回復が可能かを決定することである。コミュニティの$K$が$\sqrt{n}$ --where $n$がノードの数を表す場合、上述の多項式時間で非自明なコミュニティリカバリが可能である。 K \geq \sqrt{n}$, Chin, Mossel, Sohn, and Wein は、最近 \emph{sparse regime} において、多項式時間におけるコミュニティの回復は、非バックトラックパスを数えることによって KS 閾値以下で達成可能であることを証明した。この発見により、多くのコミュニティ体制に対する新しいしきい値が$K \geq \sqrt{n}$に仮定された。その後、カルペンティエ(Carpentier)、ジラウド(Giraud)、ヴェルツェレン(Verzelen)は、この新しいしきい値以下の低次多項式が全ての密度条件で失敗することを確立し、一定の緩やかな設定でしきい値を超える回復に成功したことを証明した。これらの結果は、多くのコミュニティ環境では、計算障壁は–Chin et al で提案されたしきい値にあるという強い証拠を提供するが、このしきい値を超える回復を達成するという問題は、ほとんどの密度の制度において依然として未解決のままである。本研究は,「カルペンティエ et al 」のフォローアップであり,「1-特定の構造特性を満たすモチーフの族を構成する」と「2-」の2つのモチーフを数えることによって,コミュニティの回復が可能であることを証明した。我々の結果は、SBMにおけるコミュニティ回復のための計算障壁の図面を、$K \geq \sqrt{n}$ community. 彼らはまた、適度にスパースな規則では、最適アルゴリズムがスペクトル法と根本的に異なるように見えることも示している。

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

関連論文リスト