2026-07-22T22:30:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18687 2024-03-06T11:02:27Z ddc:004 open_access

Faster Local Motif Clustering via Maximum Flows Chhabra, Adil Fonseca Faraj, Marcelo Schulz, Christian local motif clustering motif conductance maximum flows max-flow quotient-cut improvement 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., it has a high number of internal edges and a low number of external edges. In this work, we propose SOCIAL, a novel 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 an average motif conductance 1.7% lower than the state-of-the-art, while being up to multiple orders of magnitude faster. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Adil Chhabra and Marcelo Fonseca Faraj and Christian Schulz 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.34 urn:nbn:de:0030-drops-186871 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.34 eng https://creativecommons.org/licenses/by/4.0/legalcode