Clique(团)是图论中的基础概念,指图中两两互相连接的顶点构成的子集;在无向图中,若一个团不能再加入任何顶点而保持完全连接,则称其为极大团,包含顶点数最多的团称为最大团。Clique 相关研究横跨组合数学、理论计算机科学与机器学习,其判定与枚举的计算复杂性(最大团问题是经典 NP 完全问题)使其长期是算法研究的核心对象,近年来也频繁出现在图对齐、因果发现等学习任务中。
Clique 研究的近期进展
当前焦点与观察点
目前围绕 clique 的研究呈现两条主线。其一是算法与复杂度层面:最大团求解的精确算法、参数化算法以及团枚举的工程实现仍是活跃方向,实际应用包括社交网络社区发现、生物网络分析等。其二是机器学习中的结构约束层面:像团约束用于因果发现这类工作,显示图论的组合结构正被转化为优化问题的正则项或约束条件,这一思路有望推广到图匹配、图生成等更多任务。
值得注意的观察点是:团相关的理论结果(如与色数、DNF 复杂度的联系)往往推进缓慢但影响深远,而应用侧的进展则更快、更分散。对关注者而言,判断一项 clique 研究的价值,可以看它是提供了新的复杂度刻画,还是在真实图数据上给出了可复现的求解或建模改进。