Bi-BFS：一种新颖的基于时序图的可达性算法

刘凯洋，范新灿

（深圳职业技术学院计算机工程学院，深圳 518055）

Bi-BFS：一种新颖的基于时序图的可达性算法

刘凯洋，范新灿

（深圳职业技术学院计算机工程学院，深圳 518055）

随着海量数据的迅猛增长以及大数据时代的开启，涌现出大量的基于超大规模时序图的应用，并对经典图论算法中的可达性问题提出新的挑战。传统的可达性算法缺少对非静态性、时效性的充分考虑，因此在时序图上的运行可能导致错误结果，并且不能充分利用时序图的特性提升运行效率。考虑到时序性对于时序图的重要性，提出一种新颖的算法Bi-BFS，通过充分利用结点之间的时序性约束，并借助于现有的高效索引结构，可以快速地确定超大规模时序图上任意两个结点之间的可达性。与同类算法之间的实验表明，新算法的运行效率得到较大的提升。

可达性；时序图；算法

0 引言

随着各种智能移动设备的爆发性增加，以及新型社交网络、基于位置的服务提供和智能交通系统等网络应用的不断涌现，大量的非结构化数据采用基于图的存储方式。与传统应用产生的数据相比，这些应用产生的数据具有很强的时效性特征，我们称之为时序图。时序图中的边不是持续存在，而是具有时效性，可能只在某些特定时间段存在，如公共交通工具的发车时间，论文之间的相互引用，和分布式计算环境下各个节点之间的连通性等。如果一张图上的边和节点的存在是持续的，不会随着时间变动，我们将其称为静态图。通过删除所有的时序信息，我们可以将一张时序图转换为对应的静态图。

1 时序图相关研究

对于时序图的各种应用而言，一个基础的问题是如何确定时序图中的两个节点之间的可达性。以社交网络为例，可能的研究主题是如何确定对象之间的影响度，从而能够实现更高效的广告投放，或者更准确的民意调查预测。假设A和B都曾经向C成功推荐过产品，但是A是一年之前向C推荐过，而B与C的互动发生在最近一个月之内。显而易见，与A相比，在当前时间节点B对于C的影响力会更高。如果忽略时效性，则会错误的认为对于C而言，A和B具有相同的影响度。另外一个例子是公众信息传播模型，通过记录对象之间的社交互动信息，确定信息如何在公众之间传播。

图1（a）中展示了一个公众互动系统的示例时序图，节点表示对象，边表示对象之间的互动活动，如微信转发。为简化表示，我们用整数表示时间戳。在图1（a）中，边（A，B，1）表示B于时间1引用了A的微信文章（为简单表述，以下我们称为B引用了A。现实生活中两个对象之间的社交互动联系可能非常频密，如G与C之间的三条边所示，表示C分别于时间1，5，9引用了G。一个可能的查询是判断对于时间段[2，5]，A与C是否有过直接或者间接的信息传播流。因为图1（a）中存在边（A，G，3）和边（G，C，5），意味着C曾经引用过G，而G曾经于早些时候引用过A，因此A到C之间存在可能的信息传播。对于时间段[5，9]，则A与C之间不存在这样的传播途径。图1（b）展示了图1（a）对应的一个静态图。不难发现，由于缺少时序信息，图1（b）不能更精准地捕获对象之间的互动过程。

现有的关于时序图的路径与可达性的研究主要集中于各种时序路径的计算，如文献[4，5，6，9，10，11，12，13]。其中文献[9]作为较新的算法，主要集中于如何快速计算具备不同时序特征的路径，如最早出发路径，最晚出发路径，历时最短路径等。由于没有利用任何索引结构，在最坏情况下，文献[9]需要扫描整张时序图，使得其运行时间复杂度是O（n）。文献[10]中的算法直接应用Dijkstra算法，因此其运行效率不如文献[9]。除了文献[9，10，13]之外，其他的研究工作局限于时序图在某个特定领域的应用，如文献[4]计算两个结点之间的连通性（即两个节点之间的不相交的路径数量），文献[11]研究信息沿着时序图扩散的滞后时间（通过计算最晚出发路径得到），文献[5，6]通过计算最早出发路径来获取时序效率（如信息在两个节点之间传播的难易度）和其他一些时序特征。最新的文献[13]提出了一种称为TopChain的索引结构用来解决时序可达性问题，但是只索引通过一个节点的所有路径中的前k条，因此仍然需要通过在原始时序图上进行搜索才能得到准确答案。除此之外，文献[1，2，3]代表了静态图中可达性问题研究的典型工作，但是将其直接应用于时序图可能会导致错误结果。

