面向超图的极大团搜索算法

来源：计算机应用杂志2023年第8期北京时间：

作者：徐兰天, 李荣华, 戴永恒, 王国仁

单位：1.北京理工大学 计算机学院，北京 100081；2.电科云（北京）科技有限公司，北京 100041

摘要：现实世界中的实体关系大多不能用简单的二元关系来表示，而超图能很好地表示实体间的多元关系。因此，提出超图团和极大团的定义，并给出了搜索超图极大团的精确算法和近似算法。首先，分析了现有的普通图上的极大团搜索算法无法直接应用到超图上的原因。然后，基于超图的特性和极大团的定义，提出了一种新颖的保存超点间邻接关系的数据结构，并提出了一种超图上的精确极大团搜索算法。由于精确算法的速度较慢，因此结合支撑点（pivot）的剪枝思想，削减递归层数，提出了一种超图上的近似极大团搜索算法。在多个真实超图数据集上的实验结果显示，所提近似算法在找到大多数极大团的前提下，提高了搜索速度，当在3-uniform超图上，测试超图团的点数为22时，加速比达到了1 000以上。

关键词：超图,极大团,集合枚举,近似算法,支撑点

基金资助：国家自然科学基金资助项目(62072034);国家重点研发计划课题(2021YFB3301301)