Bi-BFS：一種新穎的基于時序圖的可達性算法

劉凱洋，范新燦

（深圳職業(yè)技術(shù)學(xué)院計算機工程學(xué)院，深圳 518055）

Bi-BFS：一種新穎的基于時序圖的可達性算法

劉凱洋，范新燦

（深圳職業(yè)技術(shù)學(xué)院計算機工程學(xué)院，深圳 518055）

隨著海量數(shù)據(jù)的迅猛增長以及大數(shù)據(jù)時代的開啟，涌現(xiàn)出大量的基于超大規(guī)模時序圖的應(yīng)用，并對經(jīng)典圖論算法中的可達性問題提出新的挑戰(zhàn)。傳統(tǒng)的可達性算法缺少對非靜態(tài)性、時效性的充分考慮，因此在時序圖上的運行可能導(dǎo)致錯誤結(jié)果，并且不能充分利用時序圖的特性提升運行效率。考慮到時序性對于時序圖的重要性，提出一種新穎的算法Bi-BFS，通過充分利用結(jié)點之間的時序性約束，并借助于現(xiàn)有的高效索引結(jié)構(gòu)，可以快速地確定超大規(guī)模時序圖上任意兩個結(jié)點之間的可達性。與同類算法之間的實驗表明，新算法的運行效率得到較大的提升。

可達性；時序圖；算法

0 引言

隨著各種智能移動設(shè)備的爆發(fā)性增加，以及新型社交網(wǎng)絡(luò)、基于位置的服務(wù)提供和智能交通系統(tǒng)等網(wǎng)絡(luò)應(yīng)用的不斷涌現(xiàn)，大量的非結(jié)構(gòu)化數(shù)據(jù)采用基于圖的存儲方式。與傳統(tǒng)應(yīng)用產(chǎn)生的數(shù)據(jù)相比，這些應(yīng)用產(chǎn)生的數(shù)據(jù)具有很強的時效性特征，我們稱之為時序圖。時序圖中的邊不是持續(xù)存在，而是具有時效性，可能只在某些特定時間段存在，如公共交通工具的發(fā)車時間，論文之間的相互引用，和分布式計算環(huán)境下各個節(jié)點之間的連通性等。如果一張圖上的邊和節(jié)點的存在是持續(xù)的，不會隨著時間變動，我們將其稱為靜態(tài)圖。通過刪除所有的時序信息，我們可以將一張時序圖轉(zhuǎn)換為對應(yīng)的靜態(tài)圖。

1 時序圖相關(guān)研究

對于時序圖的各種應(yīng)用而言，一個基礎(chǔ)的問題是如何確定時序圖中的兩個節(jié)點之間的可達性。以社交網(wǎng)絡(luò)為例，可能的研究主題是如何確定對象之間的影響度，從而能夠?qū)崿F(xiàn)更高效的廣告投放，或者更準(zhǔn)確的民意調(diào)查預(yù)測。假設(shè)A和B都曾經(jīng)向C成功推薦過產(chǎn)品，但是A是一年之前向C推薦過，而B與C的互動發(fā)生在最近一個月之內(nèi)。顯而易見，與A相比，在當(dāng)前時間節(jié)點B對于C的影響力會更高。如果忽略時效性，則會錯誤的認(rèn)為對于C而言，A和B具有相同的影響度。另外一個例子是公眾信息傳播模型，通過記錄對象之間的社交互動信息，確定信息如何在公眾之間傳播。

圖1（a）中展示了一個公眾互動系統(tǒng)的示例時序圖，節(jié)點表示對象，邊表示對象之間的互動活動，如微信轉(zhuǎn)發(fā)。為簡化表示，我們用整數(shù)表示時間戳。在圖1（a）中，邊（A，B，1）表示B于時間1引用了A的微信文章（為簡單表述，以下我們稱為B引用了A?，F(xiàn)實生活中兩個對象之間的社交互動聯(lián)系可能非常頻密，如G與C之間的三條邊所示，表示C分別于時間1，5，9引用了G。一個可能的查詢是判斷對于時間段[2，5]，A與C是否有過直接或者間接的信息傳播流。因為圖1（a）中存在邊（A，G，3）和邊（G，C，5），意味著C曾經(jīng)引用過G，而G曾經(jīng)于早些時候引用過A，因此A到C之間存在可能的信息傳播。對于時間段[5，9]，則A與C之間不存在這樣的傳播途徑。圖1（b）展示了圖1（a）對應(yīng)的一個靜態(tài)圖。不難發(fā)現(xiàn)，由于缺少時序信息，圖1（b）不能更精準(zhǔn)地捕獲對象之間的互動過程。

