Local Motif Clustering via (Hyper)Graph Partitioning

Authors

  • Adil Chhabra Heidelberg University
  • Marcelo Fonseca Faraj Heidelberg University
  • Christian Schulz Heidelberg University

Keywords:

Combinatorial Optimization

Abstract

Local clustering consists of finding a good cluster around a seed node in a graph. Recently local motif clustering has been proposed: it is a local clustering approach based on motifs rather than edges. Since this approach is recent, most algorithms to solve it are extensions of statistical and numerical methods previously used for local clustering, while combinatorial approaches are still few and simple. In this work, we build a (hyper)graph to represent the motif-distribution around the seed node. We solve this model using sophisticated (hyper)graph partitioners. On average, our algorithm computes clusters six times faster and three times better than the state-of-the-art for the triangle motif.

Downloads

Published

2022-07-17