[Colloquium] Reminder - Konstantinos Ameranis MS Presentation/Jun 3, 2022
Megan Woodward
meganwoodward at uchicago.edu
Fri Jun 3 08:19:18 CDT 2022
This is an announcement of Konstantinos Ameranis's MS Presentation
===============================================
Candidate: Konstantinos Ameranis
Date: Friday, June 03, 2022
Time: 12:30 pm CST
Location: JCL 298
Remote Location: https://uchicago.zoom.us/j/92924855210?pwd=K1VDZFU4OG5PeGVuSlpHSS81R3hXdz09
M.S. Paper Title: Nearly-Linear-Time Approximation Algorithms for Graph Clustering With Provable Guarantees
Abstract: In many graph-clustering applications, overwhelming empirical evidence suggests that communities and clusters are naturally overlapping, calling for novel overlapping graph-partitioning algorithms (OGP). In this work, we introduce a framework based on two novel clustering objectives, which naturally extend the well-studied notion of conductance to overlapping clusters and to clusters with hybrid vertex- and edge-boundary structure. Our main algorithmic contributions are nearly-linear-time algorithms O(log(n))-approximation algorithms for both these objectives. To this end, we show that the cut-matching framework of Khandekar et al. [2014] can be extended to overlapping partitions and give novel cut-improvement primitives that perform a small number of s-t maximum flow computations over the instance graph to detect sparse overlapping partitions near an input partition. Crucially, we implement our approximation algorithm to produce both overlapping and hybrid partitions for large graphs, easily scaling to tens of millions of edges, and test our implementation on real-world datasets against other competitive baselines.
Advisors: Lorenzo Orecchia
Committee Members: Gordon Kindlmann, Babis Tsourakakis, and Lorenzo Orecchia
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220603/c7afe100/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Konstantinos_MA.pdf
Type: application/pdf
Size: 3241301 bytes
Desc: Konstantinos_MA.pdf
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220603/c7afe100/attachment-0001.pdf>
More information about the Colloquium
mailing list