Seminar: Sami Davies (Simons Institute & UC Berkeley)

Zoom link: 
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09 
(Meeting ID: 849 0964 5595, Passcode: 772448)

Speaker: Sami Davies (Simons Institute & UC Berkeley)

Title: Combinatorial LP-norm Correlation Clustering

Abstract:
Correlation clustering is a natural model arising from community detection problems. A complete graph is given with each edge labeled as either positive or negative; two vertices are connected by a positive edge when they are “similar" and want to be clustered together, while a negative edge indicates vertices that are “dissimilar" and want to be in different clusters. The goal is to find a clustering that minimizes an objective capturing the edges’ disagreements with respect to the clustering. In this talk, we focus on objectives that minimize the $\ell_p$-norm of the disagreement vector, which is a well-studied class of objective. Our work provides the first purely combinatorial constant factor approximation algorithms for these problems. Additionally, we provide an algorithm that produces a single clustering solution that is *simultaneously* constant approximate for all $\ell_p$-norms of the disagreement vector. This proves that minimal sacrifice is needed in order to optimize different local norms. The combinatorial nature of our techniques lend to significant run-time improvements, with empirical results showing that our algorithms scale to larger networks that were effectively intractable for previous algorithms.

Video:

Slides:

Slides