动态图上基于2-HOP COVER的TOP-K最短路径算法
2019-04-15施琴儿
施 琴 儿
(复旦大学计算机科学技术学院复旦-众安区块链与信息安全联合实验室 上海 200433)(上海市区块链工程技术中心 上海 200433)
0 引 言
图论中最短路径问题是一个经典的问题。在一个有向带权图中，最短路径查询问题是查找图中两个节点之间的最短路径，最短距离问题是求出两个节点之间的最短的路径长度。top-k最短路径查询是对前k条最短路径的查询。近年来top-k最短路径问题在实际中有诸多的应用，如多目标跟踪[1]、基因网络[2]和多序列分析[3]等等。
很多现实中的网络是在随着时间而改变的。对于网络的实时变化，这些针对静态的图的top-k算法需要对每次变化的图进行重新的计算。在实际生活中的网络点之间的关系很复杂，网络的数据也在日益增多。对于大规模的图，每一次的变化都会引起静态算法的重新计算。对于微小的变化而言，绝大部分计算是重复的，在实际运用中效率低下。同时，我们也希望有方法分析图的改变趋势。例如，在社交网络图中，一个用户在一个时刻关注某件事的几个焦点，下个时刻关注的焦点又可能发生了改变。通过记录top-k距离的改变，可以分析用户行为。再例如，在道路网中，通过追踪两个城市之间道路的改变，可以分析道路建造的趋势。
传统的最短路径算法不能满足大规模图的top-k最短路径的计算，需要预处理原始图的数据关系，然后在图进行动态更新后，通过更新原始图的部分数据，动态图的更新算法能快速地得到新的top-k最短路径。
1 相关研究
1959年Hoffman和Pavley[4]提出了KSP(k shortest path)问题后，一些研究人员提出了解决该问题的算法。
KSP问题是基于最短路径问题提出的，一部分解决该问题的算法也是基于最短路径算法的。经典的最短路径算法有Dijkstra算法[5]、Floyd-Warshall[6]算法等。其中，Dijkstra算法对于每次查询给定的节点对都需要重新计算最短路径；Floyd算法对于节点对的查询耗时很少，但需要预先计算路径表。这些算法用于大规模图时，其时间和空间消耗不能满足实际需要。为了提高大规模图最短路径计算的性能，一些研究人员提出了两步骤算法，这类算法在求解最短路径问题时分为了两个步骤：预处理和查询。目前该类算法中的主流是基于树分解或2-hop cover[7]的。Wei在2010年[8]提出了一种高效的树分解方法：TEDI。在此之后Akiba等[9]基于TEDI做了一些优化。Xu[10]在2016年提出的BBQ优化了预处理时间以及提出了批量查询算法。Akiba等[11]在2013年提出了一个剪枝的2-hop cover最短路径算法：PLL。为了弥补PLL局限于静态图的不足，Akiba等[12]又提出了基于PLL的动态最短路径算法。
近年来主要的KSP算法分为两类：一类是不可重复路径的top-k最短路径算法，以Yen[13]提出的Yen′s算法为代表；另一类是可重复路径的top-k最短路径算法，以Eppstein[14]提出的算法为代表，该算法允许环的存在。Akiba在2015年[15]根据2-hop cover的思想提出了在大规模图中高效求解top-k的算法，在预处理得到索引集后，对于每一次查询能利用索引集快速得到top-k最短路径。
这些对KSP问题的研究，针对的都是静态图上KSP的计算。如果图进行了少许的更新改变，对这些算法而言就相当于是另一幅图了。在实际中，关系网等网络都是在实时更新的。对于静态图中的KSP算法，这些路径计算的算法都需要重新再执行一遍，极大地影响了效率。本文借鉴了两步骤算法中的2-hop cover的思想，对图进行预处理，建立索引集。如果图进行了更新，只需要更改原始图中预处理得到的部分索引集，就能得到更新后图的索引集。
2 预处理算法分析
图论中图分为两种：有向图和无向图。由于在大部分的社交网络关系图中，两个人不一定是相互关注的，并且在好友中亲密值也会不同，对应的是有向带权图，因此本文中主要研究的是有向带权图上的更新算法。动态top-k算法分为两个步骤：预处理步骤和查询步骤。然后根据预处理得到的索引集进行更新算法的操作。
2.1 2-hop cover
本文用的是基于2-hop cover的框架，具体的定义(参照文献[7])如下：
定义1在一个有向图G=(V,E)中，其对应距离标记集为LG，LG={L(v)}，其中v∈V。距离标记L(v)=(Lin(v),Lout(v))，其中：
(1) 对于所有的v∈V，Lin(v)是所有(u,δ(u,v))的集合，δ(u,v)=d(u,v)；
(2) 对于所有的v∈V，Lout(v)是所有(u,δ(v,u))的集合，δ(v,u)=d(v,u)。
任意两点x和y之间的距离定义为：
δ(x,y)=min{δxv+δvy|(v,δxv)∈Lout(x),
(v,δvy)∈Lin(y)}
(1)
如果对于图G中任意节点x和y，通过上述的距离标记集LG得到的距离等于它们在图中的实际距离，那么LG就是图G的2-hop cover。由上述的定义可知，计算任意两个节点最短距离的时间为O(|Lout(x)+Lin(y)|)。
2.2 索引算法
动态top-k算法需要对原始图进行预处理计算，对于给定的一个图G=(V,E)，得到索引集IN=(L,Lr,C)。记Gr是图G的反转图，Gr=(V,Er)。其中V是节点的集合，E是边的集合，L是图的距离标记表集合，Lr是反转图的距离标记表集合，C是自循环标记表集合。
索引算法是对图的预处理过程。在算法中，需要分别计算自循环标记表和距离标记表。默认节点编号按照度的大小给出(为了方便后面能剪枝更多的节点)。具体过程见算法1。
算法1索引算法
Input: G=(V,E),k
Output: index of G
1 procedure CreateIndex()
2 Gr=Reverse(G)
3 for i=1 to n do
4 ComputeCircle(G,vi,k)
5 end for
6 L(v),Lr(v)=empty for all v∈V
7 for i=1 to n do
8 PrunedBFS(G,Gr,L,Lr,C,vi,k)
9 end for
10 return (L,Lr,C)
算法1包含两个子程序：ComputeCircle和PrunedBFS，分别计算自循环标记表和距离标记表。
计算自循环标记表的基本思路为：对于每个节点v，用BFS来计算它到自身的距离；在每个节点的BFS过程中，剪枝掉已经访问过的节点；每个节点能被访问最多k次。这样得到一个自循环标记表。具体过程见算法2。
算法2自循环标记表算法
Input: G,v,k
Output: C(v)
1 procedure ComputeCircle(G,v,k)
2 a priority queue Q←(v,0), C(v)←empty
3 while Q is not empty do
4 pop up (u,δ) from Q
5 if u=v then C(v)=C(v)∪{δ}
6 if |C(v)|≥k and δ≥C(v)kreturn C(v)
7 for all (u,w)∈E and w≥v do
8 push (w,δ+e(u,w)) in Q
9 end for
10 end while
11 return C(v)
计算距离标记表的基本思路为：对于每个节点v，同样用剪枝的BFS来计算；在访问节点v时，如果该节点已经被访问k次，或者δvu≥mink(L,C,v,u)，将节点u剪枝，之后的搜索将不会再访问；否则，即找到一条v到u的新路径，该路径的长度小于现有索引集得到第k条路径的长度，这时将二元组(u,δvu)放入L(u)中。具体过程见算法3。
算法3距离标记表算法
Input: L,Lr,C,v,k
Output: L,Lr
1 procedure PrunedBFS(G,Gr,L,Lr,C,v,k)
2 a priority queue Q ←(v,0)
3 while Q is not empty do
4 pop up (u,δ) from Q
5 if maxk(querydis(IN,v,u))>δthen
6 add (v,δ) to L(u)
7 for all (u,w)∈E and w≥v do
8 push (w,δ+e(u,w)) in Q
9 end for
10 end if
11 end while
12 same method for Lr
13 return (L,Lr)
2.3 查询算法
通过索引算法得到的索引集IN=(L,Lr,C)，计算任意两点u和v的距离公式为：
dis(u,v)={δuw+δww+δwv}
(2)
式中：(w,δuw)∈Lr(u),δww∈C(w),(w,δwv)∈L(v)。
由式(2)可知，在计算两个节点的最短top-k距离时，需要查找到Lr(u)和L(v)中的都可到达的候选节点，即wi∈Lr(u)∩L(v)。先通过(Lr(u),C)得到到达(w1,w2,…,wt)的k个最短距离δu,wi={δ1,δ2,…,δk}，再通过L(v)中的二元组 (wi,δwi,u)得到节点u到v的top-k最短距离。
引理1对于每个点对(x,y)，通过IN=(L,Lr,C)，其k个最短路径dis(x,y)为：
dis(x,y)={d1(x,y),d2(x,y),…,dk(x,y)}
(3)
式中：di(x,y)由式(2)得到。
在算法3中可以得到节点x到所有节点v的最短的t1个距离，以及节点v到所有节点y的最短的t2个距离，其中(v,δxv)∈Lr(x)，(v,δvy)∈L(y)， 1≤t1,t2≤k。这些距离所经过的路径点v满足v
2.4 复杂度分析
在索引算法中，算法2中每个节点都被访问一遍，在碰到已经访问过的节点时， 直接进行剪枝，剩余的每个点最多被访问k次。因此，合计下来，每个节点最多被访问k次，因此其时间复杂度为O(nk)。算法3中，假定距离标记表的平均长度为len，那么我们总共需要访问n·len个节点，平均需要访问O(n/m)条边，判断每条边是否加入到队列中所需的查询需要O(len·klogk)的时间，因此总的时间复杂度为O(klogk(m·len+n·len2))。而在实际世界的图中，经过剪枝后得到的索引集的长度len=n，并且需要的k也是一个相对比较小的值。至于空间复杂度，自循环标记表需要O(nk)的空间，而距离标记表需要O(nk·len)的空间，因此总的空间复杂度为O(nk·len)。
在查询算法中，每个点的距离标记表的平均长度为len，每个点的距离存储的数量为k，因此查询算法的时间复杂度为O(len·klogk)。
3 动态更新算法分析
在实际世界里，数据及其关系是不断增加的，在图中更新基本的操作是点或边的增加。在很多实际动态改变网络中，移除点或边的操作是比较少的。在文献[16]中几种动态更新的图中，可以看到增加的操作要远比删除操作频繁，因此本文更新算法只是针对点或者边增加的更新。
在索引集中增加一个点的记录很简单：如果在图中新增加了一个新的节点a，只需要在索引集中加入L(a)=(a,0)、Lr(a)=(a,0)、C(a)=(0,∞,…,∞)。因此更新算法着重于对边的更新。
引理2假设G和G′为两个图，其中E(G)⊆E(G′)，那么对于任意两个节点x和y，x,y∈V(G)∩V(G′)，有d(x,y)≥d′(x,y)。
由引理2中可知，如果一个图包含另一个图的所有边，在这个图中的两点间的距离要小于等于在另一个图中的距离。对于图中的任意两个节点，若它们之间有一条通过新边更短的路径，则这两点间距离减小；反之，则这两点距离不变。
3.1 索引集更新
假设增加的一条边为(a,b)，权重为eab，并且a和b两个节点已经在图中。我们只需要对新加入的边影响的节点进行部分索引集的更新，即增加部分数据或更改部分数据。索引更新算法的伪代码如下：
算法4更新索引算法
Input: index of G,(a,b)
Output: index of G′
1 procedure insert_G,(a,b)
2 UpdateCircle(L,Lr,C,a,b)
3 for all vi∈L(a) from lower vido
4 D←(d1(vi,a)+eab,d2(vi,a)+eab, …,dk(vi,a)+eab)
5 UpdateIndex(G,L,Lr,vi,b,D)
6 end for
7 return (G,L,C)
8 procedure insert_Gr,(b,a)
9 UpdateCircle(L,Lr,C,a,b)
10 for all vi∈Lr(b) from lower vido
11 D←(d1(vi,b)+eab,d2(vi,b)+eab,…,dk(vi,b)+eab)
12 UpdateIndex(Gr,Lr,L,vi,a,D)
13 end for
14 return (Gr,Lr,C)
由上述的代码可知，索引集更新中包括自循环标记表集和距离标记表集更新，具体过程在算法5和算法6中给出。
图1和图2是一个示例。图1标出了从最左边节点出发的到所有节点的top-2最短距离；图2标出了在加入了一条边之后，从最左边节点出发得到的所有节点的 top-2 最短距离。可以看到只有b和在b之后的节点会有改变，其余节点不变。
图1 一个示例：图中距离是与最左边节点top-2距离
图2 一个示例：图增加一条边后与最左边节点top-2距离
引理3如果在图更新后，节点vi到u的距离改变了，那么所有更新了的top-k最短路径一定经过了边(a,b)。
引理4假设一条从节点vi到u的top-k最短路径P改变了，其中u≠a,b，那么路径中经过了节点b之后的节点w到vi的top-k距离都改变了。
由引理4可知，如果两个节点u到v的top-k最短距离改变了，那么改变的只是经过b之后的节点，在路径到达a之前所经过的节点的距离不变。因此在更新中，不需要从(vi,0)开始修改，只需要从(b,d(vi,a)+g)开始。由于在索引集中得到的d(vi,a)有k个，因此初始的集为(b,d1(vi,a)+g),(b,d2(vi,a)+g),…,(b,dk(vi,a)+g)。
在图G中增加的边为(a,b)，相应地在图Gr中增加的边为(b,a)，因此图G和Gr的距离标记表都需要更新。
3.2 自循环标记表更新
与算法1相对应，需要有自循环标记表和距离标记表更新的两个过程。由引理3和引理4可知，不是所有节点的自循环标记表需要更新，只有在自循环经过的路径中包含了边(a,b)后才会改变该节点的自循环标记表。更新自循环标记表算法伪代码如下：
算法5更新自循环标记表算法
Input: L,Lr,C,a,b
Output: C′
1 for all vi∈L(a)∩Lr(b) from lower viand vi≠a,b do
2 for all(vi,δvi,a)∈L(a) and (vi,δvi,b)∈Lr(b) do
3 if δvi,a+δvi,b+eab 4 α=query(L,C,vi,a) 5 β=query(Lr,C,b,vi) 6 δ=α+β+eab 7 for j=1 to k do 8 if δj 9 end for 10 end if 11 end for 12 end for 13 return C′ 如果vi∈L(a)∩Lr(b)，即vi→a和b→vi可达，加入边(a,b)后，更新了vi的自循环标记表，可形成vi→a→b→vi。 因此需要更新的节点最多为max(|L(a)|,|Lr(b)|)个，其余的节点不需要更新。 如3.2所述，自循环标记表的更新只需要更新L(a)∩Lr(b)个节点。相应地，对于距离标记表的更新需要更新L(a)∪Lr(b)中的节点。如果一个节点v不属于L(a)∪Lr(b)，在计算其中一个PrunedBFS时，该节点已经被剪枝，所以增加的边对被剪枝删除的节点没有影响。算法伪代码如下： 算法6更新距离标记表算法 Input: index of G,L,Lr,vt,a,D Output: index of L′ 1 Q ← empty 2 for i=1 to |D| do 3 push(a,Di) in Q 4 end for 5 while Q is not empty do 6 pop up(u,δ) from Q 7 if TopKQuery(IN,vt,u,t)>δthen 8 add(v,δ) to L(u) 9 for all(u,w)∈E′and w≥vtdo 10 push(w,δ+e(u,w)) in Q 11 end for 12 end while 13 return L′ 在算法中的TopKQuery(IN,x,y,t)定义如下： TopKQuery(IN,x,y,t)={δxvu+δvivi+δviy} (4) 其中：i≤t,(vi,δxvi)∈Lr(x),δvivi∈C(vi),(vi,δviy)∈L(y)。 它计算的是节点x和y在索引集IN下的第k个距离，如果节点x和y之间没有k条路径，那么定义TopKQuery(IN,x,y,t)=∞。 在经过更新算法后得到新的索引集IN′，要证明此为图G′的索引集。对于任意两个节点x和y，以及t(0≤t≤n)，我们定义: d1(x,y,t)=mink(d(x,vi)+d(vi,vi),d(vi,y)) 如果t=0或者没有一个vi满足i≤t，那么d1(x,y,t)=∞。 引理5对于任意两个节点x和y，以及i(0≤i≤n)，IN是图G的2-hop cover索引集，我们有TopKQuery(IN,x,y,i-1)=d1(x,y,i-1)。对于任意一个节点u，如果节点vi满足d′(vi,u) 证明：由条件可知d′(vi,u) (vi,…,z,…,z,…,a,b=w0,w1…,ws-1,u=ws) 由此可知对于所有的wi，都有d′(vi,wj) 由条件可知d′(vi,u) 同理d′(vi,wj) 因此在进行距离标记表更新算法中，对于所有的节点wj，我们有: TopKQuery(IN,vi,wj,i)≥ 得到TopKQuery(IN,vi,wj,i)≥d′(vi,wj)，所以在算法6中，节点wj没有被剪枝，该新的距离加入了L′(u)中。因此在新的索引集IN′中，一定有(vi,d(vi,u))∈L′(u)。 综上所述，引理5成立。 引理6对于任意两个节点x和y，以及i(0≤i≤n)，更新算法得到的索引集IN′，也有TopKQuery(IN′,x,y,i)=d1(x,y,i)。 证明：如果i=0，两个节点不可达，距离都为无穷大，成立。现在假设对于所有的i>0，对于任意两个节点x和y，都有TopKQuery(IN′,x,y,i-1)=d1(x,y,i-1)。 只需要证明: TopKQuery(IN′,x,y,i)=d1(x,y,i) 令δ=d1(x,y,t)。 1) 如果δ=d1(x,y,i-1)，那么一定成立。 2) 如果δ δ=d′(x,vi)+d′(vi,vi)+d′(vi,y) 只需要证明： (vi,d′(x,vi))∈L′r(x) 在这里证明(vi,d′(vi,y))∈L′(y)。 如果d′(vi,y)=d(vi,y)，从d1(x,y,t)=mink(d(x,vi)+d(vi,vi),d(vi,y)) 可知，在经过节点vi到节点y的路径中，不存在一个节点vl(l d1(vi,y,i-1)>d1(vi,y,i) 如果(vi,d′(vi,y))∉L(y)，那么： TopKQuery(IN,viy,i)=d1(vi,y,i-1)>d1(vi,y,i)存在矛盾，因此一定有(vi,d′(vi,y))∈L(y)⊆L′(y)。 如果d′(vi,y) 综上所述，引理6成立。 由引理5和引理6可知，如果增加了边(a,b)，所有经过该边的路径距离都加入到了新的索引集中，得到的IN′为图G′的索引集。 点更新的时间消耗是O(1)。 对于边更新，假设距离标记表的平均长度为len，即|L(v)|=len,|Lr(v)|=len。 那么在UpdateCircle(L,Lr,C,a,b)中要更新的节点数为O(len)，由于需要对每个要更新节点查询当前的k短路，每次查询时间为O(klogk)，因此在线自循环标记表更新的时间复杂度为O(len·klogk)。假设在UpdateIndex(G,L,Lr,vi,b,D)中需要访问的节点数量为O(len)，那么访问的点对数为O(kt)，在算法6中的TopKQuery需要O(len·klogk)的时间，算法4中需要访问该过程O(len)次，因此该过程的时间复杂度为O(len2·k2tlogk)。在剪枝之后len,t≼n，在平时应用中k也是比较小的数字。 所以更新算法的时间复杂度为O(len·klogk+len2k2tlogk)。 在更新算法中，使用的依旧是初始索引集的存储空间。被修改的节点数量为O(len)，每个节点最多修改了O(k)个值，因此空间复杂度为O(len·k)。 因此，动态top-k更新算法的时间复杂度为O(len·klogk+len2·k2tlogk)，空间复杂度为O(len·k)。 本节将通过实验评估动态更新算法的时间和空间开销。实验用计算机的配置为Intel Core i5(2.7 GHz)处理器，8 GB内存。实验程序运行于单个CPU核心上。数据集选用了Wikipedia vote network[17]，其中包括7 115个节点，103 689条边，在这里默认所有边的权值为1。 实验中，更新量定义为网络更新时增加的边数，每增加一条边，运行一次更新算法。定义实验数据的单位平均值为实测值除以更新量，即每增加一条边的平均数据指标。 实际结果显示，更新算法的总开销和单位平均开销与k和更新量有关。 表1列出了更新量为1 000时不同的k对应的更新算法的时间开销。可以看到，随着k的增加，单位平均更新时间也在逐渐增加；在k不大于32时，更新算法的时间开销较小，性能较好。 表1 k对更新算法时间开销的影响 表2列出了更新量为1 000时不同的k对应的更新算法的空间开销和访问节点数量。可以看到，访问节点单位平均数量约等于索引集中每节点索引的平均长度；k不大于32时，访问节点单位平均数量和索引集总长度单位平均增长率都较小，此时更新算法的空间开销和访问节点数量较小。 表2 k对更新算法空间开销和平均访问节点数量的影响 图3显示了k=16时更新量对单位平均更新时间与访问节点单位平均数量的影响。可以看到三项数值都随着更新量的增大而增大，但增长较为缓慢，且自循环标记表单位平均更新时间仅为微秒级。由此说明算法在大更新量下仍能保持较好的性能。 图3 更新量对更新算法时间开销和访问节点数量的影响 本文对于动态更新的有向带权图中的top-k最短路径问题设计并分析了基于2-hop cover的算法。更新算法利用预处理得到的索引集来更新，从而显著地减少了图改变后计算top-k的时间，只需要消耗更新算法的时间，而且有效地利用了原图的数据集和性质。 本文在理论上证明了更新算法的正确性，分析了时间复杂度，证明其更新时间远小于将更新后的图看作静态图重新预处理的计算时间，并用实验评估了更新算法处理大规模网络的实际性能，证实了其实用性。动态top-k更新算法在大规模图上可以进行快速更新和查询。在未来研究工作中，我们将研究对于批量的更新如何提高效率、减少时间，以此来提高更新算法在实际应用中的性能。3.3 距离标记表更新
3.4 正确性证明
(vi,d′(vi,y))∈L′(y)
3.5 复杂度分析
3.6 实例分析
4 结 语
