软件学报

作者：潘敏佳，李荣华，赵宇海，王国仁

单位：潘敏佳，北京理工大学 计算机科学与技术学院, 北京 10008111,李荣华，北京理工大学 计算机科学与技术学院, 北京 10008102,赵宇海，东北大学 计算机科学与工程学院, 辽宁 沈阳 11081903,王国仁，北京理工大学 计算机科学与技术学院, 北京 10008104

关键词：时序图;时序环;约束环;剪枝;环枚举算法

基金：国家自然科学基金（61772346，U1809206，61772124，61332006，61332014，61328202，U1401256）

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

来源：2020年第12期

《软件学报》期刊编辑部

查看软件学报杂志2020年第12期