深圳大学学报（理工版）2025，Vol.42Issue(1)：68-76,9.DOI:10.3724/SP.J.1249.2025.01068
MSHC:一种多阶段超图聚类算法
MSHC:a multi-stage hypergraph clustering algorithm
摘要
Abstract
As a high-dimensional extension of ordinary graphs,hypergraphs can more flexibly reflect high-order complex relationships between nodes.Hypergraph clustering aims to discover complex high-order correlations in powerful hypergraph structures.In response to challenges faced by current hypergraph clustering algorithms,such as extremely high complexity,unstable clustering results,and the tendency to fall into local optima,a multi-stage hypergraph clustering algorithm denoted as MSHC is proposed based on the idea of hypergraph partitioning.This algorithm divides the hypergraph clustering process into three stages:hypergraph reduction,hypergraph initial clustering,and optimization migration.In the first stage,a fast reduction method that preserves the hypergraph structure is proposed to reduce the complexity of subsequent algorithms.In the second stage,a similarity measurement method between hypergraph nodes based on set pair analysis theory is introduced,and hierarchical clustering algorithm is applied for initial clustering.Four different cluster merging strategies are employed to increase the diversity of clustering schemes.In the final stage,the genetic algorithm is applied to obtain the optimal hypergraph clustering scheme.Comparative experiments are conducted with two traditional hypergraph clustering algorithms on three data sets with different sizes.Experimental results show that the hypergraph modularity index of the MSHC algorithm is improved by 0.079 and 0.077on the Songs_genres and Papers_keywords datasets respectively,and is only reduced by 0.006 on the Movies_genres dataset.关键词
数据处理/超图聚类/遗传算法/集对分析理论/超图约简/多阶段聚类/超图模块度Key words
data processing/hypergraph clustering/genetic algorithm/set pair analysis theory/hypergraph reduction/multi-stage clustering/hypergraph modularity分类
信息技术与安全科学引用本文复制引用
张春英,王静,刘璐,兰思武,张庆达..MSHC:一种多阶段超图聚类算法[J].深圳大学学报（理工版）,2025,42(1):68-76,9.基金项目
Basic Scientific Research Business Expenses of Hebei Provincial Universities(JST2022001) 河北省属高校基本科研业务费资助项目(JST2022001) （JST2022001）
