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

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

[7]
模体(motif) 可以用于衡量某一个模式在不同时间规模下出现的频率,这样的模式具有一定的现实意义.
模体对于理解图的结构和系统的功能也有着重要的意义.环路就是一种重要的模体,显然,它是指一系列节点在
某一时间段内经过一系列交互回到出发点的行为.因此,寻找时序环也可以被认为是在寻找时序图中的一系列
模体.
[8]
Paranjape 等人 提出了对简单模体进行计数的方法,使用的时间接近于线性.该算法寻找的主要是二元模
体和三元模体,其中当然也包括了三元环这种情况.然而,由于环路计数与环路枚举有较大的区别,这个算法虽
然对计算小的模体数量具有意义,却不适用于更为广泛的情况.
环路计数和环路检测是关于环路的两个枚举问题:环路计数要求统计图中所有环路的条数;环路检测则是
关于如何具体构造这些环路,给出详细的路径信息.通过环路检测,我们一定可以获得环路的计数值;但是反过
来,环路计数的值却往往对环路检测的实现起不到什么作用.
在静态图上寻找环路是一个经典的问题,从上世纪 70 年代开始就有了研究 [9−11] .解决问题的算法主要有
Tiernan 算法 [12] 、Weinblatt 算法 [13] 等.目前,解决这个问题的最有效方案是 Johnson 算法 [14] .Johnson 算法可以在
静态有向图中找到所有简单环路,同时保证时间复杂度上限为 O((n+e)(c+1)),空间复杂度上限为 O(n+e),其中,n
代表节点个数,e 代表边的条数,c 代表图中简单环路的个数.
Johnson 算法用深度优先搜索的方式搜索有向图,与此同时加入剪枝,尽可能地避免当前节点向不可能形成
环路的节点进行搜索,因此大大提升了效率.剪枝主要通过对节点的封锁/解锁来进行处理.如当前的环路源点
为 a,若由 a 经过一系列路径搜索到 b 之后,发现 b 并不能通过后续的搜索回到 a,则 b 被暂时封锁.这样一来,就
可以避免未来由 b 出发的无效搜索.
但是对于无向图上的环路枚举,Johnson 算法不是最优的.Ferreira 等人提出了一个更优的算法 [15] :令 C(G)
为图 G 上的所有环路,|c|为 C(G)中每一条环路的边的数量,则 Ferreira 算法所需的时间为 ( +∑ cC ()G ||c ) .其
O m
∈
中,O(m)是读图所必须的时间,而 ( ∑ cC ()G ||c ) 是输入环路所必须的时间.因此,该算法是渐进最优的.
O
∈
综上所述,类似的算法在静态图上已经有了良好的表现,但是它们并不能被直接用于带有时序的交互网络.
这是由于静态图中没有附加其他信息,整个图更为简单;而时序图上的环在普通环的基础上,要求时序递增,提
升了复杂度.再者,时序图上两点之间极有可能出现多条带有不同时间戳的时序边,而在静态图上,两个点之间
往往可以简化为只有一条边.
由于近年来对时序图网络研究的兴起,以及对时序环重要性认识的不断提高,已经有一些专家学者针对时
序环进行了研究.阿里巴巴在 2018 年提出了限制条件下的实时环路检测 [16] ,其中的限制包括长度限制、重要性
限制等.该算法针对不断更新的时序图网络,按照用户的要求,将符合条件的环路返回给用户.算法中定义了热
点(hotpoint)的概念,表示一些交互活动频繁、重要性较高的点,而这些热点往往是带来较大查询时延的瓶颈.于
是,算法为这些热点维护特殊的索引,这样一来,热点带来的查询复杂度就可以降低.然而,这个算法查询的环路
并不是严格遵循时序递增的时序环,因此该技术不能用于本文的研究问题.
与本文所研究的问题最相关的工作有两个.
• 2017 年,Kumar 和 Calders 提出了一种较为朴素的时序环枚举算法 [17] ,该算法在研究时序环的同时,提
出了一个论断,认为可以使用简单时序环以及它们的数量分布情况来表现时序网络里的信息流动.具
体而言,该算法枚举窗口内所有可能的时序路径来寻找时序环,它记录所有当前已经形成的时序路径,
并将新的点不断追加到之前的路径上,直到环路形成.该算法容易理解也便于实现,但是并不适用于大
图,当路径越来越多,该算法会占用过多的内存;
• 2SCENT [18] 算法是 2018 年由 Kumar 等人提出的时序环枚举算法,也是目前为止最快的时序递增环路
枚举算法,它借鉴了 Johnson 算法中的思想,是一个适用于时序图的 Johnson 算法衍生.相对于朴素的算
法,它达到了 300 倍以上的时间提升,同时能处理的图的大小也获得了巨大的增加.2SCENT 算法是一
个两阶段的算法.