論文の概要: Community Detection and Stochastic Block Models
- arxiv url: http://arxiv.org/abs/1703.10146v3
- Date: Wed, 25 Oct 2023 02:53:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-29 16:21:16.230680
- Title: Community Detection and Stochastic Block Models
- Title（参考訳）: コミュニティ検出と確率ブロックモデル
- Authors: Emmanuel Abbe
- Abstract要約: 幾何ブロックモデル(SBM)はクラスタリングとコミュニティ検出を研究するための標準モデルとして広く用いられている。
統計学やデータ科学で発生する情報理論と計算上のトレードオフを研究するための、肥大した基盤を提供する。
本書は、SBMにおけるコミュニティ検出の基本的な限界を確立する最近の発展について調査する。
- 参考スコア（独自算出の注目度）: 20.058330327502503
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The stochastic block model (SBM) is a random graph model with different group
of vertices connecting differently. It is widely employed as a canonical model
to study clustering and community detection, and provides a fertile ground to
study the information-theoretic and computational tradeoffs that arise in
combinatorial statistics and more generally data science.
This monograph surveys the recent developments that establish the fundamental
limits for community detection in the SBM, both with respect to
information-theoretic and computational tradeoffs, and for various recovery
requirements such as exact, partial and weak recovery. The main results
discussed are the phase transitions for exact recovery at the
Chernoff-Hellinger threshold, the phase transition for weak recovery at the
Kesten-Stigum threshold, the optimal SNR-mutual information tradeoff for
partial recovery, and the gap between information-theoretic and computational
thresholds.
The monograph gives a principled derivation of the main algorithms developed
in the quest of achieving the limits, in particular two-round algorithms via
graph-splitting, semi-definite programming, (linearized) belief propagation,
classical/nonbacktracking spectral methods and graph powering. Extensions to
other block models, such as geometric block models, and a few open problems are
also discussed.
- Abstract（参考訳）: 確率ブロックモデル(SBM)は、異なる頂点群が異なる接続を行うランダムグラフモデルである。
クラスタリングとコミュニティ検出を研究するための標準モデルとして広く用いられ、組合せ統計学やより一般的にデータ科学で発生する情報理論と計算のトレードオフを研究するための肥大した基盤を提供する。
このモノグラフは、情報理論と計算上のトレードオフと、厳密、部分的、弱い回復といった様々な回復要件の両方に関して、sbmにおけるコミュニティ検出の基本的な限界を確立する最近の進展を調査している。
本研究の主な成果は、チェルノフ・ヘリンジャー閾値での正確な回復のための相転移、ケステン・スティグム閾値での弱い回復のための相転移、部分回復のための最適SNR-ミューチュアル情報トレードオフ、情報理論と計算しきい値の間のギャップである。
モノグラフは、限界を達成するために開発された主要なアルゴリズム、特にグラフ分割、半定値計画、(線形化)信念伝播、古典的/非バックトラックスペクトル法、グラフ電力による2ラウンドアルゴリズムを原理的に導出する。
幾何学的ブロックモデルなどの他のブロックモデルの拡張や、いくつかのオープン問題についても論じている。
関連論文リスト
- Wasserstein proximal operators describe score-based generative models
and resolve memorization [12.321631823103894]
We first formulate SGMs with terms of Wasserstein proximal operator (WPO)
We show that WPO describe the inductive bias of diffusion and score-based model。
本稿では,SGMの性能を劇的に向上させる,スコア関数の解釈可能なカーネルベースモデルを提案する。
論文 参考訳（メタデータ） (2024-02-09T03:33:13Z) - Fundamental limits of community detection from multi-view data:
multi-layer, dynamic and partially labeled block models [7.778975741303385]
現代のネットワーク分析におけるマルチビューデータのコミュニティ検出について検討する。
我々は,データと潜在パラメータ間の相互情報を特徴付ける。
コミュニティ検出のための近似メッセージパッシングに基づく反復アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-01-16T07:13:32Z) - Distributed Bayesian Learning of Dynamic States [65.7870637855531]
提案アルゴリズムは有限状態隠れマルコフモデルに対する分散ベイズフィルタタスクである。
逐次状態推定や、動的環境下でのソーシャルネットワーク上での意見形成のモデル化に使用できる。
論文 参考訳（メタデータ） (2022-12-05T19:40:17Z) - GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP,
and Beyond [101.5329678997916]
対話型意思決定の一般的な枠組みの下で, サンプル高能率強化学習(RL)について検討した。
本稿では,探索とエクスプロイトの基本的なトレードオフを特徴付ける,新しい複雑性尺度である一般化エルダー係数(GEC)を提案する。
低 GEC の RL 問題は非常にリッチなクラスであり、これは低ベルマン楕円体次元問題、双線型クラス、低証人ランク問題、PO-双線型クラス、一般化正規PSR を仮定する。
論文 参考訳（メタデータ） (2022-11-03T16:42:40Z) - Semi-Supervised Clustering of Sparse Graphs: Crossing the
Information-Theoretic Threshold [3.6052935394000234]
ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。
ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。
パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
論文 参考訳（メタデータ） (2022-05-24T00:03:25Z) - Inverting brain grey matter models with likelihood-free inference: a
tool for trustable cytoarchitecture measurements [62.997667081978825]
脳の灰白質細胞構造の特徴は、体密度と体積に定量的に敏感であり、dMRIでは未解決の課題である。
我々は新しいフォワードモデル、特に新しい方程式系を提案し、比較的スパースなb殻を必要とする。
次に,提案手法を逆転させるため,確率自由推論 (LFI) として知られるベイズ解析から最新のツールを適用した。
論文 参考訳（メタデータ） (2021-11-15T09:08:27Z) - Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
本稿では,d-uniform hypergraph block model(d-HSBM)の正確な回復の基本的な限界について検討する。
精度の高いしきい値が存在し、正確な回復がしきい値の上に達成でき、その下には不可能であることを示す。
論文 参考訳（メタデータ） (2021-05-11T03:39:08Z) - Exact Clustering in Tensor Block Model: Statistical Optimality and
Computational Limit [10.8145995157397]
高階クラスタリングは、マルチウェイデータセットの異種サブ構造を特定することを目的とする。
非計算と問題の性質は統計学と統計学の両方に重大な課題をもたらす。
論文 参考訳（メタデータ） (2020-12-18T00:48:27Z) - Identification of Probability weighted ARX models with arbitrary domains [75.91002178647165]
PieceWise Affineモデルは、ハイブリッドシステムの他のクラスに対する普遍近似、局所線型性、同値性を保証する。
本研究では,任意の領域を持つ固有入力モデル(NPWARX)を用いたPieceWise Auto Regressiveの同定に着目する。
このアーキテクチャは、機械学習の分野で開発されたMixture of Expertの概念に従って考案された。
論文 参考訳（メタデータ） (2020-09-29T12:50:33Z) - Model Fusion with Kullback--Leibler Divergence [58.20269014662046]
異種データセットから学習した後続分布を融合する手法を提案する。
我々のアルゴリズムは、融合モデルと個々のデータセット後部の両方に対する平均場仮定に依存している。
論文 参考訳（メタデータ） (2020-07-13T03:27:45Z) - Non-Convex Exact Community Recovery in Stochastic Block Model [31.221745716673546]
近年,対称ブロックモデル(SBM)に基づくグラフのコミュニティ検出が注目されている。
この問題の対数的疎度構造において、提案した2段階法は、$mathcalO(nlog2n/loglog n)$ timeにおいて、情報理論の限界まで正確に2つのコミュニティを復元できることを示す。
また, 提案手法の有効性を実証し, 理論的発展を補完するために, 合成データセットと実データセットの両方で数値実験を行った。
論文 参考訳（メタデータ） (2020-06-29T07:03:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。