BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Learning Communities in the Presence of Errors Makarychev, Konstantin


I will talk about learning hidden communities in the presence of modeling errors in the Stochastic Block Model. This model, which is also known as the Planted Partition Model, is widely used for community detection and graph partitioning in various fields, including machine learning, statistics, and social sciences. We consider graphs generated according to the Stochastic Block Model and then modified by an adversary. We allow two types of adversarial errors, Feige—Kilian or monotone errors, and edge outlier errors. In the talk, I will present a simple SDP-based algorithm for finding planted communities in sparse graphs from the Stochastic Block Model and prove that this algorithm is robust to adversarial errors. The talk is based on a joint work with Yury Makarychev and Aravindan Vijayaraghavan (COLT 2016).

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International