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