单图中的近似频繁子图挖掘算法

• 作者: 林欣 窦建凯 胡文心
• 来源期刊: 华东师范大学学报（自然科学版）
• 学科: 工学
• 关键词: 近似 图 频繁子图挖掘 剪枝
• 年，卷（期）: 2019,（6）
• 所属期刊栏目: 计算机科学
• 页码范围: 73-87
• 页数: 15页
• 分类号: TP391.4
• 字数: 8762字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-5641.2019.06.008

摘要

图数据的挖掘工作是数据挖掘工作中的重要组成部分,已经有许多人在这个领域进行了深入的研究.由于数据获取不可避免噪音数据,故在挖掘频繁图时考虑近似十分重要.然而许多此前的工作只考虑了子图间编辑距离(Graph Edit Distance,GED)的绝对值,而没有考虑子图间编辑距离与子图大小的相对关系.提出了一种在单图中进行近似频繁子图挖掘的新算法,并在计算近似程度时考虑当前子图的大小.该算法通过对近似频繁子图的大小上限进行预测,并通过局部反单调性进行剪枝,提高了算法的效率.实验表明,该算法能够挖掘出传统算法无法发现的近似频繁子图,且相比对比算法具有更好的时间性能.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	胡文心	华东师范大学计算中心	15	293	6.0	15.0
2	林欣	华东师范大学计算机科学与技术系	9	129	5.0	9.0
3	窦建凯	华东师范大学计算机科学与技术系	1	0	0.0	0.0