提出超图聚类新方法，兼顾满足边数与公平性
Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
- 设计首个超图满意边最大化近似算法
- 改进图结构最优近似因子，突破此前局限
- 引入平衡与公平目标，拓展聚类评价维度
我们研究边染色超图的聚类框架，目标是根据多路交互的主要类型对对象进行聚类（即着色）。经典目标是通过节点着色最小化不满足的超边数量——即包含颜色不匹配节点的超边。本文提出超越该目标的多个新方向：首先，针对最大化满意边这一等价但更难近似的任务，首次提出超图的近似算法，并进一步优化，获得图结构上最佳近似因子；随后，引入融合平衡与公平性的新目标函数，给出新的复杂性结果、近似算法及固定参数可解性分析。
原文摘要 · Abstract (English)
We consider a framework for clustering edge-colored hypergraphs, where the goal is to cluster (equivalently, to color) objects based on the primary type of multiway interactions they participate in. One well-studied objective is to color nodes to minimize the number of unsatisfied hyperedges -- those containing one or more nodes whose color does not match the hyperedge color. We motivate and present advances for several directions that extend beyond this minimization problem. We first provide new algorithms for maximizing satisfied edges, which is the same at optimality but is much more challenging to approximate, with all prior work restricted to graphs. We develop the first approximation algorithm for hypergraphs, and then refine it to improve the best-known approximation factor for graphs. We then introduce new objective functions that incorporate notions of balance and fairness, and provide new hardness results, approximations, and fixed-parameter tractability results.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。