基于联合意义度量的Top-K图模式挖掘

摘要：

提出了一个新的研究问题:如何挖掘Top-K图模式,联合起来使某个意义度量最大化.利用信息论的概念,给出了两个具体问题的定义MES和MIGS,并证明它们是NP-难.提出了两个高效算法Greedy-TopK和Clus-ter-TopK.Greedy-TopK先产生频繁子图,然后按增量贪心方式选择K个图模式.Cluster-TopK先挖掘频繁子图的一个代表模式集合,然后从代表模式中按增量贪心方式选择K个图模式.当意义度量满足submodular性质时,Greedy-TopK能提供近似比保证.Cluster-TopK没有近似比保证,但比Greedy-TopK更高效.实验结果显示,在结果可用性方面,文中提出的Top-K挖掘优于传统的Top-K挖掘.Cluster-TopK比Greedy-TopK快至少一个数量级.而且,在质量和可用性方面,Cluster-TopK的挖掘结果非常类似于Greedy-TopK的挖掘结果.

关键词：图挖掘、图数据库、频繁子图、代表模式、联合熵、信息增益

所属期刊栏目：33

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

资助基金：国家"九七三"重点基础研究发展规划项目基金2006CB303005;国家自然科学基金60533110,60773063

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

页数：共16页

页码：215-230