图1 一个示例时序图及其静态图表示

我们注意到时序图中节点的度可能非常高，如一个人可能会在不同时间打多个电话给同一个人/不同人，一个站点可能始发多个不同班次的公共交通工具，一篇论文可能被多个论文引用等。如果使用文献[9]中的顺序扫描的方式来计算可达性，则不能避免访问不属于查询时间区间[t1，t2]内的边，导致运行效率低下。因此，我们提出一种新颖的算法Bi-BFS（Bidirectional BFS），通过利用现有的B+-tree索引，快速定位满足查询条件的边，提高运行效率。同时，算法从两端节点同时出发，进行双向搜索，期望在某个中间节点相遇，从而以最短时间判断节点之间的可达性查询。通过对不同的数据进行试验表明，Bi-BFS算法可以较大幅度地提升可达性查询效率。

2 时序可达性及相关定义

接下来我们定义时序图上的时序可达性查询。给定一个查询时间区间TC=[ts,te]（ts≤te），时序图GT上一个可达性查询TR=（GT，u，v，TC）为判断u和v之间是否存在一条PT，并且满足start（PT）≥ts和end（PT）≤te。如果这样的PT存在，则我们称u和v在TC区间内是可达，反之则为不可达。考虑图1（a）中的时序图，则A和E在区间[2，6]和[1，5]都是可达，但是对于区间[4，6]不可达，因为A始发的边的开始时间均小于4，因此不存在满足条件的PT。同样的查询如果运行在图1（b）上所示的静态图上，由于时序信息的缺失，会错误的判断A和E在区间[4，6]间可达。

3 改进的算法Bi-BFS

从上述的时序可达性查询例子可以看出，由于时序性特征的存在，使得时序可达性查询具有比静态图的可达性查询更复杂的特性。时序可达性查询不仅要确定两个节点之间是否存在路径，而且还要验证路径是否满足时序性要求，即时序路径定义中ti+λi≤ti+1。虽然可以通过直接应用宽度优先遍历（BFS）或者深度优先遍历（DFS）解决时序可达性问题，但是其在超大规模时序图上的运行效率较低，因为需要访问大量无效的中间节点。另外一种方式是通过查找两个节点之间的时序路径判断其可达性，如应用文献[4,5,6,9,10]中的算法。因为未能充分利用时序可达性的特性，与BFS/DFS相比，这些算法运行效率提升有限。

通过上述讨论得知，如果充分有效地利用时序递增性则能避免访问无效边，从而提升搜索效率。因此，针对一个节点u的所有出边（u，v，t，λ），我们在其t上建立一棵B+-tree。图2展示了建立于图1（a）中G节点所有出边上的B+-tree，并假设B+-tree节点的度为2。考虑到我们用指针按顺序链接B+-tree中所有叶子节点，实现更快的批量载入。以上文中的（D，G，7）为例，通过查询图2中的B+-tree得知只有（G，C，9）满足时序递增性要求，避免了其余4条边的访问。如果以（A，G，3）为例，则首先找到（G，H，4），并通过叶子节点之间的指针快速提取（G，C，5）、（G，E，5）、（G，C，9）。

当为GT中的每个节点建立B+-tree之后，给定一个时序可达性查询TR=（GT，u，v，TC），我们可以通过在GT上进行BFS获得结果。常规遍历算法（BFS或者DFS）从u出发，期望在某个遍历过程中到达v，或者未能在TC内到达v。如果v距离u较远（即u到v的路径较长），或者u到v的时序路径数量较少，则BFS算法需要访问大量的中间节点；而DFS的运行时间取决于选择的路径，其时间效率普遍低于BFS（后续的实验中验证了这一点）。

图2 图1（a）中G节点出边对应的B+-tree

考虑到以上算法的局限性，给定TR=（GT，u，v，TC），我们提出一种改进算法Bi-BFS，从u和v同时出发进行BFS遍历，期望在PT的中间节点相遇（PT为从u到v并且满足TC的时序路径）。为方便以下讨论，我们为每个节点w定义一个二元组wt=（we，wl），we表示从u出发最早到达w的时间，而wl表示从w出发到达v的最晚出发时间，并且we∈TC，wl∈TC。初始状态下，所有节点的we=MAX，wl=-MAX。

