Fundamental Limit of Community Detection in Stochastic Block Models

on YouTube ↗25m

" summary

States an exact information-theoretic threshold for exact recovery in stochastic block models with log-degree scaling: recovery occurs iff a Chernoff–Hellinger style distance between community profiles exceeds one. Provides a quasi-linear degree-profiling algorithm (O(n^{1+ε}) time) that achieves that threshold, and links the threshold to the two-group formula ((a+b)/2 > 1+√(ab)) when p,q ~ (a log n)/n. Tests on a 1,500-node blog network yield ~95% accuracy with parameters just above the threshold.

AI-written summary · about

" chapters (8)

1. 0:00Introduction
2. 3:37Stochastic Block Model
3. 5:32Quiz
4. 6:23Problem
5. 7:38Model
6. 8:04History
7. 13:55Channel Coding Theorem
8. 21:24Proof

" related talks

• 45mCorrelated Stochastic Block Models: Graph Matching And Community RecoveryMiklos Racz · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 43mInformation-Theoretic Bounds and Phase Transitions in Community Detection and High-Dimensional ClustCris Moore · Random Instances and Phase Transitions (Simons Institute, 2016)
• 39mLocal Algorithms for Community DetectionElchanan Mossel · Approximate Counting, Markov Chains and Phase Transitions
• 24mIs it easier to count communities than find them?Cynthia Rush, Fiona Skerman, Alexander S Wein, Dana Yang · ITCS 2023
• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)
• 54mNode Privacy, High-dimensional Graph Summaries, and Block ModelsAdam M. Smith · Privacy and the Science of Data Analysis 2019
• 47mLearning Probabilistic Models for Graph Partitioning in the Presence of NoiseAravindan Vijayaraghavan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 11mSharp Threshold for the Planted Matching ProblemDana Yang · Meet the Fellows Welcome Event