Title: Local Clustering on Complex Graphs and Complex Hypergraphs

Abstract:

The objective of local or seeded clustering is to identify a dense community situated near specific seed nodes. Although conventional graph clustering research predominantly focuses on discrete graphs—defined as unweighted, undirected structures lacking self-loops—actual-world networks often exhibit greater complexity. This study extends the foundational Andersen-Chung-Lang (ACL) algorithm, which does not rely on approximation, to accommodate more intricate graph types. We demonstrate that its quadratic optimality properties hold for a broader spectrum of complex graphs, encompassing weighted, directed, and self-looped graphs, as well as hypergraphs characterized by edge-dependent vertex weights. By utilizing PageRank, we introduce two distinct methods: GeneralACL for standard graphs and HyperACL for hypergraphs. We establish that, provided two mild conditions are satisfied, both proposed algorithms are capable of locating clusters that are quadratically optimal with respect to conductance. Furthermore, we present experimental results that support our theoretical conclusions. The source code for this work can be accessed at https://github.com/iDEA-iSAIL-Lab-UIUC/HyperACL.

Source: arXiv Generated at: 2026-06-04 00:00:00 UTC