定理1：给定TR=（GT，u，v，TC），如果存在一个节点w及wt=（we，wl），we和wl非0，并且we≤wl，则u和v在TC区间内时序可达。反之亦然。

下面算法1给出了Bi-BFS算法：

总之，随着信息时代的发展，社会对于人们的专业素质、专业知识和专业能力要求日益提高，新知识、新技术、新规范、新理念层出不穷，各个专业既高度分化又日趋综合。面对时代的挑战，高校教育唯有强化通识基础，融合不同专业知识，才能培养出高规格的创新型人才。

算法1：Bi-BFS算法

输入：一个时序网络G=（VT，ET），TR=（GT，u，v，TC），TC=[ts，te]

输出：true or false

算法1中的1-3行进行初始化工作，4-27行的循环体为算法主体。每一次循环时，从u和v交替推进。算法中5-15以u为起点，检查满足TC（t∈TC）和时序路径要求（t≥we）的u的出边（第6行），如果已经到达v（第7行），则返回真值。如果x≠v，则x为中间节点，并且存在如下两种情况：

①t＜xe（第9行），意味着当前路径为u到x的最快路径（到达时间最早），因此算法将xe更新为当前到达时间（第10行）。如果更新过的xe和已有xl满足xe≤xl（第11行），根据定理1，TR查询返回真值。否之，将x入队列（第14行），以便后续处理。

算法中16-26行为从v出发倒推，其基本思路与上述类似，因此不再重复。需要说明的是无论Q1和Q2为空导致退出4-27行的while循环时，算法直接判定TR为false。如果TR为真，则必定存在一条从u到v的时序路径，因此要么第7行或第18行条件满足，要么存在w满足we≤wl（定理1），也即第11行或者第12行条件满足。因此，如果Q1=Ø或者Q2=Ø，TR=false。

我们用下面的例子说明改进算法的基本思路。给定TR=（GT，A，I，TC），TC=[1，9]，

①首先检查A的所有出边，标记并入队列满足TC要求的节点Ft=（1，-MAX），Gt=（3，-MAX），Bt=（1，-MAX）。如图3（a）中的阴影节点所示。Fl，Gl，Bl均为-MAX，表示目前我们还未能知道这3个节点与终点F之间的时序可达性。

②接下来，搜索I的入边，寻找并标示能在TC时间内到达F的节点，即Ht=（MAX，8），其运行结果如图3（b）所示。He=MAX表示目前源点A和H之间的时序可达性未知。

③检查步骤1入队列的所有节点的所有出边。以B为例，则Ge的值由步骤1里面的3更新为2，表示我们可以更早的从A到达G，即路径（A，B，G）。当检查F的出边时，我们计算出He=3，而步骤2中得到Hl=8，因此Ht=（3，8）。根据定理1，算法结束并返回true。最终找到的时序路径如图3（c）所示。

4 实验结果与分析

本节中我们在数据集上进行试验，展示Bi-BFS算法与现有最新的One-Scan算法[9]之间的性能对比。除了One-Scan算法之外，文献[9]中还提出了Transformed Graph算法，但是其运行效率不如One-Scan算法，因此试验只对比Bi-BFS与One-Scan算法。实验中使用2个真实时序数据集：dblp和enron[14]。表1展示了这两个数据集的统计信息。所有试验均运行在一台Intel 3.0G CPU和4G内存的Windows 7上。

表1 数据集统计信息（K=103）

图3 改进算法的一个示例

为了更好地模拟算法在真实运行环境下的性能，我们编写了一个模拟查询产生器，用来生成随机的时序可达性查询。试验中每次使用一个包括1000个查询的查询集，并记录这个查询集的平均查询时间。因为TC的区间长度对算法效率有着显著的影响，因此本实验主要针对4组不同长度的TC=[ts，te]进行对比，即I= te-ts和I4=2I3=2I2=2I1（I2的区间长度是I1的两倍，以此类推）。图4展示不同算法之间的运行时间对比（单位为秒）。

图4中的实验对比结果表明，通过利用B+-tree以及双向BFS，Bi-BFS算法在两个实际数据集上的效率均优于One-Scan算法。虽然随着TC区间的扩大以及需要访问的边的数量增加，导致两个算法的平均运行时间均加大，Bi-BFS的增加幅度大幅小于One-Scan算法，能更好地适应大区间查询。相比dblp而言，enron的节点具有更高的度，边的数量相对更多，因此Bi-BFS算法可以利用B+-tree快速定位和提取满足条件的边，从而实现更好的运行效率。

