面向时序图数据的快速环枚举算法-潘敏佳，李荣华，赵宇海，王国仁.pdf

上善若水

502

13页

1次

2022-05-24

免费下载

软件学报 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

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

∗

潘敏佳

李荣华

赵宇海

王国仁

(北京理工大学计算机科学与技术学院,北京 100081)

(东北大学计算机科学与工程学院,辽宁沈阳 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 algorith m 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.ht m

Fast Temporal Cycle Enumeration Algorithm on Temporal Graphs

PAN Min -Jia

, LI Rong-Hua

, ZHAO Yu-Hai

, WANG Guo-Ren

(School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China)

(School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China)

Abstra ct : 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 b e applied to detect the fr aud behavior in t emporal financial networks. Additionally, the number

of temporal cycles can b e used to characteri ze the topolo gical prop erties of temporal graphs. Based on th e 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, th e algorithm traverses th e 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 d ynamic depth first search using the above information to find all valid temporal cycles. Extensiv e 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 Found ation of China (6177234 6, U1809206, 61772124, 61332006, 61332014, 6132820 2,

U1401256)

收稿时间: 2019-0 7-18; 修改时间: 2019-09-10; 采用时间: 2019-11-25

3824

Journal of Software 软件学报 Vol.31, No.12, December 2020

在现实世界中,很多图数据上都带有时序信息,例如电信话务网络、金融交易网络、道路交通网络和在线

社交网络等等.而环路作为一种特殊的结构,在各种图中都频繁出现,并且拥有着重要的意义.目前,时序环已经

开始被应用于多个领域,有了多种实际应用.比如在生物领域,时序环可以表示某种生物反馈机制

[1]

;在金融领

域,检测出的时序环可能代表了某一种金融诈骗行为

[2]

.攫取时序图结构,可以帮助我们挖掘未知的图模式.图 1

展示了两个具有不同含义的时序图.

• 图 1(a)为用户之间进行金钱交易的时序图,其中的时序边表示某一用户在某一时间向另一用户进行款

项支付.可以看到,买家 1 和买家 2 分别处于不同的时序环中,表明它们参与到了不同的有第三方参与

的欺骗行为中,具体可以表现为阿里巴巴中某些不正当的刷单行为;

• 图 1(b)表示细胞之间某些信息通过介质进行传递,最终由细胞 D 传往细胞 A 的时序边表示信息的反馈.

可见:在不同背景的时序图下,时序环拥有不同的意义.但在某些情形中,用户需要的并不是所有的环路,而

是某些长度的环路.最朴素的算法需要从每个点进行小于等于该长度的深度优先搜索,在大多数情况下,费时并

且会占用大量空间.本文在 2SCENT 算法的基础上提出一种两阶段的环路枚举算法,相对于 2SCENT,它减少了

搜索所需的时间,并且在大多数情况下都能显著节约存储空间.

Fig.1 Te mporal cycles with different meanings

图 1 具有不同意义的时序环

本文的创新贡献主要包括以下两个方面.

(1) 提出了一种长度限制下的环路枚举新算法.该算法通过引入新型的剪枝技术,允许用户快速获得某一

长度以内的所有时序环;

(2) 在 4 个真实的时序图上进行了大量的对比实验,并详细分析了算法起效的原因,以及在不同情况下的

表现.实验结果表明,本文提出的算法较过去的 2SCENT 算法在性能上能够提升 50%以上.

本文第 1 节介绍时序环枚举的相关工作.第 2 节给出一些定义以及问题描述.第 3 节介绍环枚举算法的具

体设计.第 4 节在 4 个真实数据集上使用 2SCENT 算法和我们的算法来比较算法的运行效率.第 5 节总结全文

并且给出未来的工作.

1 相关工作

时序图

[3]

是由节点和带有时间戳的边组成的集合,相对于静态图而言,它加入了“时序”的概念,因此两个节

点之间的多条边不能简单地视作一条.针对时序图,有很多亟待处理的问题.时序图上的查询处理问题

[4]

主要有

路径问题、可达性问题和精确匹配问题等;时序图挖掘问题主要有最小生成树问题、稠密子图挖掘问题和 k-

匿名问题等等.

除此之外,由于在时序图上的子图会随着时间进行演化,而这种演化模式会随着时间推移不断出现,因此出

现了对“频繁演化模式”的算法研究

[5]

,以及找到 k 个最有影响力的顶点,使得信息得到最大化传播的影响力最大

化算法研究等等

[6]

.可以说,研究时序图中隐含的信息,能够提升我们对信息网络的认知水平.

of 13

免费下载

软件学报计算机技术

关注

评论