現(xiàn)有的關(guān)于時序圖的路徑與可達性的研究主要集中于各種時序路徑的計算，如文獻[4，5，6，9，10，11，12，13]。其中文獻[9]作為較新的算法，主要集中于如何快速計算具備不同時序特征的路徑，如最早出發(fā)路徑，最晚出發(fā)路徑，歷時最短路徑等。由于沒有利用任何索引結(jié)構(gòu)，在最壞情況下，文獻[9]需要掃描整張時序圖，使得其運行時間復(fù)雜度是O（n）。文獻[10]中的算法直接應(yīng)用Dijkstra算法，因此其運行效率不如文獻[9]。除了文獻[9，10，13]之外，其他的研究工作局限于時序圖在某個特定領(lǐng)域的應(yīng)用，如文獻[4]計算兩個結(jié)點之間的連通性（即兩個節(jié)點之間的不相交的路徑數(shù)量），文獻[11]研究信息沿著時序圖擴散的滯后時間（通過計算最晚出發(fā)路徑得到），文獻[5，6]通過計算最早出發(fā)路徑來獲取時序效率（如信息在兩個節(jié)點之間傳播的難易度）和其他一些時序特征。最新的文獻[13]提出了一種稱為TopChain的索引結(jié)構(gòu)用來解決時序可達性問題，但是只索引通過一個節(jié)點的所有路徑中的前k條，因此仍然需要通過在原始時序圖上進行搜索才能得到準(zhǔn)確答案。除此之外，文獻[1，2，3]代表了靜態(tài)圖中可達性問題研究的典型工作，但是將其直接應(yīng)用于時序圖可能會導(dǎo)致錯誤結(jié)果。

圖1 一個示例時序圖及其靜態(tài)圖表示

我們注意到時序圖中節(jié)點的度可能非常高，如一個人可能會在不同時間打多個電話給同一個人/不同人，一個站點可能始發(fā)多個不同班次的公共交通工具，一篇論文可能被多個論文引用等。如果使用文獻[9]中的順序掃描的方式來計算可達性，則不能避免訪問不屬于查詢時間區(qū)間[t1，t2]內(nèi)的邊，導(dǎo)致運行效率低下。因此，我們提出一種新穎的算法Bi-BFS（Bidirectional BFS），通過利用現(xiàn)有的B+-tree索引，快速定位滿足查詢條件的邊，提高運行效率。同時，算法從兩端節(jié)點同時出發(fā)，進行雙向搜索，期望在某個中間節(jié)點相遇，從而以最短時間判斷節(jié)點之間的可達性查詢。通過對不同的數(shù)據(jù)進行試驗表明，Bi-BFS算法可以較大幅度地提升可達性查詢效率。

2 時序可達性及相關(guān)定義

接下來我們定義時序圖上的時序可達性查詢。給定一個查詢時間區(qū)間TC=[ts,te]（ts≤te），時序圖GT上一個可達性查詢TR=（GT，u，v，TC）為判斷u和v之間是否存在一條PT，并且滿足start（PT）≥ts和end（PT）≤te。如果這樣的PT存在，則我們稱u和v在TC區(qū)間內(nèi)是可達，反之則為不可達。考慮圖1（a）中的時序圖，則A和E在區(qū)間[2，6]和[1，5]都是可達，但是對于區(qū)間[4，6]不可達，因為A始發(fā)的邊的開始時間均小于4，因此不存在滿足條件的PT。同樣的查詢?nèi)绻\行在圖1（b）上所示的靜態(tài)圖上，由于時序信息的缺失，會錯誤的判斷A和E在區(qū)間[4，6]間可達。

3 改進的算法Bi-BFS

從上述的時序可達性查詢例子可以看出，由于時序性特征的存在，使得時序可達性查詢具有比靜態(tài)圖的可達性查詢更復(fù)雜的特性。時序可達性查詢不僅要確定兩個節(jié)點之間是否存在路徑，而且還要驗證路徑是否滿足時序性要求，即時序路徑定義中ti+λi≤ti+1。雖然可以通過直接應(yīng)用寬度優(yōu)先遍歷（BFS）或者深度優(yōu)先遍歷（DFS）解決時序可達性問題，但是其在超大規(guī)模時序圖上的運行效率較低，因為需要訪問大量無效的中間節(jié)點。另外一種方式是通過查找兩個節(jié)點之間的時序路徑判斷其可達性，如應(yīng)用文獻[4,5,6,9,10]中的算法。因為未能充分利用時序可達性的特性，與BFS/DFS相比，這些算法運行效率提升有限。

