基于灵活平衡约束的图聚类方法  

Graph Clustering Based on Flexibly Balanced Constraint

作　　者：罗辉[1] 韩纪庆[1] LUO Hui;HAN Ji-Qing(School of Computer Science and Technology,Harbin Institute of Technology,Harbin 150001)

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《自动化学报》2023年第4期778-789,共12页Acta Automatica Sinica

基　　金：国家自然科学基金(U1736210);国家重点研发计划(2017YFB1002102)资助。

摘　　要：现有的图聚类方法主要存在两方面的问题,一是对各个类规模一致的假设,在许多实际应用中并不成立;二是在处理多类聚类问题时,其所常借助的递归技术或启发式算法会影响聚类的性能.为此,本文提出一种基于灵活平衡约束的多类图聚类方法.其能够覆盖从绝对平衡约束到无平衡约束的范围,可同时处理类别规模一致和不一致的问题.为有效求解新方法中的参数,进一步提出一个紧松弛方法来使所提出的图聚类方法不仅易于求解,且在处理多类聚类问题时不必依赖递归技术,而能直接得到聚类结果.另外,本文还给出一种实现松弛图聚类的有效求解算法.在合成数据和真实数据上的实验结果表明,所提出的方法具有良好的性能.The existing graph clustering methods suffer from two main problems:first,they assume that the size of each class is the same,which is not applicable in many practical applications;second,when dealing with multi-class clustering problems,the recursive technique or heuristic algorithm that is commonly used can affect the clustering performance.To address these issues,this paper proposes a multi-class graph clustering method based on flexible balance constraints.It can cover a range from absolute balance constraints to no balance constraints and can handle both uniform and non-uniform class size problems simultaneously.To effectively solve the parameters in the new method,a tight relaxation method is further proposed to make the proposed graph clustering method not only easy to solve but also able to obtain clustering results directly without relying on recursive techniques when dealing with multi-class clustering problems.In addition,this paper also presents an effective algorithm for implementing the relaxed graph clustering.Experimental results on both synthetic and real data demonstrate that the proposed method has good performance.

关 键 词：图聚类 图分割 平衡约束 紧松弛 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]