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

• 作者: 刘勇 李建中 高宏
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 图挖掘 图数据库 频繁子图 代表模式 联合熵 信息增益
• 年，卷（期）: 2010,（2）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 215-230
• 页数: 16页
• 分类号: TP311
• 字数: 17727字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2010.00215

摘要

提出了一个新的研究问题:如何挖掘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的挖掘结果.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘勇	哈尔滨工业大学计算机科学与技术学院	120	1324	19.0	28.0
2	李建中	哈尔滨工业大学计算机科学与技术学院	237	6003	33.0	72.0
3	高宏	哈尔滨工业大学计算机科学与技术学院	109	1574	18.0	36.0