通過上述討論得知，如果充分有效地利用時序遞增性則能避免訪問無效邊，從而提升搜索效率。因此，針對一個節(jié)點u的所有出邊（u，v，t，λ），我們在其t上建立一棵B+-tree。圖2展示了建立于圖1（a）中G節(jié)點所有出邊上的B+-tree，并假設(shè)B+-tree節(jié)點的度為2?？紤]到我們用指針按順序鏈接B+-tree中所有葉子節(jié)點，實現(xiàn)更快的批量載入。以上文中的（D，G，7）為例，通過查詢圖2中的B+-tree得知只有（G，C，9）滿足時序遞增性要求，避免了其余4條邊的訪問。如果以（A，G，3）為例，則首先找到（G，H，4），并通過葉子節(jié)點之間的指針快速提取（G，C，5）、（G，E，5）、（G，C，9）。

當(dāng)為GT中的每個節(jié)點建立B+-tree之后，給定一個時序可達性查詢TR=（GT，u，v，TC），我們可以通過在GT上進行BFS獲得結(jié)果。常規(guī)遍歷算法（BFS或者DFS）從u出發(fā)，期望在某個遍歷過程中到達v，或者未能在TC內(nèi)到達v。如果v距離u較遠（即u到v的路徑較長），或者u到v的時序路徑數(shù)量較少，則BFS算法需要訪問大量的中間節(jié)點；而DFS的運行時間取決于選擇的路徑，其時間效率普遍低于BFS（后續(xù)的實驗中驗證了這一點）。

圖2 圖1（a）中G節(jié)點出邊對應(yīng)的B+-tree

考慮到以上算法的局限性，給定TR=（GT，u，v，TC），我們提出一種改進算法Bi-BFS，從u和v同時出發(fā)進行BFS遍歷，期望在PT的中間節(jié)點相遇（PT為從u到v并且滿足TC的時序路徑）。為方便以下討論，我們?yōu)槊總€節(jié)點w定義一個二元組wt=（we，wl），we表示從u出發(fā)最早到達w的時間，而wl表示從w出發(fā)到達v的最晚出發(fā)時間，并且we∈TC，wl∈TC。初始狀態(tài)下，所有節(jié)點的we=MAX，wl=-MAX。

定理1：給定TR=（GT，u，v，TC），如果存在一個節(jié)點w及wt=（we，wl），we和wl非0，并且we≤wl，則u和v在TC區(qū)間內(nèi)時序可達。反之亦然。

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

總之，隨著信息時代的發(fā)展，社會對于人們的專業(yè)素質(zhì)、專業(yè)知識和專業(yè)能力要求日益提高，新知識、新技術(shù)、新規(guī)范、新理念層出不窮，各個專業(yè)既高度分化又日趨綜合。面對時代的挑戰(zhàn)，高校教育唯有強化通識基礎(chǔ)，融合不同專業(yè)知識，才能培養(yǎng)出高規(guī)格的創(chuàng)新型人才。

算法1：Bi-BFS算法

輸入：一個時序網(wǎng)絡(luò)G=（VT，ET），TR=（GT，u，v，TC），TC=[ts，te]

輸出：true or false

算法1中的1-3行進行初始化工作，4-27行的循環(huán)體為算法主體。每一次循環(huán)時，從u和v交替推進。算法中5-15以u為起點，檢查滿足TC（t∈TC）和時序路徑要求（t≥we）的u的出邊（第6行），如果已經(jīng)到達v（第7行），則返回真值。如果x≠v，則x為中間節(jié)點，并且存在如下兩種情況：

①t＜xe（第9行），意味著當(dāng)前路徑為u到x的最快路徑（到達時間最早），因此算法將xe更新為當(dāng)前到達時間（第10行）。如果更新過的xe和已有xl滿足xe≤xl（第11行），根據(jù)定理1，TR查詢返回真值。否之，將x入隊列（第14行），以便后續(xù)處理。

