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

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

¾ 在第 1 个阶段(可以被称作源检测阶段),它找到所有的候选信息四元组,其中包括环路顶点、开
始时间、结束时间、候选节点集合.为了适应更大的图,该算法还引入了布隆过滤器来完成这一
阶段的处理;
¾ 在第 2 个阶段,利用每一组候选信息进行动态深度优先搜索.为了避免不必要的多次重复搜索,
引入了时序图中的“关闭时间”这一概念来进行剪枝.为了处理那些有多重边、高度重复活动的
网络,该算法还使用“路径束”进行搜索,使效率得到了提升.
2 问题描述及相关定义

2.1 时序边和时序图
时序边是一条带有时间戳的有向边,表示成三元组(起点,终点,时间戳),其中,时间戳为非负实数,本文中时
间戳的单位为秒.一系列时序边的集合被称为时序图 G(V,E).时序图 G 建立在点集合 V 上,由(u i ,v i ,t i ),i=1,2,…,m
构成.u i ,v i ∈V,m=|E|,为边集合的大小.
2.2 时序环
时序环是由一组时序边 p=〈(u,v 1 ,t 1 ),(v 1 ,v 2 ,t 2 ),…,(v n−1 ,u,t n )〉组成的环路,其中,t 1 <t 2 <…<t n .在本文中,我们要寻
找的环是简单时序环,即环路中不含有重复经过的节点.
2.3 持续时间和时间窗口
对于找到的一条路径 ⎯⎯→⎯⎯→u 1 t v 1 2 t 2 →v ...⎯ ⎯ n t →u ,我们定义它的持续时间为 t n −t 1 ,它的长度为 n.时间窗
口是指我们所要寻找的最大持续时间值.若时间窗口限制为δ,则要求 t n −t 1 ≤δ.
在本文中,对于给定的时间窗口,我们只寻找持续时间小于等于时间窗口的简单时序环.
2.4 长度限制的查询
对于某个时间窗口ω,若用户只要求查找长度小于 L 的环路,则将这样的查询称为长度限制为 L 的查询,这
样的环路被称为约束时序环.当 L 足够大时,获得的是全部的环路.
2.5 问题定义

本文具体研究的问题是:对于给定的时序图 G(V,E)、时间窗口ω、长度限制 L,枚举所有长度 l<L、持续时
间 w≤ω的简单约束时序环.

3 新型环枚举算法设计

在最朴素的算法下,直接对图上的每一个顶点进行深度优先搜索或广度优先搜索,在很多情况下会产生巨
大的损耗,不仅在时间上远远不能满足现实的需求,也极容易造成空间的不足,使得系统崩溃.这主要是由于其
中一大部分的搜索是无效的,并不能对形成环路起到作用,但是它们却会被不断存储下来.因此,如果我们能知
道环路中会经过的顶点以及大致时间再进行搜索,就可以降低搜索的复杂度.
在寻找环的过程中,常使用两阶段的算法:在第 1 阶段确定可能成为环的结构,在第 2 阶段对这些结构进行
进一步确认.本文基于 2SCENT 算法,使用两个阶段的方法来寻找满足要求长度的简单环路:在第 1 个阶段,遍历
所有的时序边,获得环路起点、环路的起始时间、环路的结束时间、可能经过的节点集合、环路最小跳数这 5
个信息;在第 2 阶段,利用以上信息,进行动态深度优先搜索,结合剪枝技术,最终获得要求的环路.

3.1 获取五元组算法
产生候选五元组模块的五元组是指〈环路起点 s,环起始时间 ts,环结束时间 te,候选节点集合 candidates,最
小跳数 hop〉.其中,候选节点集合是环路中可能会经过的节点的集合,最小跳数是指通过该五元组进行搜索能获
得的环路的最小长度,它可以给出一系列环路的长度下限.