動(dòng)態(tài)圖上基于2-HOP COVER的TOP-K最短路徑算法

施 琴 兒

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院復(fù)旦-眾安區(qū)塊鏈與信息安全聯(lián)合實(shí)驗(yàn)室 上海 200433)(上海市區(qū)塊鏈工程技術(shù)中心 上海 200433)

0 引 言

圖論中最短路徑問題是一個(gè)經(jīng)典的問題。在一個(gè)有向帶權(quán)圖中，最短路徑查詢問題是查找圖中兩個(gè)節(jié)點(diǎn)之間的最短路徑，最短距離問題是求出兩個(gè)節(jié)點(diǎn)之間的最短的路徑長度。top-k最短路徑查詢是對前k條最短路徑的查詢。近年來top-k最短路徑問題在實(shí)際中有諸多的應(yīng)用，如多目標(biāo)跟蹤[1]、基因網(wǎng)絡(luò)[2]和多序列分析[3]等等。

很多現(xiàn)實(shí)中的網(wǎng)絡(luò)是在隨著時(shí)間而改變的。對于網(wǎng)絡(luò)的實(shí)時(shí)變化，這些針對靜態(tài)的圖的top-k算法需要對每次變化的圖進(jìn)行重新的計(jì)算。在實(shí)際生活中的網(wǎng)絡(luò)點(diǎn)之間的關(guān)系很復(fù)雜，網(wǎng)絡(luò)的數(shù)據(jù)也在日益增多。對于大規(guī)模的圖，每一次的變化都會(huì)引起靜態(tài)算法的重新計(jì)算。對于微小的變化而言，絕大部分計(jì)算是重復(fù)的，在實(shí)際運(yùn)用中效率低下。同時(shí)，我們也希望有方法分析圖的改變趨勢。例如，在社交網(wǎng)絡(luò)圖中，一個(gè)用戶在一個(gè)時(shí)刻關(guān)注某件事的幾個(gè)焦點(diǎn)，下個(gè)時(shí)刻關(guān)注的焦點(diǎn)又可能發(fā)生了改變。通過記錄top-k距離的改變，可以分析用戶行為。再例如，在道路網(wǎng)中，通過追蹤兩個(gè)城市之間道路的改變，可以分析道路建造的趨勢。

傳統(tǒng)的最短路徑算法不能滿足大規(guī)模圖的top-k最短路徑的計(jì)算，需要預(yù)處理原始圖的數(shù)據(jù)關(guān)系，然后在圖進(jìn)行動(dòng)態(tài)更新后，通過更新原始圖的部分?jǐn)?shù)據(jù)，動(dòng)態(tài)圖的更新算法能快速地得到新的top-k最短路徑。

1 相關(guān)研究

1959年Hoffman和Pavley[4]提出了KSP(k shortest path)問題后，一些研究人員提出了解決該問題的算法。

KSP問題是基于最短路徑問題提出的，一部分解決該問題的算法也是基于最短路徑算法的。經(jīng)典的最短路徑算法有Dijkstra算法[5]、Floyd-Warshall[6]算法等。其中，Dijkstra算法對于每次查詢給定的節(jié)點(diǎn)對都需要重新計(jì)算最短路徑；Floyd算法對于節(jié)點(diǎn)對的查詢耗時(shí)很少，但需要預(yù)先計(jì)算路徑表。這些算法用于大規(guī)模圖時(shí)，其時(shí)間和空間消耗不能滿足實(shí)際需要。為了提高大規(guī)模圖最短路徑計(jì)算的性能，一些研究人員提出了兩步驟算法，這類算法在求解最短路徑問題時(shí)分為了兩個(gè)步驟：預(yù)處理和查詢。目前該類算法中的主流是基于樹分解或2-hop cover[7]的。Wei在2010年[8]提出了一種高效的樹分解方法：TEDI。在此之后Akiba等[9]基于TEDI做了一些優(yōu)化。Xu[10]在2016年提出的BBQ優(yōu)化了預(yù)處理時(shí)間以及提出了批量查詢算法。Akiba等[11]在2013年提出了一個(gè)剪枝的2-hop cover最短路徑算法：PLL。為了彌補(bǔ)PLL局限于靜態(tài)圖的不足，Akiba等[12]又提出了基于PLL的動(dòng)態(tài)最短路徑算法。

