This was my first real research project at 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. Each of n nodes starts with a distinct label; then, iteratively, every node takes on the majority label among its neighbors. The algorithm is simple, fast, model-free, and parallelizable, yet very little is known rigorously about when it is accurate.
We give a near-optimal characterization of when two rounds of label propagation exactly recover communities in a K-community balanced stochastic block model, and complement it with extensive simulations that suggest further conjectures about the behavior of a few rounds of label propagation on the stochastic block model.