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

Maximal clique searching algorithm for hypergraphs

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

Most of entity relationships in the real world cannot be represented by simple binary relations,and hypergraph can represent the n-ary relations among entities well.Therefore,definitions of hypergraph clique and maximal clique were proposed,and the exact algorithm and approximation algorithm for searching hypergraph maximal clique were given.First,the reason why the existing maximal clique searching algorithms on ordinary graphs cannot be applied to hypergraphs directly was analyzed.Then,based on the characteristics of hypergraph and the definition of maximal clique,a novel data structure for preserving the adjacency relations among hyperpoints was proposed,and an accurate maximal clique searching algorithm on hypergraph was proposed.As the running of the exact algorithm is slow,the pruning idea of pivots was combined with,the number of recursive layers was reduced,and an approximation maximal clique searching algorithm on hypergraph was proposed.Experimental results on multiple real hypergraph datasets show that under the premise finding most maximal cliques,the proposed approximation algorithm improves the search speed.When the number of test hypergraph cliques on 3-uniform hypergraph is 22,the acceleration ratio reaches over 1 000.