近年來主要的KSP算法分為兩類：一類是不可重復(fù)路徑的top-k最短路徑算法，以Yen[13]提出的Yen′s算法為代表；另一類是可重復(fù)路徑的top-k最短路徑算法，以Eppstein[14]提出的算法為代表，該算法允許環(huán)的存在。Akiba在2015年[15]根據(jù)2-hop cover的思想提出了在大規(guī)模圖中高效求解top-k的算法，在預(yù)處理得到索引集后，對于每一次查詢能利用索引集快速得到top-k最短路徑。

這些對KSP問題的研究，針對的都是靜態(tài)圖上KSP的計(jì)算。如果圖進(jìn)行了少許的更新改變，對這些算法而言就相當(dāng)于是另一幅圖了。在實(shí)際中，關(guān)系網(wǎng)等網(wǎng)絡(luò)都是在實(shí)時(shí)更新的。對于靜態(tài)圖中的KSP算法，這些路徑計(jì)算的算法都需要重新再執(zhí)行一遍，極大地影響了效率。本文借鑒了兩步驟算法中的2-hop cover的思想，對圖進(jìn)行預(yù)處理，建立索引集。如果圖進(jìn)行了更新，只需要更改原始圖中預(yù)處理得到的部分索引集，就能得到更新后圖的索引集。

2 預(yù)處理算法分析

圖論中圖分為兩種：有向圖和無向圖。由于在大部分的社交網(wǎng)絡(luò)關(guān)系圖中，兩個(gè)人不一定是相互關(guān)注的，并且在好友中親密值也會(huì)不同，對應(yīng)的是有向帶權(quán)圖，因此本文中主要研究的是有向帶權(quán)圖上的更新算法。動(dòng)態(tài)top-k算法分為兩個(gè)步驟：預(yù)處理步驟和查詢步驟。然后根據(jù)預(yù)處理得到的索引集進(jìn)行更新算法的操作。

2.1 2-hop cover

本文用的是基于2-hop cover的框架，具體的定義(參照文獻(xiàn)[7])如下：

定義1在一個(gè)有向圖G=(V,E)中，其對應(yīng)距離標(biāo)記集為LG，LG={L(v)}，其中v∈V。距離標(biāo)記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)。

任意兩點(diǎn)x和y之間的距離定義為：

δ(x,y)=min{δxv+δvy|(v,δxv)∈Lout(x),
(v,δvy)∈Lin(y)}

(1)

如果對于圖G中任意節(jié)點(diǎn)x和y，通過上述的距離標(biāo)記集LG得到的距離等于它們在圖中的實(shí)際距離，那么LG就是圖G的2-hop cover。由上述的定義可知，計(jì)算任意兩個(gè)節(jié)點(diǎn)最短距離的時(shí)間為O(|Lout(x)+Lin(y)|)。

2.2 索引算法

動(dòng)態(tài)top-k算法需要對原始圖進(jìn)行預(yù)處理計(jì)算，對于給定的一個(gè)圖G=(V,E)，得到索引集IN=(L,Lr,C)。記Gr是圖G的反轉(zhuǎn)圖，Gr=(V,Er)。其中V是節(jié)點(diǎn)的集合，E是邊的集合，L是圖的距離標(biāo)記表集合，Lr是反轉(zhuǎn)圖的距離標(biāo)記表集合，C是自循環(huán)標(biāo)記表集合。

索引算法是對圖的預(yù)處理過程。在算法中，需要分別計(jì)算自循環(huán)標(biāo)記表和距離標(biāo)記表。默認(rèn)節(jié)點(diǎn)編號按照度的大小給出(為了方便后面能剪枝更多的節(jié)點(diǎn))。具體過程見算法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包含兩個(gè)子程序：ComputeCircle和PrunedBFS，分別計(jì)算自循環(huán)標(biāo)記表和距離標(biāo)記表。

計(jì)算自循環(huán)標(biāo)記表的基本思路為：對于每個(gè)節(jié)點(diǎn)v，用BFS來計(jì)算它到自身的距離；在每個(gè)節(jié)點(diǎn)的BFS過程中，剪枝掉已經(jīng)訪問過的節(jié)點(diǎn)；每個(gè)節(jié)點(diǎn)能被訪問最多k次。這樣得到一個(gè)自循環(huán)標(biāo)記表。具體過程見算法2。

算法2自循環(huán)標(biāo)記表算法

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)

