Font size: Αα Αα Αα hide gadgets
You are here: Theses » MSc » Konstantinos Koiliaris Anonymously browsing from at 03:03:27, 26-09-2017. login

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.

Scientific committee


Download thesis.


Page updates

No recent updates.

Feeds RSS and Atom feeds

all posts RSS
news RSS
announcements RSS
website news RSS
all events RSS
defenses RSS
exams RSS
seminars RSS
graduations RSS
Web standards: XHTML1.0, CSS3.
© 1996 – 2017 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.