Information-Theoretic Bounds and Phase Transitions in Community Detection and High-Dimensional Clust

on YouTube ↗43m

" summary

Uses the second moment method and small-subgraph conditioning to bound when planted structure is statistically detectable versus a null Erdős–Rényi graph, showing an explicit threshold: roughly lambda^2·d ≲ 2 log K/(K−1) (so information-theoretic detection sits below the Kesten–Stigum / spectral threshold for large K). The proof converts the likelihood-ratio variance into an overlap entropy vs Frobenius-norm optimization, proves contiguity in that regime, and connects to spectral tests based on the nonbacktracking matrix.

AI-written summary · about

" chapters (9)

1. 0:00Start
2. 6:07The Stochastic Block Model
3. 11:08Planted Coloring Problem
4. 16:42Likelihood Ratio Testing
5. 26:13An Overlap Matrix
6. 28:56Entropy of Zeta
7. 35:41Spectral Method
8. 38:11Big Data Limit
9. 42:29Condensation Point

" related talks

• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)
• 25mFundamental Limit of Community Detection in Stochastic Block ModelsEmmanuel Abbe · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 39mLocal Algorithms for Community DetectionElchanan Mossel · Approximate Counting, Markov Chains and Phase Transitions
• 11mUnderstanding Statistical-to-Computational Gaps via Low-Degree PolynomialsAlex Wein · Meet the Fellows Welcome Event
• 43mGlobal Community Detection Using Individual-Centered Partial Information NetworksRachel Wang · Statistics in the Big Data Era 2022
• 41mReducibility and Statistical-Computational Gaps from Secret LeakageGuy Bresler · Computational Phase Transitions (Simons Institute, 2020)
• 41mGeneral Network Models with Transitive StructuresSharmodeep Bhattacharyya · Statistics in the Big Data Era 2022
• 01h 11mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)