MSc thesis of Konstantinos Koiliaris
Graph Partitioning Under the Spectral Lens
Supervisor: Efstathios Zachos
Finding underlying structure in data has been a fundamental task for mathematicians, computer- and now data-scientists and the importance of clustering and partitioning data has increased dramatically in the past decade. We present the journey of one of the most essential problems in the area: Graph Partitioning. We begin with the importance and the wide range of applications it finds, the computational difficulties involved in solving it efficiently and the inapproximability results tied to it. We demonstrate the first average case analysis approaches using random models, the most prominent of which is the planted partition model or stochastic block model where the graph has k equally sized blocks and vertices connect independently with probability p within blocks and q across blocks. Recently, a large amount of research in computer science and statistics has been invested in providing lower-bounds on the scaling of |p − q| to ensure recovery of the planted blocks (partitions). We focus on the seminal results using spectral techniques and provide a high level overview of this rapidly evolving area, including the recent information-theoretic perspective threshold on the |p − q| range for recovery. Finally, give our own spectral approach for solving Graph Partitioning for arbi- trary k in the planted partition model and albeit not improving the state-of-the-art we believe our approach constitutes a new, easier proof for a very recent result.
Defended: Jan. 12, 2015.