2015
COLT
COLT 2015
Stochastic Block Model and Community Detection in Sparse Graphs: A spectral algorithm with optimal rate of recovery
Abstract
In this paper, we present and analyze a simple and robust spectral algorithm for the stochastic block model with k blocks, for any k fixed. Our algorithm works with graphs having constant edge density, under an optimal condition on the gap between the density inside a block and the density between the blocks. As a co-product, we settle an open question posed by Abbe et. al. concerning censor block models.
🌉
Interdisciplinary Bridge
— Machine Learning and Mathematics & Optimization
🐣
Hot Topic Early Bird
— graph clustering
🐝
Cross-Pollinator
— Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics, Security & Privacy, Speech & Audio