Local Algorithms for Community Detection

on YouTube ↗39m

" summary

Studies reconstruction on a Poisson D tree and gives exact conditions when noisy boundary labels give the same root-recovery probability as perfect labels (e.g. relates to D(1−2ε)^2 thresholds and nontrivial limits). Shows that initializing with any slightly-better-than-random estimator and running belief propagation (a local algorithm) reaches information-theoretic optimal recovery for two equal-size clusters, extends to models with side information and degree-correlated trees, and poses open counterexamples and deterministic-counting questions.

AI-written summary · about

" chapters (7)

1. 0:00Local algorithms intro
2. 3:24Broadcasting on trees
3. 11:44Phase transitions in models
4. 19:59Block models connection
5. 27:00Belief propagation optimality
6. 32:43Counting in percolation
7. 37:01Open problems

" related talks

• 25mFundamental Limit of Community Detection in Stochastic Block ModelsEmmanuel Abbe · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)
• 47mLearning Probabilistic Models for Graph Partitioning in the Presence of NoiseAravindan Vijayaraghavan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 25mLucky Talk: From Coding to ClusteringEmmanuel Abbe · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 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)
• 52mNew Algorithms For The Graph Alignment ProblemMarc Lelarge · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 11mSharp Threshold for the Planted Matching ProblemDana Yang · Meet the Fellows Welcome Event