Label Propagation Algorithms on Balanced Stochastic Block Models

[Note that the poster on this page is quite old - will update soon!]

This was my first real research project and NU, and I will be eternally grateful to my advisor, Prof. Miki Racz, and my PhD mentor, Shuwen Chai, for their mentorship, enthusiasm, and seemingly endless patience for my questions.

Abstract

We study the label propagation algorithm for recovering communities in a graph. In this algorithm, each of n nodes starts with a distinct label; then, iteratively, each node takes on the majority label among its neighbors. This algorithm is simple, fast, model-free, and parallelizable, yet very little is known rigorously about when it is accurate.

Here, we give a near-optimal characterization of when two rounds of label propagation exactly recover communities in a K-community balanced stochastic block model. We complement this with extensive simulations that suggest further conjectures on the behavior of few rounds of label propagation on the stochastic block model.