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

潘敏佳 等:面向时序图数据的快速环枚举算法 3827

t
b
按照时间戳递增的顺序读入时序边.假设边表示信息的传递过程,则由一条输入边 a ⎯⎯→ 可得:节点 a 所
拥有的信息在时间 t 传递到节点 b.由于在时间 t 之前还可能有一系列的时序边到达点 a,因此 a 所拥有的信息
里其实包含了所有在 t 之前传递给 a 的来自其他节点的信息.我们用“到达”来表示某个节点拥有的信息传递到
t
另一个节点,则 a ⎯⎯→ 表示 a 可以经由时间 t 到达 b;同时,所有可以到达点 a 的节点也可以到达点 b.定义连通
b
集合 Arrive(X)为可以通过一系列时序递增的边到达 X 的节点集,则通过这一条输入边,a 以及 Arrive(a)中的节点
会加入 Arrive(b).
以此类推,若最终在某个点 j,发现 j 的连通集合中拥有自身,则证明存在一条由 j 出发、经过递增的时序边
回到 j 的时序环.但是由于时间窗口的限制,有一些点已经超出时间窗口(时间戳过小),不应该被加入连通集合.
因此,除了记录节点编号,同时也记录由该点出发的边的时间戳,以便及时删除应当废弃的信息,避免占用过多
内存.为了实现这一点,我们在 Arrive 集合的基础上用二元组〈节点,出发时间〉来代替原先单纯的节点信息.如
Arrive(X)中包含的二元组〈n,t〉表示 n 从一条以 n 为起点的、时间戳为 t 的时序边开始,沿着时序递增路径最终
可以将信息传递给节点 X,此二元组也可以称为被 X 所拥有.
除了以上的两个信息之外,需要使用最小跳数来帮助我们处理与环路长度有关的信息.跳数的值等于经过
的时序边的数量,若点 a 到点 b 的跳数为 n,则代表点 a 经过 n 条边可以到达点 b.因此,最小跳数表示至少要经
过的边数.对于每一个〈节点,出发时间〉的二元组,附加一个最小跳数的信息,表示该节点到拥有这个二元组的节
点的最小距离(至少要经过的边数).
进一步扩展 Arrive 集合,除了〈节点,出发时间〉之外,加入最小跳数域,我们用三元组〈node,time,hop〉来进行表
示.对于每个点 s,用集合 S 来表示它所拥有的三元组集合,即:
S[s]={〈node 1 ,time 1 ,hop 1 〉,〈node 2 ,time 2 ,hop 2 〉,…,〈node n ,time n ,hop n 〉}.
用这个集合来表示 node i 从时间戳为 time i 的时序边开始,经过最少 hop i 条时序边可以到达点 s.对于一条边
t
b
a ⎯⎯→ ,若 S[a]中含有三元组〈node i ,time i ,hop i 〉,则在时间 t,node i 的信息传递到 b,使 b 中也出现一个由 node i 从
time i 出发的三元组,而这个三元组的 hop 值显然与 a 中三元组的 hop 值有关联.我们将点 b 在时间 t 根据 a 的集
合 S[a]来更新自己的三元组集合 S[b]的过程称为“继承”.则 b 在继承这个三元组时会出现两种情况.
• 若 S[b]中不含有前两个域为〈node i ,time i 〉的三元组,则插入〈node i ,time i ,hop i +1〉这样的三元组.显然,这是
由于从 a 到 b 又经过了一条边,因此,node i 到 b 的距离应该为其到 a 的距离加一,即 hop i +1;
• 另一种情况下,若 S[b]中已经含有这样的三元组,则需要将这个三元组中的 hop 值与 hop i +1 进行比较,
并取其中较小的那个,以此来确保跳数是最小的.
t
从集合 S 的定义可以得到获得环路的方法,如在处理一条 i ⎯⎯→ 的边后,发现 S[s]中出现了三元组〈s,t′,
s
hop〉,则证明找到了环路.同时,我们还能获得该环路集合的起始时间为 t′,结束时间为 t,环路最小长度为 hop.
由上述已知可能有环路由 s 从时间 t′出发最终在 t 时刻返回 s,那么对于 S[s]中所有的三元组,若其对应的时
间戳在时间 t′到 t 之间,则这个三元组中的节点就成为此环路中可能经过的节点.这样的节点们构成了候选节点
集合,表示一系列可能出现在环路中的节点的集合.这样的节点集合并不是完全准确的,它是环路中真正经过的
节点的超集.为了进一步缩小节点的范围,还需要通过 hop 值来排除一部分不会在满足要求的环路中出现的点:
t
对于一条边 a ⎯⎯→ ,若在继承来自于点 a 的三元组时,发现三元组为〈b,t′,hop〉,这说明可以形成新的环路;但如
b
果生成的新 hop 值(即 hop+1)已经大于要求的最大长度 L,则不生成五元组,这是因为通过该五元组形成的环必
然超长.若发现另一三元组不能成环并且新 hop 值大于等于 L,则不进行三元组的继承.显然,通过这个三元组里
的点到点 b 的路径均大于等于 L,因此这个三元组里的跳数域最后一定会被更新成更小的合法值或是直接被舍
弃.然而,这样的舍弃并不代表这个三元组中的节点不会成为环路的一部分,未来它仍有可能获得更小的 hop 值
而得以进入候选节点集合.
3
如图 2 所示,若当前我们想要寻找长度小于 5 的环路.在处理了时间戳 3⎯⎯→ 后,我们有 S[4]={〈3,3,1〉,
4
4
〈2,2,2〉,〈1,1,3〉}};但在处理边 4 ⎯⎯→ 时,我们不会继承〈1,1,3〉这个三元组,这是由于此时新的 hop 值将更新为 4
5
但仍未成环,因此无需将其保存下来.至此,我们找到所有五元组.需要注意:一个五元组并不代表一条环路,而是