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-），男，河南平頂山人，碩士研究生，教授，研究方向為軟件開發模型、大數據查詢設計與優化、大數據挖掘等