劉凱洋，范新?tīng)N

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

Bi-BFS：一種新穎的基于時(shí)序圖的可達(dá)性算法

劉凱洋，范新?tīng)N

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

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

可達(dá)性；時(shí)序圖；算法

0 引言

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

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

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

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

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

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

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

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

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

3 改進(jìn)的算法Bi-BFS

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

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

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

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

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

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

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

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

算法1：Bi-BFS算法

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

輸出：true or false

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

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

算法中16-26行為從v出發(fā)倒推，其基本思路與上述類似，因此不再重復(fù)。需要說(shuō)明的是無(wú)論Q1和Q2為空導(dǎo)致退出4-27行的while循環(huán)時(shí)，算法直接判定TR為false。如果TR為真，則必定存在一條從u到v的時(shí)序路徑，因此要么第7行或第18行條件滿足，要么存在w滿足we≤wl（定理1），也即第11行或者第12行條件滿足。因此，如果Q1=?或者Q2=?，TR=false。

我們用下面的例子說(shuō)明改進(jìn)算法的基本思路。給定TR=（GT，A，I，TC），TC=[1，9]，

①首先檢查A的所有出邊，標(biāo)記并入隊(duì)列滿足TC要求的節(jié)點(diǎn)Ft=（1，-MAX），Gt=（3，-MAX），Bt=（1，-MAX）。如圖3（a）中的陰影節(jié)點(diǎn)所示。Fl，Gl，Bl均為-MAX，表示目前我們還未能知道這3個(gè)節(jié)點(diǎn)與終點(diǎn)F之間的時(shí)序可達(dá)性。

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

圖3 改進(jìn)算法的一個(gè)示例

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

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

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

5 結(jié)論

圖4 性能對(duì)比

Bi-BFS算法目前只適應(yīng)于解決簡(jiǎn)單時(shí)序圖上的可達(dá)性查詢，后續(xù)的工作包括如何擴(kuò)展適應(yīng)復(fù)雜時(shí)序圖，如公共交通系統(tǒng)的定時(shí)發(fā)車，周期性的課程安排等；同時(shí)，如何能夠與已有的基于圖的索引相結(jié)合，如2-hop等，從而更好地提升運(yùn)行效率，也是值得研究的方向之一。

[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-），男，湖南益陽(yáng)人，研究生博士學(xué)位，研究方向?yàn)閳D論、最優(yōu)路徑、可達(dá)性

2016-12-15

2017-02-25

范新?tīng)N（1978-），男，河南平頂山人，碩士研究生，教授，研究方向?yàn)檐浖_(kāi)發(fā)模型、大數(shù)據(jù)查詢?cè)O(shè)計(jì)與優(yōu)化、大數(shù)據(jù)挖掘等