基于属性相似性的极大团

Maximal Clique Based on Attribute Similarities

极大团枚举是图论中一个基本问题,且在生活中具有广泛的应用。但一直以来,关于极大团的研究主要集中在图的拓扑结构上,而较少关注顶点上的信息。论文定义一种结合图的结构和属性相似性的极大团,SA-clique,并提出了它的应用场景。针对该SA-clique查询,论文提出一种其充分利用等价点剪枝策略有效求解算法SCQuery。通过实验证明该算法具有较高的效率。

Maximal clique enumeration is a fundamental problem in graph theory and widely applied to various fields Howev？er,many existing graph clustering methods mainly focus on the topological structure,but largely ignore the vertex properties. In thispaper,a novel maximal clique,SA-clique,based on both structural and attribute through a attribute similarities measure is pro？posed,and its application scenarios is present. Meanwhile,an efficient algorithm SCQuery is proposed,which takes full advantageof the equivalent pruning strategy. The efficiency of the algorithm is proved by experimens.