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

来源：计算机科学与探索杂志2017年第9期北京时间：

作者：王章辉，赵宇海，王国仁，李源

单位：东北大学 计算机科学与工程学院，沈阳 110819

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

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