Page 157 - 《软件学报》2020年第12期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2020,31(12):3823−3835 [doi: 10.13328/j.cnki.jos.005968] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

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

1
1
2
潘敏佳 , 李荣华 , 赵宇海 , 王国仁 1
1
(北京理工大学 计算机科学与技术学院,北京 100081)
2 (东北大学 计算机科学与工程学院,辽宁 沈阳 110819)
通讯作者: 李荣华, Email: lironghuabit@126.com

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

中文引用格式: 潘敏佳,李荣华,赵宇海,王国仁.面向时序图数据的快速环枚举算法.软件学报,2020,31(12):3823−3835.
http://www.jos.org.cn/1000-9825/5968.htm
英文引用格式: Pan MJ, Li RH, Zhao YH, Wang GR. Fast temporal cycle enumeration algorithm on temporal graphs. Ruan Jian
Xue Bao/Journal of Software, 2020,31(12):3823−3835 (in Chinese). http://www.jos.org.cn/1000-9825/5968.htm

Fast Temporal Cycle Enumeration Algorithm on Temporal Graphs
1
2
1
PAN Min-Jia , LI Rong-Hua , ZHAO Yu-Hai , WANG Guo-Ren 1
1 (School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China)
2 (School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China)
Abstract: Temporal graph is a type of graph where each edge is associated with a timestamp. In temporal graphs, a temporal cycle
denotes a loop where the timestamps of the edges in the loop follow an increasing order. Temporal cycle enumeration has a number of
real-life applications. For example, it can be applied to detect the fraud behavior in temporal financial networks. Additionally, the number
of temporal cycles can be used to characterize the topological properties of temporal graphs. Based on the 2SCENT algorithm proposed by
Rohit Kumar et al. in 2018, a new temporal cycle enumeration algorithm is proposed which uses additional cycle information to prune the
search space. Specifically, the proposed algorithm is a two-stage algorithm. First, the algorithm traverses the temporal graph to identify all
root nodes that probably form temporal cycles, as well as the corresponding time and length information of the cycles. Second, the
algorithm performs a dynamic depth first search using the above information to find all valid temporal cycles. Extensive experiments are
conducted on four real-life datasets, using 2SCENT as the baseline algorithm. The result shows that the proposed algorithm reduces the
running time over the 2SCENT algorithm by 50 percent.
Key words: temporal graph; temporal cycle; constraint cycle; prune; cycle enumeration algorithm

∗ 基金项目: 国家自然科学基金(61772346, U1809206, 61772124, 61332006, 61332014, 61328202, U1401256)
Foundation item: National Natural Science Foundation of China (61772346, U1809206, 61772124, 61332006, 61332014, 61328202,
U1401256)
收稿时间: 2019-07-18; 修改时间: 2019-09-10; 采用时间: 2019-11-25