面向时序图数据的快速环枚举算法

• 作者: 潘敏佳 李荣华 赵宇海 王国仁
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 时序图 时序环 约束环 剪枝 环枚举算法
• 年，卷（期）: 2020,（12）
• 所属期刊栏目: 数据库技术
• 页码范围: 3823-3835
• 页数: 13页
• 分类号: TP311
• 语种: 中文

摘要

时序图数据是一类边上带有时间戳信息的图数据.在时序图数据中,时序环是边满足时间戳递增约束的回路.时序环枚举在现实中有着很多应用,它可以帮助挖掘金融网络中的欺诈行为.此外,研究时序环的数量对于刻画不同时序图的特性也有重要作用.基于2018年由Rohit Kumar等人提出的时序环枚举算法(2SCENT算法),提出一种通过添加环路信息来削减搜索空间的新型时序环枚举算法.所提出的算法为一个两阶段的算法:1)首先,通过遍历原图获得所有可能会形成环路的节点,以及相应的时间和长度信息;2)然后,利用以上信息进行动态深度优先搜索,挖掘所有的满足约束条件的环.在4个不同的真实时序图数据集上进行了大规模的实验,并以2SCENT算法作为基准对算法进行了对比.实验结果表明,所提出的算法较之前最好的2SCENT算法要快50％以上.