Parameter-light algorithms for improving hypermodularity-based community detection

Abstract

Abstract Community detection is a central problem in network science, traditionally performed on graphs, often via modularity maximization. Yet, many real-world systems inherently involve higher-order interactions between more than two entities, naturally modeled as hypergraphs. In such contexts, pairwise projections obscure higher-order structure and may lead to misleading communities. Recent works thus addressed higher-order community detection, with hypermodularity as one promising candidate. The state-of-the-art algorithm h-louvain [Kaminski et al., J. ComNetw 2024] mixes greedy optimization techniques for both modularity and hypermodularity in a multilevel scheme. While being effective with default parameters, the algorithm lacks guidance on how to combine the two objectives and thus needs parameter tuning. This parameter tuning step uses probabilistic strategies such as Bayesian Optimization Technique (BOT), resulting in a very significant overhead in running time. In this paper, we propose three algorithmic variants of h-louvain to recover communities of high accuracy without the need for time-consuming searches of mixing parameters. Our variants consist of new ideas for creating starting solutions for greedy multilevel algorithms and additional post-processing steps inspired by the community detection algorithm leiden [Traag et al., SciRep 2019] for graphs. In extensive experiments with over 50 real-world and randomly generated graphs, we show that across nearly all test cases, a member of our algorithm suite matches or surpasses h-louvain w. r. t. Asymmetric RMI; hence, they provide a more faithful community representation than the state of the art.