2023/05/28 by Alex Crane, Crane, Alex, Brian Lavallee +5 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Bioinformatics and Genomic Networks #Complex Network Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2305.17598
openalex publication_date 2023/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A recent trend in data mining has explored (hyper)graph clustering algorithms for data with categorical relationship types. Such algorithms have applications in the analysis of social, co-authorship, and protein interaction networks, to name a few. Many such applications naturally have some overlap between clusters, a nuance which is missing from current combinatorial models. Additionally, existing models lack a mechanism for handling noise in datasets. We address these concerns by generalizing Edge-Colored Clustering, a recent framework for categorical clustering of hypergraphs. Our generalizations allow for a budgeted number of either (a) overlapping cluster assignments or (b) node deletions. For each new model we present a greedy algorithm which approximately minimizes an edge mistake objective, as well as bicriteria approximations where the second approximation factor is on the budget. Additionally, we address the parameterized complexity of each problem, providing FPT algorithms and hardness results.