Minisymposium Presentation

Local clustering aims to identify a cluster within a given graph that includes a designated seed node or a significant portion of a group of seed nodes. This cluster should be well-characterized, i.e., in the context of motifs, such as edges or triangles, it should have a high number of internal motifs and a low number of external motifs (motif conductance). In this talk, we present SOCIAL, a state-of-the-art algorithm for local motif clustering which optimizes for motif conductance based on a local hypergraph model representation of the problem and an adapted version of the max-flow quotient-cut improvement algorithm (MQI). In our experiments with the triangle motif, SOCIAL produces local clusters with superior solution quality among alternate approaches, while being up to multiple orders of magnitude faster.