算法中16-26行為從v出發(fā)倒推，其基本思路與上述類似，因此不再重復(fù)。需要說明的是無論Q1和Q2為空導(dǎo)致退出4-27行的while循環(huán)時，算法直接判定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的所有出邊，標(biāo)記并入隊列滿足TC要求的節(jié)點Ft=（1，-MAX），Gt=（3，-MAX），Bt=（1，-MAX）。如圖3（a）中的陰影節(jié)點所示。Fl，Gl，Bl均為-MAX，表示目前我們還未能知道這3個節(jié)點與終點F之間的時序可達性。

②接下來，搜索I的入邊，尋找并標(biāo)示能在TC時間內(nèi)到達F的節(jié)點，即Ht=（MAX，8），其運行結(jié)果如圖3（b）所示。He=MAX表示目前源點A和H之間的時序可達性未知。

③檢查步驟1入隊列的所有節(jié)點的所有出邊。以B為例，則Ge的值由步驟1里面的3更新為2，表示我們可以更早的從A到達G，即路徑（A，B，G）。當(dāng)檢查F的出邊時，我們計算出He=3，而步驟2中得到Hl=8，因此Ht=（3，8）。根據(jù)定理1，算法結(jié)束并返回true。最終找到的時序路徑如圖3（c）所示。

4 實驗結(jié)果與分析

本節(jié)中我們在數(shù)據(jù)集上進行試驗，展示Bi-BFS算法與現(xiàn)有最新的One-Scan算法[9]之間的性能對比。除了One-Scan算法之外，文獻[9]中還提出了Transformed Graph算法，但是其運行效率不如One-Scan算法，因此試驗只對比Bi-BFS與One-Scan算法。實驗中使用2個真實時序數(shù)據(jù)集：dblp和enron[14]。表1展示了這兩個數(shù)據(jù)集的統(tǒng)計信息。所有試驗均運行在一臺Intel 3.0G CPU和4G內(nèi)存的Windows 7上。

表1 數(shù)據(jù)集統(tǒng)計信息（K=103）

圖3 改進算法的一個示例

為了更好地模擬算法在真實運行環(huán)境下的性能，我們編寫了一個模擬查詢產(chǎn)生器，用來生成隨機的時序可達性查詢。試驗中每次使用一個包括1000個查詢的查詢集，并記錄這個查詢集的平均查詢時間。因為TC的區(qū)間長度對算法效率有著顯著的影響，因此本實驗主要針對4組不同長度的TC=[ts，te]進行對比，即I= te-ts和I4=2I3=2I2=2I1（I2的區(qū)間長度是I1的兩倍，以此類推）。圖4展示不同算法之間的運行時間對比（單位為秒）。

圖4中的實驗對比結(jié)果表明，通過利用B+-tree以及雙向BFS，Bi-BFS算法在兩個實際數(shù)據(jù)集上的效率均優(yōu)于One-Scan算法。雖然隨著TC區(qū)間的擴大以及需要訪問的邊的數(shù)量增加，導(dǎo)致兩個算法的平均運行時間均加大，Bi-BFS的增加幅度大幅小于One-Scan算法，能更好地適應(yīng)大區(qū)間查詢。相比dblp而言，enron的節(jié)點具有更高的度，邊的數(shù)量相對更多，因此Bi-BFS算法可以利用B+-tree快速定位和提取滿足條件的邊，從而實現(xiàn)更好的運行效率。

時序圖中的時序可達性查詢由于其所具有的時序約束特征，使得傳統(tǒng)的可達性算法要么不適用時序圖，要么運行效率低下。本文中提出一個新穎的基于B+-tree的改進算法Bi-BFS，通過利用B+-tree和雙向BFS，大幅提升時序可達性查詢的運行效率。實驗結(jié)果驗證了Bi-BFS能夠更好地適應(yīng)超大規(guī)模數(shù)據(jù)集以及更長的查詢區(qū)間。

5 結(jié)論

圖4 性能對比

Bi-BFS算法目前只適應(yīng)于解決簡單時序圖上的可達性查詢，后續(xù)的工作包括如何擴展適應(yīng)復(fù)雜時序圖，如公共交通系統(tǒng)的定時發(fā)車，周期性的課程安排等；同時，如何能夠與已有的基于圖的索引相結(jié)合，如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，F(xiàn)AN 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-），男，湖南益陽人，研究生博士學(xué)位，研究方向為圖論、最優(yōu)路徑、可達性

2016-12-15

2017-02-25

范新燦（1978-），男，河南平頂山人，碩士研究生，教授，研究方向為軟件開發(fā)模型、大數(shù)據(jù)查詢設(shè)計與優(yōu)化、大數(shù)據(jù)挖掘等