多样性度量的Top-K区分子图挖掘

摘要：

区分子图可以用来描述复杂的图数据结构和构建高效的图分类模型.提出了多样性度量的Top-K区分子图挖掘问题,避免了挖掘结果之间出现高度相关的子图模式,提高了区分子图模式的可用性.通过组合图结构相似性与支持集相似性约束,给出图模式的多样性度量标准.提出两个高效算法Greedy-TopK和Leap-TopK挖掘多样性度量的Top-K区分子图.Greedy-TopK算法采用两阶段的增量式贪婪方法快速挖掘K个区分子图模式.Leap-TopK算法通过在挖掘过程中限制扩展结构相似的图模式,实现了跳跃搜索子图模式空间.实验结果表明,Leap-TopK算法的效率明显优于Greedy-TopK算法;在可用性方面,利用Leap-TopK算法与Greedy-TopK算法挖掘结果构建的图分类器具有相似的分类精度,且都优于传统区分子图挖掘算法产生的结果.

关键词：图挖掘、图分类、子图模式、区分子图、多样性

所属期刊栏目：11

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

资助基金：The National Natural Science Foundation of China under Grant Nos. 61272182, 61332014, 61173029;the Key Program of National Natural Science of China under Grant No. U1401256;the Fundamental Research Funds for the Central Universities of China under Grant No. N150402002

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

页数：共10页

页码：1379-1388