Research Article
High-Order Local Clustering on Hypergraphs
@ARTICLE{10.4108/eetsis.7431, author={Jingtian Wei and Zhengyi Yang and Qi Luo and Yu Zhang and Lu Qin and Wenjie Zhang}, title={High-Order Local Clustering on Hypergraphs}, journal={EAI Endorsed Transactions on Scalable Information Systems}, volume={11}, number={6}, publisher={EAI}, journal_a={SIS}, year={2024}, month={12}, keywords={Local Clustering, Hypergraphs, Conductance}, doi={10.4108/eetsis.7431} }
- Jingtian Wei
Zhengyi Yang
Qi Luo
Yu Zhang
Lu Qin
Wenjie Zhang
Year: 2024
High-Order Local Clustering on Hypergraphs
SIS
EAI
DOI: 10.4108/eetsis.7431
Abstract
Graphs are a commonly used model in data mining to represent complex relationships, with nodes representing entities and edges representing relationships. However, graphs have limitations in modeling high-order relationships. In contrast, hypergraphs offer a more versatile representation, allowing edges to join any number of nodes. This capability empowers hypergraphs to model multiple relationships and capture high-order information present in real-world applications. We focus on the problem of local clustering in hypergraphs, which computes a cluster near a given seed node. Although extensively explored in the context of graphs, this problem has received less attention for hypergraphs. Current methods often directly extend graph-based local clustering to hypergraphs, overlooking their inherent high-order features and resulting in low-quality local clusters. To address this, we propose an effective hypergraph local clustering model. This model introduces a novel conductance measurement that leverages the high-order properties of hypergraphs to assess cluster quality. Based on this new definition of hypergraph conductance, we propose a greedy algorithm to find local clusters in real time. Experimental evaluations and case studies on real-world datasets demonstrate the effectiveness of the proposed methods.
Copyright © 2025 J. Wei et al., licensed to EAI. This is an open access article distributed under the terms of the CC BY-NCSA 4.0, which permits copying, redistributing, remixing, transformation, and building upon the material in any medium so long as the original work is properly cited.