时序图中的时序可达性查询由于其所具有的时序约束特征，使得传统的可达性算法要么不适用时序图，要么运行效率低下。本文中提出一个新颖的基于B+-tree的改进算法Bi-BFS，通过利用B+-tree和双向BFS，大幅提升时序可达性查询的运行效率。实验结果验证了Bi-BFS能够更好地适应超大规模数据集以及更长的查询区间。

5 结论

图4 性能对比

Bi-BFS算法目前只适应于解决简单时序图上的可达性查询，后续的工作包括如何扩展适应复杂时序图，如公共交通系统的定时发车，周期性的课程安排等；同时，如何能够与已有的基于图的索引相结合，如2-hop等，从而更好地提升运行效率，也是值得研究的方向之一。

[1]Cheng J,Huang S,Wu H,et al.TF-Label:a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph[C]. Proc.SIGMOD Conference,2013:192-204.

[2]Cheng J,Ke Y,Chu S,Cheng C.Efficient Processing of Distance Queries in Large Graphs:a Vertex Cover Approach[C].Proc.SIGMOD Conference,2012:457-468.

[3]Cheng J,Shang Z,Cheng H,Wang H,et al.Efficient Processing of k-hop Reachability Queries[J].VLDB Journal,2014,23(2):227-252.

[4]Kempe D,Kleinberg J.M,Kumar A.Connectivity and Inference Problems for Temporal Networks[J].Journal of Computer System Science,2002,64(4):820-842.

[5]Tang J,Musolesi M.,Mascolo C.,Latora V.Temporal Distance Metrics for Social Network Analysis[C].Proc.the ACM Workshop on Online Social Networks,2009:31-36.

[6]Tang J,Musolesi M,Mascolo C,Latora V.Characterising Temporal Distance and Reachability in Mobile and Online Social Networks[J]. Computer Communication Review,2010,40(1):118-124.

[7]Xiang L,Yuan Q,Zhao S,et al.Temporal Recommendation on Graph via Long-and Short-term Preference Fusion[C].Proc.KDD, 2010:723-732.

[8]Xuan B,Ferreira A,Jarry A.Computing Shortest,Fastest,and Foremost Journeys in Dynamics Networks[J].International Journal of Computer Science,2003,14(2):267-285.

[9]Wu H,Cheng J,Huang et al.Path Problems in Temporal Graphs[C].Proc.VLDB Conference,2014:721-732.

[10]Santoro N,Quattrociocchi W,Flocchini P,et al.Time-varying Graphs and Social Network Analysis:Temporal Indicators and Metrics[C].CoRR,abs/1102.0629,2011.

[11]Kossinets G,Kleinberg J.M.,Watts D.J.The Structure of Information Pathways in a Social Communication Network[C].Proc.KDD, 2008:435-443.

[12]Wang S,Lin W,Yang Y,Xiao X,et al.Efficient Route Planning on Public Transportation Networks:A Labelling Approach[C].Proc. SIGMOD,2015:967-982.

[13]Wu H,Huang Y,Cheng J,et al.Efficient Processing of Reachability and Time-based Path Queries in a Temporal Graph[C].CoRR, vol.abs/1601.05909,2016.

[14]Enron:(Email network),Koblenz Large Network Collection http://konect.uni-koblenz.de/.

BI-BFS:An Innovative Approach to Answer Temporal Reachability Queries

LIU Kai-yang，FAN Xin-can
（Department of Computer Engineering,Shenzhen Polytechnic,Shenzhen 508055）

Reachability over a massive graph is a fundamental graph problem with numerous applications.However,the concept of a classic reachability algorithm is insufficient for a temporal graph,as it does not consider the temporal information,which is vital for determining the reachability between two nodes.Proposes an efficient online algorithm Bi-BFS for answering the reachability problem in a massive temporal graph.The proposed approach fully explores the time constraints among edges in a temporal graph,and utilizes an index to speed up the computation.Various experimental results demonstrate that the algorithm outperforms competitors greatly.

Reachability;Temporal Graph;Algorithm

1007-1423（2017）08-0012-07

10.3969/j.issn.1007-1423.2017.08.003

刘凯洋（1978-），男，湖南益阳人，研究生博士学位，研究方向为图论、最优路径、可达性

2016-12-15

2017-02-25

范新灿（1978-），男，河南平顶山人，硕士研究生，教授，研究方向为软件开发模型、大数据查询设计与优化、大数据挖掘等