科研之友
微信
新浪微博
Facebook
分享链接
摘要
现实世界中的实体关系大多不能用简单地的二元关系来表示，而超图能更好的地表示实体间的多元关系。因此，提出一种超图团和极大团的定义，并给出了搜索超图极大团的精确算法和近似算法。首先，分析了现有的普通图上的极大团搜索算法无法直接应用到超图上的原因；然后基于超图的特性和极大团的定义，提出了一种新颖的保存超点间邻接关系的数据结构，并提出了一种超图上的精确极大团搜索算法；由于精确算法的速度较慢，进一步结合支撑点（pivot）的剪枝思想，削减递归层数，提出一种超图上的近似极大团搜索算法。通过在多个真实超图数据集上进行实验，结果表明近似算法可以在找到大多数极大团的前提下，对精确算法的加速比达到100以上。
-
单位北京科技; 北京理工大学
