Abstract: Maximal clique enumeration is a fundamental problem in graph theory and widely applied to various fields such as social networks. However, in reality world, the graph not only is huge but also carries important attribute information on the vertex. The current algorithms focus on the structure, largely ignoring the attribute content on the vertex. This paper presents S-Clique combining both the characters of structure and attribute information. The length of the intersection of each vertex attribute value set meets the minimum support. For S-Clique problem, it proposes an efficient algorithm SCE-PE, which makes full use of the parent node equivalence pruning strategies. Meanwhile it re-optimizes vertex visits order to improve the performance of the algorithm. The experimental results show that algorithm of SCE-PE improves the efficiency by 40% compared with the basic algorithm.

Key words: graph data, maximal clique, attribute constraints, support

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

关键词: 图数据, 极大团, 属性约束, 支持度