<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
<span style="margin:0px;font-size:12pt;color:black;background-color:rgb(255, 255, 255)"><span style="margin:0px;font-size:15px;color:rgb(32, 31, 30);background-color:white"><span style="margin:0px"><span style="margin:0px;font-size:16px;color:rgb(49, 49, 49);word-spacing:1px"><font style="font-size:1.13em"><b>Date:</b> May
4th, Wednesday</font></span></span></span></span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
<div style="margin:0px;font-size:12pt;color:black;background-color:rgb(255, 255, 255)">
<div style="margin:0px;font-size:15px;color:rgb(32, 31, 30);background-color:white">
<div style="margin:0px">
<div style="margin:0px;font-size:16px;color:rgb(49, 49, 49);word-spacing:1px"><font style="font-size:1.13em"><b>Time: </b>12:30pm CT</font></div>
<div style="margin:0px;font-size:16px;color:rgb(49, 49, 49);word-spacing:1px"><font style="font-size:1.13em"><b>Location: </b>JCL 390</font></div>
<div dir="auto" style="margin:0px;font-size:16px;color:rgb(49, 49, 49);word-spacing:1px">
<b><font style="font-size:1.13em"><br>
</font></b></div>
<div dir="auto" style="margin:0px;font-size:16px;color:rgb(49, 49, 49);word-spacing:1px">
<b><font style="font-size:1.13em">Speaker: <span> </span><span data-markjs="true" class="marke54hqorjt" data-ogac="" data-ogab="" data-ogsc="" data-ogsb="" style="margin:0px"></span>Konstantinos Ameranis</font></b></div>
<div dir="auto" style="margin:0px;font-size:16px;color:rgb(49, 49, 49);word-spacing:1px">
<font size="4"><br>
</font></div>
</div>
<div style="margin:0px"><b style="color:rgb(49, 49, 49);font-size:16px;word-spacing:1px"><font style="font-size:1.13em">Title: Practical Nearly-Linear-Time Approximation Algorithms for Hybrid and Overlapping Graph Clustering</font></b></div>
<div style="margin:0px"><b style="color:rgb(49, 49, 49);font-size:16px;word-spacing:1px"><font style="font-size:1.13em"><br>
</font></b></div>
<div style="margin:0px"><span style="margin:0px;font-size:16px;color:rgb(49, 49, 49);word-spacing:1px"><font style="font-size:1.13em"><b>Zoom: </b>[<a href="https://www.google.com/url?q=https%3A%2F%2Fuchicago.zoom.us%2Fj%2F96245648955%3Fpwd%3DeEJnV2xDSE1nZ3ErY2J3b0ZjK3dSUT09&sa=D&ust=1651938555712000&usg=AOvVaw1qcHB50_g0EIprlJDge879" title="https://www.google.com/url?q=https%3A%2F%2Fuchicago.zoom.us%2Fj%2F96245648955%3Fpwd%3DeEJnV2xDSE1nZ3ErY2J3b0ZjK3dSUT09&sa=D&ust=1651938555712000&usg=AOvVaw1qcHB50_g0EIprlJDge879">link</a>]</font></span></div>
<div style="margin:0px"><br>
</div>
<div style="margin:0px">
<div dir="auto" style="margin:0px"><font style="color:rgb(49, 49, 49);font-size:1.13em;word-spacing:1px"><span style="margin:0px;font-size:13pt"><b>Abstract:</b></span><b> </b><span style="margin:0px;font-size:12pt;font-family:"trebuchet ms", sans-serif;color:rgb(32, 31, 30);background-color:white;word-spacing:0px">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. Based on recent work with Lorenzo Orecchia.</span></font></div>
<div dir="auto" style="margin:0px"><font style="color:rgb(49, 49, 49);font-size:1.13em;word-spacing:1px"><span style="margin:0px;font-size:15px;font-family:"trebuchet ms", sans-serif;color:rgb(32, 31, 30);background-color:white;word-spacing:0px"><br>
</span></font></div>
<div dir="auto" style="margin:0px"><font face="trebuchet ms,sans-serif"><b>COVID Policy:<span style="margin:0px"> </span></b>As per university policy, masking is not currently required for in-person attendance. Please note that we will have fully masked and
social-distanced tables available to accommodate any attendees who would prefer such arrangements. Please contact us if you have any questions or feedback. </font></div>
</div>
</div>
<div style="margin:0px;font-size:15px;color:rgb(32, 31, 30);background-color:white">
<font size="4"><br>
</font></div>
<div style="margin:0px;font-size:15px;color:rgb(32, 31, 30);background-color:white">
<span style="margin:0px;font-size:large">[<a href="https://urldefense.com/v3/__https://orecchia.net/event/theory-lunch/__;!!BpyFHLRN4TMTrA!pwdRh9yLA-IBD6NCNvREJGd9Nj5jtC6_N-AowF6HSwIQeb1FPAmu0L_tAswwp_F5nRs$" target="_blank" rel="noopener noreferrer" data-auth="NotApplicable" title="https://orecchia.net/event/theory-lunch/" data-linkindex="1" style="margin:0px"><span style="margin:0px"><span data-markjs="true" class="markde4xhzh08" data-ogac="" data-ogab="" data-ogsc="" data-ogsb="" style="margin:0px">Theory</span></span> <span data-markjs="true" class="markjd1w5oi2w" data-ogac="" data-ogab="" data-ogsc="" data-ogsb="" style="margin:0px">Lunch</span> Webpage</a>]<br>
[<a href="https://urldefense.com/v3/__https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America*Chicago__;Lw!!BpyFHLRN4TMTrA!pwdRh9yLA-IBD6NCNvREJGd9Nj5jtC6_N-AowF6HSwIQeb1FPAmu0L_tAsww4XtIRnQ$" target="_blank" rel="noopener noreferrer" data-auth="NotApplicable" title="https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America/Chicago" data-linkindex="2" style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span data-markjs="true" class="markde4xhzh08" data-ogac="" data-ogab="" data-ogsc="" data-ogsb="" style="margin:0px">Theory</span></span></span></span><span style="margin:0px"> </span><span style="margin:0px"><span data-markjs="true" class="markjd1w5oi2w" data-ogac="" data-ogab="" data-ogsc="" data-ogsb="" style="margin:0px">Lunch</span></span><span style="margin:0px"> </span>Calendar</a>]</span></div>
</div>
<br>
</div>
</body>
</html>