S-Clique:属性约束的极大团枚举

摘要：

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

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

所属期刊栏目：54

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金61462050,61562054;云南省自然科学基金2013FZ020,KKSY201303095;高等学校学科创新引智计划111计划B12028

在线出版日期：2018-03-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：66-71