計(jì)算距離標(biāo)記表的基本思路為：對于每個(gè)節(jié)點(diǎn)v，同樣用剪枝的BFS來計(jì)算；在訪問節(jié)點(diǎn)v時(shí)，如果該節(jié)點(diǎn)已經(jīng)被訪問k次，或者δvu≥mink(L,C,v,u)，將節(jié)點(diǎn)u剪枝，之后的搜索將不會(huì)再訪問；否則，即找到一條v到u的新路徑，該路徑的長度小于現(xiàn)有索引集得到第k條路徑的長度，這時(shí)將二元組(u,δvu)放入L(u)中。具體過程見算法3。

算法3距離標(biāo)記表算法

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)，計(jì)算任意兩點(diǎn)u和v的距離公式為：

dis(u,v)={δuw+δww+δwv}

(2)

式中：(w,δuw)∈Lr(u),δww∈C(w),(w,δwv)∈L(v)。

由式(2)可知，在計(jì)算兩個(gè)節(jié)點(diǎn)的最短top-k距離時(shí)，需要查找到Lr(u)和L(v)中的都可到達(dá)的候選節(jié)點(diǎn)，即wi∈Lr(u)∩L(v)。先通過(Lr(u),C)得到到達(dá)(w1,w2,…,wt)的k個(gè)最短距離δu,wi={δ1,δ2,…,δk}，再通過L(v)中的二元組 (wi,δwi,u)得到節(jié)點(diǎn)u到v的top-k最短距離。

引理1對于每個(gè)點(diǎn)對(x,y)，通過IN=(L,Lr,C)，其k個(gè)最短路徑dis(x,y)為：

dis(x,y)={d1(x,y),d2(x,y),…,dk(x,y)}

(3)

式中：di(x,y)由式(2)得到。

在算法3中可以得到節(jié)點(diǎn)x到所有節(jié)點(diǎn)v的最短的t1個(gè)距離，以及節(jié)點(diǎn)v到所有節(jié)點(diǎn)y的最短的t2個(gè)距離，其中(v,δxv)∈Lr(x)，(v,δvy)∈L(y)， 1≤t1,t2≤k。這些距離所經(jīng)過的路徑點(diǎn)v滿足vmax(x,y)，即w是比x和y訪問更晚的節(jié)點(diǎn)，可以得到新的路徑|P′|<|P|且P′=(x,…,v,…,w,…,v,…,y)。由于每個(gè)節(jié)點(diǎn)的自循環(huán)標(biāo)記表中的路徑可以訪問所有訪問順序靠后的節(jié)點(diǎn)，因此在計(jì)算距離公式時(shí)需要加上C(v)來得到top-k最短距離。

2.4 復(fù)雜度分析

在索引算法中，算法2中每個(gè)節(jié)點(diǎn)都被訪問一遍，在碰到已經(jīng)訪問過的節(jié)點(diǎn)時(shí)， 直接進(jìn)行剪枝，剩余的每個(gè)點(diǎn)最多被訪問k次。因此，合計(jì)下來，每個(gè)節(jié)點(diǎn)最多被訪問k次，因此其時(shí)間復(fù)雜度為O(nk)。算法3中，假定距離標(biāo)記表的平均長度為len，那么我們總共需要訪問n·len個(gè)節(jié)點(diǎn)，平均需要訪問O(n/m)條邊，判斷每條邊是否加入到隊(duì)列中所需的查詢需要O(len·klogk)的時(shí)間，因此總的時(shí)間復(fù)雜度為O(klogk(m·len+n·len2))。而在實(shí)際世界的圖中，經(jīng)過剪枝后得到的索引集的長度len=n，并且需要的k也是一個(gè)相對比較小的值。至于空間復(fù)雜度，自循環(huán)標(biāo)記表需要O(nk)的空間，而距離標(biāo)記表需要O(nk·len)的空間，因此總的空間復(fù)雜度為O(nk·len)。

在查詢算法中，每個(gè)點(diǎn)的距離標(biāo)記表的平均長度為len，每個(gè)點(diǎn)的距離存儲(chǔ)的數(shù)量為k，因此查詢算法的時(shí)間復(fù)雜度為O(len·klogk)。

3 動(dòng)態(tài)更新算法分析

在實(shí)際世界里，數(shù)據(jù)及其關(guān)系是不斷增加的，在圖中更新基本的操作是點(diǎn)或邊的增加。在很多實(shí)際動(dòng)態(tài)改變網(wǎng)絡(luò)中，移除點(diǎn)或邊的操作是比較少的。在文獻(xiàn)[16]中幾種動(dòng)態(tài)更新的圖中，可以看到增加的操作要遠(yuǎn)比刪除操作頻繁，因此本文更新算法只是針對點(diǎn)或者邊增加的更新。

