论文研究 S Clique:属性约束的极大团枚举.pdf

极大团枚举是图论中一个基础性研究问题，并被广泛应用到社交网络等各种领域。现实生活中的图数据不仅规模大，而且顶点上往往都带有重要的属性信息。然而当前极大团枚举算法主要关注图的结构特性，很大程度上忽视了顶点上的属性信息。提出一种结合图的结构特性和顶点属性的极大团S-Clique：各顶点属性值集合的交集的大小满足最小支持度的极大团，并提出了它的应用场景。针对S-Clique问题，提出一种有效求解算法SCE-PE，其充分利用父结点等价剪枝策略。同时重新优化顶点访问次序提出SCE-PES，进一步提高SCE-PE算法性能。实验结果表明，算法SCE-PES的效率较SCE-PE提高了40%左右。