基于属性相似性的极大团

摘要

极大团枚举是图论中一个基本问题,且在生活中具有广泛的应用.但一直以来,关于极大团的研究主要集中在图的拓扑结构上,而较少关注顶点上的信息.论文定义一种结合图的结构和属性相似性的极大团,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 this paper,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 advantage of the equivalent pruning strategy. The efficiency of the algorithm is proved by experiments.