在索引集中增加一個(gè)點(diǎn)的記錄很簡單：如果在圖中新增加了一個(gè)新的節(jié)點(diǎn)a，只需要在索引集中加入L(a)=(a,0)、Lr(a)=(a,0)、C(a)=(0,∞,…,∞)。因此更新算法著重于對邊的更新。

引理2假設(shè)G和G′為兩個(gè)圖，其中E(G)?E(G′)，那么對于任意兩個(gè)節(jié)點(diǎn)x和y，x,y∈V(G)∩V(G′)，有d(x,y)≥d′(x,y)。

由引理2中可知，如果一個(gè)圖包含另一個(gè)圖的所有邊，在這個(gè)圖中的兩點(diǎn)間的距離要小于等于在另一個(gè)圖中的距離。對于圖中的任意兩個(gè)節(jié)點(diǎn)，若它們之間有一條通過新邊更短的路徑，則這兩點(diǎn)間距離減小；反之，則這兩點(diǎn)距離不變。

3.1 索引集更新

假設(shè)增加的一條邊為(a,b)，權(quán)重為eab，并且a和b兩個(gè)節(jié)點(diǎn)已經(jīng)在圖中。我們只需要對新加入的邊影響的節(jié)點(diǎn)進(jìn)行部分索引集的更新，即增加部分?jǐn)?shù)據(jù)或更改部分?jǐn)?shù)據(jù)。索引更新算法的偽代碼如下：

算法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)

由上述的代碼可知，索引集更新中包括自循環(huán)標(biāo)記表集和距離標(biāo)記表集更新，具體過程在算法5和算法6中給出。

圖1和圖2是一個(gè)示例。圖1標(biāo)出了從最左邊節(jié)點(diǎn)出發(fā)的到所有節(jié)點(diǎn)的top-2最短距離；圖2標(biāo)出了在加入了一條邊之后，從最左邊節(jié)點(diǎn)出發(fā)得到的所有節(jié)點(diǎn)的 top-2 最短距離。可以看到只有b和在b之后的節(jié)點(diǎn)會(huì)有改變，其余節(jié)點(diǎn)不變。

圖1 一個(gè)示例：圖中距離是與最左邊節(jié)點(diǎn)top-2距離

圖2 一個(gè)示例：圖增加一條邊后與最左邊節(jié)點(diǎn)top-2距離

引理3如果在圖更新后，節(jié)點(diǎn)vi到u的距離改變了，那么所有更新了的top-k最短路徑一定經(jīng)過了邊(a,b)。

引理4假設(shè)一條從節(jié)點(diǎn)vi到u的top-k最短路徑P改變了，其中u≠a,b，那么路徑中經(jīng)過了節(jié)點(diǎn)b之后的節(jié)點(diǎn)w到vi的top-k距離都改變了。

由引理4可知，如果兩個(gè)節(jié)點(diǎn)u到v的top-k最短距離改變了，那么改變的只是經(jīng)過b之后的節(jié)點(diǎn)，在路徑到達(dá)a之前所經(jīng)過的節(jié)點(diǎn)的距離不變。因此在更新中，不需要從(vi,0)開始修改，只需要從(b,d(vi,a)+g)開始。由于在索引集中得到的d(vi,a)有k個(gè)，因此初始的集為(b,d1(vi,a)+g),(b,d2(vi,a)+g),…,(b,dk(vi,a)+g)。

在圖G中增加的邊為(a,b)，相應(yīng)地在圖Gr中增加的邊為(b,a)，因此圖G和Gr的距離標(biāo)記表都需要更新。

3.2 自循環(huán)標(biāo)記表更新

與算法1相對應(yīng)，需要有自循環(huán)標(biāo)記表和距離標(biāo)記表更新的兩個(gè)過程。由引理3和引理4可知，不是所有節(jié)點(diǎn)的自循環(huán)標(biāo)記表需要更新，只有在自循環(huán)經(jīng)過的路徑中包含了邊(a,b)后才會(huì)改變該節(jié)點(diǎn)的自循環(huán)標(biāo)記表。更新自循環(huán)標(biāo)記表算法偽代碼如下：

