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

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