算法5更新自循環(huán)標(biāo)記表算法

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可達(dá)，加入邊(a,b)后，更新了vi的自循環(huán)標(biāo)記表，可形成vi→a→b→vi。 因此需要更新的節(jié)點(diǎn)最多為max(|L(a)|,|Lr(b)|)個(gè)，其余的節(jié)點(diǎn)不需要更新。

3.3 距離標(biāo)記表更新

如3.2所述，自循環(huán)標(biāo)記表的更新只需要更新L(a)∩Lr(b)個(gè)節(jié)點(diǎn)。相應(yīng)地，對于距離標(biāo)記表的更新需要更新L(a)∪Lr(b)中的節(jié)點(diǎn)。如果一個(gè)節(jié)點(diǎn)v不屬于L(a)∪Lr(b)，在計(jì)算其中一個(gè)PrunedBFS時(shí)，該節(jié)點(diǎn)已經(jīng)被剪枝，所以增加的邊對被剪枝刪除的節(jié)點(diǎn)沒有影響。算法偽代碼如下：

算法6更新距離標(biāo)記表算法

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)。

它計(jì)算的是節(jié)點(diǎn)x和y在索引集IN下的第k個(gè)距離，如果節(jié)點(diǎn)x和y之間沒有k條路徑，那么定義TopKQuery(IN,x,y,t)=∞。

3.4 正確性證明

在經(jīng)過更新算法后得到新的索引集IN′，要證明此為圖G′的索引集。對于任意兩個(gè)節(jié)點(diǎn)x和y，以及t(0≤t≤n)，我們定義:

d1(x,y,t)=mink(d(x,vi)+d(vi,vi),d(vi,y))

如果t=0或者沒有一個(gè)vi滿足i≤t，那么d1(x,y,t)=∞。

引理5對于任意兩個(gè)節(jié)點(diǎn)x和y，以及i(0≤i≤n)，IN是圖G的2-hop cover索引集，我們有TopKQuery(IN,x,y,i-1)=d1(x,y,i-1)。對于任意一個(gè)節(jié)點(diǎn)u，如果節(jié)點(diǎn)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)

因此在進(jìn)行距離標(biāo)記表更新算法中，對于所有的節(jié)點(diǎn)wj，我們有:

TopKQuery(IN,vi,wj,i)≥

得到TopKQuery(IN,vi,wj,i)≥d′(vi,wj)，所以在算法6中，節(jié)點(diǎn)wj沒有被剪枝，該新的距離加入了L′(u)中。因此在新的索引集IN′中，一定有(vi,d(vi,u))∈L′(u)。

綜上所述，引理5成立。

引理6對于任意兩個(gè)節(jié)點(diǎn)x和y，以及i(0≤i≤n)，更新算法得到的索引集IN′，也有TopKQuery(IN′,x,y,i)=d1(x,y,i)。

證明：如果i=0，兩個(gè)節(jié)點(diǎn)不可達(dá)，距離都為無窮大，成立。現(xiàn)在假設(shè)對于所有的i>0，對于任意兩個(gè)節(jié)點(diǎn)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)

在這里證明(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))

可知，在經(jīng)過節(jié)點(diǎn)vi到節(jié)點(diǎn)y的路徑中，不存在一個(gè)節(jié)點(diǎn)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)，所有經(jīng)過該邊的路徑距離都加入到了新的索引集中，得到的IN′為圖G′的索引集。

3.5 復(fù)雜度分析

點(diǎn)更新的時(shí)間消耗是O(1)。

對于邊更新，假設(shè)距離標(biāo)記表的平均長度為len，即|L(v)|=len,|Lr(v)|=len。

那么在UpdateCircle(L,Lr,C,a,b)中要更新的節(jié)點(diǎn)數(shù)為O(len)，由于需要對每個(gè)要更新節(jié)點(diǎn)查詢當(dāng)前的k短路，每次查詢時(shí)間為O(klogk)，因此在線自循環(huán)標(biāo)記表更新的時(shí)間復(fù)雜度為O(len·klogk)。假設(shè)在UpdateIndex(G,L,Lr,vi,b,D)中需要訪問的節(jié)點(diǎn)數(shù)量為O(len)，那么訪問的點(diǎn)對數(shù)為O(kt)，在算法6中的TopKQuery需要O(len·klogk)的時(shí)間，算法4中需要訪問該過程O(len)次，因此該過程的時(shí)間復(fù)雜度為O(len2·k2tlogk)。在剪枝之后len,t?n，在平時(shí)應(yīng)用中k也是比較小的數(shù)字。

所以更新算法的時(shí)間復(fù)雜度為O(len·klogk+len2k2tlogk)。

在更新算法中，使用的依舊是初始索引集的存儲(chǔ)空間。被修改的節(jié)點(diǎn)數(shù)量為O(len)，每個(gè)節(jié)點(diǎn)最多修改了O(k)個(gè)值，因此空間復(fù)雜度為O(len·k)。

因此，動(dòng)態(tài)top-k更新算法的時(shí)間復(fù)雜度為O(len·klogk+len2·k2tlogk)，空間復(fù)雜度為O(len·k)。

3.6 實(shí)例分析

本節(jié)將通過實(shí)驗(yàn)評估動(dòng)態(tài)更新算法的時(shí)間和空間開銷。實(shí)驗(yàn)用計(jì)算機(jī)的配置為Intel Core i5(2.7 GHz)處理器，8 GB內(nèi)存。實(shí)驗(yàn)程序運(yùn)行于單個(gè)CPU核心上。數(shù)據(jù)集選用了Wikipedia vote network[17]，其中包括7 115個(gè)節(jié)點(diǎn)，103 689條邊，在這里默認(rèn)所有邊的權(quán)值為1。

實(shí)驗(yàn)中，更新量定義為網(wǎng)絡(luò)更新時(shí)增加的邊數(shù)，每增加一條邊，運(yùn)行一次更新算法。定義實(shí)驗(yàn)數(shù)據(jù)的單位平均值為實(shí)測值除以更新量，即每增加一條邊的平均數(shù)據(jù)指標(biāo)。

實(shí)際結(jié)果顯示，更新算法的總開銷和單位平均開銷與k和更新量有關(guān)。

表1列出了更新量為1 000時(shí)不同的k對應(yīng)的更新算法的時(shí)間開銷。可以看到，隨著k的增加，單位平均更新時(shí)間也在逐漸增加；在k不大于32時(shí)，更新算法的時(shí)間開銷較小，性能較好。

表1 k對更新算法時(shí)間開銷的影響

表2列出了更新量為1 000時(shí)不同的k對應(yīng)的更新算法的空間開銷和訪問節(jié)點(diǎn)數(shù)量。可以看到，訪問節(jié)點(diǎn)單位平均數(shù)量約等于索引集中每節(jié)點(diǎn)索引的平均長度；k不大于32時(shí)，訪問節(jié)點(diǎn)單位平均數(shù)量和索引集總長度單位平均增長率都較小，此時(shí)更新算法的空間開銷和訪問節(jié)點(diǎn)數(shù)量較小。

表2 k對更新算法空間開銷和平均訪問節(jié)點(diǎn)數(shù)量的影響

圖3顯示了k=16時(shí)更新量對單位平均更新時(shí)間與訪問節(jié)點(diǎn)單位平均數(shù)量的影響。可以看到三項(xiàng)數(shù)值都隨著更新量的增大而增大，但增長較為緩慢，且自循環(huán)標(biāo)記表單位平均更新時(shí)間僅為微秒級。由此說明算法在大更新量下仍能保持較好的性能。

圖3 更新量對更新算法時(shí)間開銷和訪問節(jié)點(diǎn)數(shù)量的影響

4 結(jié) 語

本文對于動(dòng)態(tài)更新的有向帶權(quán)圖中的top-k最短路徑問題設(shè)計(jì)并分析了基于2-hop cover的算法。更新算法利用預(yù)處理得到的索引集來更新，從而顯著地減少了圖改變后計(jì)算top-k的時(shí)間，只需要消耗更新算法的時(shí)間，而且有效地利用了原圖的數(shù)據(jù)集和性質(zhì)。

本文在理論上證明了更新算法的正確性，分析了時(shí)間復(fù)雜度，證明其更新時(shí)間遠(yuǎn)小于將更新后的圖看作靜態(tài)圖重新預(yù)處理的計(jì)算時(shí)間，并用實(shí)驗(yàn)評估了更新算法處理大規(guī)模網(wǎng)絡(luò)的實(shí)際性能，證實(shí)了其實(shí)用性。動(dòng)態(tài)top-k更新算法在大規(guī)模圖上可以進(jìn)行快速更新和查詢。在未來研究工作中，我們將研究對于批量的更新如何提高效率、減少時(shí)間，以此來提高更新算法在實(shí)際應(yīng)用中的性能。