大規模時序圖數據的查詢處理與挖掘技術綜述

王一舒 袁 野 劉 萌 王國仁

1(東北大學計算機科學與工程學院 沈陽 110004) 2 (北京理工大學計算機學院 北京 100081) (yishuwang@stumail.neu.edu.cn)

近年來，隨著語義網絡(semantic Web)、社交網絡(social networks)、生物網絡(biological networks)等新興領域的飛速發展，數據的結構越來越復雜，數據量呈幾何狀增長，并且這種增長趨勢還在不斷的持續[1].圖(graph)作為一種特殊的數據存儲模型，在大規模數據中的應用越來越廣泛，實現對復雜數據的存儲和分析.圖作為一種抽象的數據類型，從概念上可以分2種類型：有向圖(directed graph)和無向圖(undirected graph).每個圖數據結構包含了一組頂點(vertices)用來表示對象，頂點間由有向或者無向的邊(edges)連接，用來表示對象與對象之間的二元關系.在實際應用中，圖的頂點和邊上常常帶有特定的信息，像標簽或者數字屬性等(如長度、花銷等).例如，用圖來表示一個城市之間的到達關系，其中每個頂點表示一個城市，若2個頂點之間存在邊，則表示2個城市之間是可以直接到達的，在這種情況下，邊上會有用來表示2個城市之間距離信息的標簽.隨著圖上的研究不斷深入，研究者們發現有些網絡會隨著時間不斷變化，例如在上面的例子中，若在邊上加上表示時間的標簽，那么就可以表示該城市的公交車輛運輸網絡，邊上的時間表示這條道路上公交車的起始時間.如何在這類隨時間變化的圖上進行查詢處理與挖掘工作成為了當前熱門的研究領域，為了更好地為這類隨時間變化的圖構建模型，研究者們提出了一種新型的圖模型——時序圖.

時序圖(temporal graph，也被稱為temporal net-work[2-3]，time-dependent network[4]，time-varying graph[5])是一種會隨著時間不斷變化的圖結構.時序圖本質上是帶有隨時間變化標簽(label)的圖，即圖中的標簽帶有某種特定的時間屬性.與強調維護查詢處理與挖掘結果正確性的動態圖(dynamic graph)和對過去快照(snapshot)進行查詢的歷史網絡(historical network)不同，時序圖強調在一個時間閾值內數據的變化.時序圖的應用非常廣泛，許多網絡模型都可以通過時序圖來構建模型，或者說只要存在動態邏輯的圖都可以通過時序圖建模和研究.常見的時序圖應用有5個方面：

1) 點對點通信

點對點的通信(如信息或電子病毒的動態傳播)是一種一對一的消息傳播形式，這種消息傳播形式非常符合時序圖模型.點對點通信通常分為2種情況：①在某一時刻上將一系列信息從一個人傳播到另一個人，持續時間可以忽略不計，如電子郵件、手機短信或者在線論壇等即時的消息網絡；②在一個時間段上2個人之間的消息傳播，如打電話，這種情況雖然不是即時的，但是有特定的持續時間[6-8].但是在很多情況下這段持續時間可以被忽略不計，在這種情況下打電話就可以被認為是即時的.

2) 一對多的消息傳播

與一對一的通信網絡不同，一對多的消息傳播形式更多是強調單一個體對一個群體進行消息的傳播，即消息以廣播的形式擴散，最常見的一對多的傳播形式是微博和朋友圈.現有的研究大多還沒有將時間維度作為一個考慮因素，但是Yasseri等人在文獻[7]中分析維基百科的編輯們活動的作息規律時，引入了時間維度來估計編輯們的地理位置.

3) 生物信息網絡

常見的生物信息網絡包括：基因調控網絡(gene regulatory networks)、代謝網絡(metabolic net-works)、信號傳導網絡(signal transduction pathway)以及蛋白質互作網絡(protein-protein-interaction networks)，很多情況下這些細胞中分子的相互作用都可以通過圖來構建模型.現有的大部分研究工作都是在靜態圖上進行的，但是在真實世界中，許多生物功能中的連接不是一直處于活躍狀態的，Przytycka等人[9]認為在未來的工作中從靜態網絡分析提升到動態網絡分析是必不可少的，而現在也有一些工作開始考慮時間對蛋白質互作網絡[10]和基因調控網絡[11]的影響.

4) 道路交通網絡

道路交通網絡是指各種運輸網、郵電網構成的整體交通網.道路交通網絡通常有一些固定的網絡路線，有一組運輸單位在這些路線上隨時間不斷地改變位置.道路交通網絡可以說是最適合用時序圖建模的網絡之一，因為很多情況下，在道路交通網絡上時間本身就是一個必須考慮的因素，例如航班運輸網絡中，當需要轉乘航班時，轉乘航班的起飛時間必須在轉乘之前的航班到達之后，才能保證轉乘成功.文獻[12]就是以火車行程表為例，給出了在時序圖上的可達性查詢和基于時間的路徑查詢方法.

5) 在線社交網絡

在線社交網絡如Facebook，Twitter等通過記錄用戶的數字軌跡來研究相關信息.在社交網絡中，僅使用用戶之間的關注信息和好友關系來確定用戶之間的密切程度是不夠的，還需要記錄他們之間更為具體的互動，才能更加精確刻畫用戶之間的關系，而時間是常見的影響因素之一，所以考慮時間的影響是十分必要的.例如在社交網絡中，通常用時間戳(time stamp)來記錄用戶的上線和下線操作；當一個用戶關注另一用戶時，也會存在一個時間戳來記錄這種操作；同理，當用戶取消關注時，這個行為也會被時間戳記錄下來.

現有的絕大多數圖查詢處理與挖掘技術都是應用于靜態圖(static graph)和動態圖上的，研究者們提出了大量的查詢和處理方法來解決圖上數據查詢處理與挖掘時可能遇到的問題.但是，由于時序圖上考慮了時間影響，所以時序圖上的查詢要比靜態圖上更為復雜，如在靜態圖上最簡單的最短路徑查詢，在時序圖上就要更為細致地考慮在某一時間閾值內的最短路徑.同理時序圖上的挖掘問題也需要考慮時間對挖掘結果的影響，如最小生成樹問題，在時序圖上需要考慮滿足特殊時間條件的最小生成樹.而且許多靜態圖上可以在線性時間內解決的問題，在時序圖上會成為NP完全或者NP難問題，如連通分支問題.而在動態圖上，雖然存在著隨著時間變化的動態圖，但是這些動態圖上的方法主要是用來維護圖上的查詢處理與挖掘的增量結果，例如動態圖上的可達性查詢問題是要提出一種方法來維護2個頂點之間的可達性，而時序圖則是要判斷在給定時間內，2個頂點是否是可達的.而動態圖上也可以在P時間內解決的問題，在時序圖上確是NP問題，如最小生成樹問題.因此與動態圖相比，時序圖上的查詢處理和挖掘問題的定義和解決的目標不盡相同.所以隨著時間因素的引入，現有的靜態圖和動態圖上的方法并不能很好地適配于時序圖上，這為時序圖上的查詢處理與挖掘工作帶來了巨大的挑戰.為了解決這些問題，一些基于時序圖上的查詢和處理方法相繼被提出.

Fig.1 Difference between static graph and temporal graph, and the time sequence of temporal graph圖1 靜態圖和時序圖的區別以及時序圖中的時間序列

1 時序圖數據定義與模型

圖是一種數學對象，現實生活中的許多動態系統上的問題可以通過圖來解決，比如社交網絡上消息的傳播、網絡上包的傳輸等，但是其實這些動態系統(如社交網絡，傳輸網絡等)才是研究者們真正感興趣的東西[13].動態系統建模最大的優點在于，它不需要去考慮這些動態系統上實際的動態，只需要考慮動態系統上的行為.即動態系統可以估計網絡上部分與部分之間的影響；也可以計算動態系統的優化程度；還可以查找在系統操作中哪些頂點有相同的作用等[14-17].但是動態網絡的變化多種多樣，為了更好地構建模型，研究者們將其中按照時間變化的動態網絡建模成時序圖，如將時間作為邊上的權值(weight)，通過時間序列來表示頂點和邊之間的連接和交互關系.如圖1所示，圖1(a)表示有4個頂點的靜態圖；圖1(b)表示存在于1～10時間閾值內的時序圖；圖1(c)表示圖1(b)中頂點和邊對應的時間序列.在靜態圖1(a)中，如果頂點A與頂點B相連，而頂點B與頂點C相連，那么A和C之間一定存在一條經過B的路徑使得A和C之間是連通的.但是在時序圖1(b)中如果A和B之間的邊(A,B)存在于時刻{6,8,9}，而B和C之間的邊(B,C)存在于時刻{2,4,6}，那么只有在時刻6時A和C是通過B連通的.因此，在時序圖中，時間是一個非常重的影響因素，頂點與頂點之間的關系也隨著時間不同在不斷地變化，這使得不同時間閾值內圖的結構是完全不同的.因此靜態圖上的定義和模型并不能直接適用于時序圖，下面本文將給出時序圖的基本定義和常見的模型.

1.1 時序圖基本定義

給定一個時序圖G=(V,E)，其中V是G中的一組頂點,E是G中的一組邊.對于一條邊e∈E，用四元組(u,v,t,λ)來表示，其中頂點u,v∈V，t是起始時間(starting time)，λ是從u到v遍歷時間(traversal time)，則從u到v的終止時間(ending time)為t+λ.邊e的起始時間為t(e)，遍歷時間為λ(e)，即e在[t,t+λ]時是被激活的.

時序圖可以分為2種情況:1)頂點間的相互作用.是指在一個確切時間上發生的、持續時間可以忽略不計的時序圖，即λ(e)=0.在這種情況下，時序圖可以用三元組(u,v,t)表示，對于e存在一組時間序列Te={t1,t2,…,tn}作為標簽.這種時序圖常用來表示郵件網絡、電話網絡、信息網絡等即時通信網絡或者持續時間不重要的網絡.2)時序圖中的邊在時間閾值中被激活，即λ(e)≠0.這種時序圖常用來表示持續時間很重要的時序圖，例如在道路交通網絡中，常用這種時序圖來表示飛機運輸網絡，用頂點表示機場，頂點間的邊表示2個機場之間存在航班，邊上時間的標簽表示在標簽時間時有飛機經過.雖然，時序圖上部分拓撲結構的性質與靜態圖類似，如頂點的定義.但是由于時序圖引入了時間標簽，頂點與頂點的關系將會受到時間影響，所以一些圖上的基本拓撲性質不能直接引用靜態圖上的定義，而動態圖上很多拓撲性質是不能被定義的，只能根據動態圖的性質提出信息維護方式來找到這些性質.下面本文將根據靜態圖上的定義，給出常見時序圖上的拓撲性質定義.

頂點之間的連通性(connectivity)是圖中最基本的概念之一，連通性是指一對頂點之間是否存在一條路徑使之連通.任何圖都可以根據其連通性劃分為若干組頂點；這些劃分反過來又為圖上發生的動態操作施加限制.而對于靜態圖，頂點分為連通的和不連通的，連通分量(connected component)被定義為頂點之間存在的路徑點集.而在有向圖中，連通分量分為2種情況：強連通分量(strongly connected component)，即所有頂點對之間都存在一條有向的路徑和弱連通分量(weakly connected component)，即假設邊是無向的，所有頂點之間都存在一條路徑.這2個概念可以推廣到時序圖中.對于時序圖G，當頂點u和頂點v之間存在一條基于時間的有向路徑，則2個頂點是強連通的；當頂點u和頂點v之間存在一條基于時間的無向路徑，則2個頂點是弱連通的.

在靜態圖中，頂點之間的距離(distance)是指2個頂點之間的最短路徑長度；在時序圖中，頂點之間的距離是指2個頂點可達的最短時間.在靜態圖中，圖的直徑(diameter)是指任意2個頂點距離最大值；在時序圖中，2個頂點不是在任意時間都是連通的，因此時序圖的直徑是最小的頂點距離，以此來保證在時序圖G的激活時間內，不會有過多的頂點距離小于直徑.

1.2 時序圖模型

當時間是離散的，時序圖可以簡化成為一個邊e∈E上的標簽都為0或常數的靜態圖G=(V,E).邊上的標簽表示邊被激活(available)的時間，即邊上的標簽為0表示這條邊永遠不會被激活，而當邊上的標簽為常數時，表示這條邊在該常數時刻是被激活的.這里的標簽可以是秒、天、年等，也可以是一些人為且離散的時間度量形式.本文將根據時序圖的特點，介紹3種常見的時序圖建模形式.

Fig.2 Graph transformation from temporal graph to static graph圖2 時序圖轉化為靜態圖實例

第3種是通過時間為頂點構建副本，將時序圖完全地轉換成靜態圖.現有圖上的查詢處理與挖掘方法都是在靜態圖上完成的，大量的靜態圖上的數據查詢處理與挖掘被提出，并且技術已經趨于完善，如果能在不丟失任何信息的前提下，將時序圖轉換成與之等價的靜態圖，為時序圖上的查詢處理與挖掘工作提供良好的基礎.時序圖轉換靜態圖的基本思想是：根據邊上的時間信息為每個頂點創造多個副本，即在同一個時刻的圖中同時存在頂點和頂點的多個副本，通過頂點副本將時序圖轉化為靜態圖.對于時序圖G=(V,E)和靜態圖G=(V,E)，V={v1,v2,…,vn}，則V={(vi,t):1≤i≤n,1≤t≤λ(e),vi=vi}.根據時間戳將圖G水平分層，在每個水平層次包含V的副本，然后根據時間添加頂點與頂點副本之間的邊，并規定邊只能從上層頂點指向下層頂點，即頂點(vi,t)，1≤t<λ(e)和它的一個副本(vi,t+1)之間存在邊e=((vi,t),(vi,t+1)).這種方法通過完全保留頂點之間傳遞信息的方式，將頂點間的信息存儲下來，但是在某些特定情況下，有些邊可以被省略[18].圖2是一個將時序圖轉換成靜態圖的實例.圖2中(a)表示一個時序圖G，每條邊的持續時間為1；圖2(b)表示由G以頂點a為原點，保留所有路徑和時間信息轉換成為靜態圖G.這種建模方法可以使靜態圖上的方法完美移植到時序圖上，這也是現有時序圖上常見的建模形式，但是隨著大數據時代的到來，圖的規模不斷擴大，稠密且大規模的圖數據不斷增多，這種方法使圖的規模激增，因此這種方法不能很好地應用于大圖數據中.

2 時序圖數據查詢處理方法

靜態圖的拓撲結構可以通過大量的特征信息來度量[19]，這些特征信息一般是基于頂點之間的鄰接關系(如頂點的度或聚類系數)或者較大的頂點集合之間的連接關系(如網絡直徑).這些特征信息的度量方式在靜態圖中已經非常成熟，有些方法只需要稍作改變就可以直接應用到時序圖中，如時序圖中頂點的度是由某一時間時間閾值內激活的邊的數量決定的.但是大部分的方法并不能很好地適應時序圖，如時序圖中路徑是隨時間不斷變化的，若想要研究2個頂點之間的路徑，要考慮時間先后對路徑的影響.下面本文將介紹4個時序圖上已經提出的查詢處理問題.

2.1 時序圖上路徑問題

圖上頂點間的路徑(path)表示連接頂點的一條通路.路徑問題是最基本查詢問題之一.在靜態圖中，路徑是從一個頂點出發，到另一個頂點為止的一組邊.最短路徑查詢是最常見的關于路徑的查詢.在靜態圖上最經典的最短路徑查詢算法是Dijkstra[20]算法.文獻[21]提出了一種2-hop算法，這種方法為圖中每個頂點構建索引，記錄該頂點能在2跳內到達的頂點，當查詢2個頂點之間的最短路徑時，只需要查找這2個頂點的索引即可.文獻[22]列舉了大量的最短路徑算法，并通過實驗對這些方法進行了分析和比對.但是在時序圖中，要想找到頂點間的路徑必須考慮路徑邊上激活時間的先后順序.因此在時序圖中，路徑通常被定義為連接頂點集的非遞減連續時間的一組邊的序列，在文獻[23-24]中這種路徑被稱為“依賴時間(time-respecting)的路徑”.

時序圖上的路徑查詢比靜態圖上的路徑查詢更為復雜，簡單的求2個頂點間的最短路徑已經不能滿足時序圖上的查詢需求.在時序圖上，路徑問題要考慮2個部分：時間和路徑長度.經典的時序圖上的路徑問題有最早到達路徑(earliest arrival path，EAP)、最遲離開路徑(latest departure path，LDP)和最短持續時間路徑(shortest duration path，SDP)[25].

1) EAP問題

EAP問題是指給定2個頂點u和v和起始時間戳t，求從頂點u出發到達頂點v的需要的最短時間，即求從站A到達站B所需的最短時間和應該選擇的路徑.

2) LDP問題

LDP問題是指給定2個頂點u和v的終止時間戳t′，求若在時刻t′之前從頂點u出發到達頂點v，最遲從頂點u出發的時間，即如果計劃在時刻t′之前到達站B，求最晚從站A出發的時間和應該選擇的路線.

3) SDP問題

SDP問題是指給定2個頂點u和v、起始時間戳t和終止時間戳t′，求在時間[t,t′]內，從頂點u出發到達頂點v最快的路徑，即最晚時刻t從站A出發，最遲時刻t′到達站B，求所需時間最短的路徑.

文獻[26-27]也將EAP，LDP和SDP問題稱為“Foremost Path”，“Reverse-Foremost Path”和“Fastest Path”問題.如圖3所示是一個包含了6個頂點14條邊的時序圖，頂點表示車站，邊表示車站與車站之間存在一條通路.其中邊上的標簽td,ta表示每條邊的起始時間td和終止時間ta，3種不同帶箭頭的線表示3輛車b1，b2和b3的行駛路程.假設在時刻t=5在車站v5準備前往v1，即查詢EAP問題，那么結果應為在時刻6搭乘b3從v5出發在時刻8到達v1；假設需要在時刻t′=13之前從車站v1到達v4，即查詢LDP問題，那么結果應為在時刻10搭乘b1從v1出發，然后在v2換乘b2，最后乘坐b2在時刻13到達v4；假設在時刻t=5從車站v5出發，要在時刻t′=10之前到達v1，即查詢SDP問題，那么結果應為在時刻6搭乘b3從v5出發在時刻8到達v1.

Fig.3 A temporal graph of traffic network圖3 車輛交通網絡的時序圖

文獻[26-27]提出了基于貪心算法的時序圖上路徑查詢算法.這種算法以經典的Dijkstra算法為基礎，通過枚舉的方式求解EAP，LDP和SDP問題，該方法通過索引Lv來存儲SDP的持續時間信息，Lv中包含了元素[sv,av]，分別記錄了路徑P的起始時間和終止時間.以SDP問題為例，若要查找頂點u和v之間最短持續時間路徑，首先初始化sv=t，av=t′，然后判斷能到達頂點v的邊是否能由頂點u到達，若能，則用較小的持續時間更新Lv，直到找到持續時間最小的路徑為止.

因為基于貪心算法的路徑查詢思路比較簡單，查詢的效率也比較低，所以文獻[26-27]提出了一種基于圖轉化的路徑查詢方法.這種圖轉換方法的基本思想是為時序圖中的頂點構建副本，構成我們熟悉的靜態圖，然后在靜態圖上進行路徑查找.將時序圖轉換為靜態圖后，通過廣度優先遍歷就可以直接解決時序圖上的路徑問題.由于將時序圖轉化為靜態圖后會增大原有的圖規模，而且廣度優先遍歷的效率相對較低，所以該方法不能很好地適用于大規模圖數據上.因此在文獻[27]最后給出了時序圖上并行處理路徑問題的方法.

文獻[25]提出了TTL(timetable labeling)算法為時序的邊構建索引，來解決時序圖上的路徑問題.TTL算法為時序圖G=(V,E)中的每個頂點構建TTL索引.TTL索引分為2個標簽Lin(v)和Lout(v)，每個標簽是由一組標簽l=x,td,ta,b,p組成的規范路徑(canonical path)，對于Lin(v)，x為路徑的起始頂點，v為路徑的終止頂點，td為起始時間，ta為終止時間，b為搭乘的車輛(如果搭乘的車輛不是唯一的則為null)，p為路徑經過的編號最小的頂點(如果沒有則為null)；與Lin(v)不同的是，Lout(v)中v為路徑的起始頂點，x為路徑的終止頂點，而頂點u和v之間的規范路徑P是指u和v之間即是最早到達又是最晚出發的路徑.當給定查詢頂點u和v、起始時間戳t和終止時間戳t′時，只需要從TTL表中找到可能的候選集，然后通過候選集找到符合要求的最短路徑即可.該方法在生成的TTL表時需要消耗大量的時間和空間代價，雖然查詢時間較短，但只適用于中等規模的圖，在稠密圖和大圖中不能很好的應用.

2.2 時序圖上可達性查詢問題

可達性查詢是用來回答在有向圖中，一個頂點到另一頂點之間是否存在路徑的問題.可達性查詢作為最基本的圖數據處理方法之一，在社交網絡、生物信息網絡和語義網中都扮演著重要角色，在多個計算機科學領域，如軟件工程、社交網絡、生物網絡、編程語言、路由規劃等都有很好的應用.在靜態圖中大量可達性索引方法被相繼提出，這些方法大體可以分為2種：只依賴標簽的方法[28-31]；依賴標簽和深度優先遍歷的方法[32-34].只依賴標簽來解決可達性查詢問題，這類方法通常為圖中頂點構建索引，以此來壓縮傳遞閉包，然后通過頂點的標簽關系來實現可達性查詢.依賴標簽和深度優先遍歷的方法是指在可能的情況下，使用標簽來解決可達性查詢問題，對使用標簽不能解決時或者代價太高的部分，用深度優先遍歷來解決.但是由于時序圖中頂點之間的邊會受時間的影響，所以靜態圖上的可達性查詢方法并不能直接移植到時序圖上.

由于靜態圖上的可達性查詢方法已經非常成熟，因此將時序圖轉化成靜態圖，然后通過靜態圖上的可達性查詢方法來處理時序圖上的可達性查詢問題是最為簡單的方法.文獻[12]提出了TopChain方法來解決時序圖上的可達路徑查詢問題.這種方法先通過為每個頂點構建副本，將時序圖完全轉成靜態圖，然后將圖劃分成不相交且包含了圖中所有頂點的鏈，為每個頂點v構建標簽(v.x,v.y)，其中v.x是v所在鏈的編號，v.y是v在鏈中的位置.接下來根據鏈中頂點的關系為每個頂點構建Lin(v)和Lout(v)標簽，Lout(v)中包含了k個鏈序號最小的且v能到達的頂點，同理Lin(v)中包含了k個鏈序號最小的且能到達v的頂點.當判斷2個時序圖中的原頂點u和v在時間閾值[t,t′]中是否可達時，只需要根據2個頂點在時間閾值中的副本{u1,u2,…,un}和{v1,v2,…,vm}上的標簽之間的關系進行判斷即可得到2個頂點間的可達信息.該方法的索引較為簡單，但索引規模較大，只能應用于中小規模的圖，在實際大圖中不能很好的應用.

2.3 時序圖上精確匹配問題

圖上的精確匹配是目前應用最為廣泛的圖匹配技術，精確匹配問題是指給定數據圖g和查詢圖q，判斷g中是否有與q同構的子圖.現有的在靜態圖上的子圖同構方法可以分為2類：使用索引的方法[35-38]和不使用索引的方法[39-41].而在時序圖中，若使用索引的方法來實現精確圖匹配，則在構建索引時需要考慮時間的因素，這使得索引規模擴大.而在時序圖中采用回溯的方法，由于時間會影響頂點之間的關系，所以很難得到查詢圖每個頂點的候選集.并且與靜態圖的精確匹配不同，時序圖的精確匹配分為2種情況：

1) 時序圖上的靜態圖匹配

時序圖上的靜態圖匹配是指數據圖為時序圖，查詢圖為靜態圖.

2) 時序圖上的時序圖匹配

時序圖上的時序圖匹配是指數據圖為時序圖，查詢圖也為時序圖.

對于時序圖上的靜態圖匹配只需考慮數據圖上的時間信息，然后參考靜態圖上精確匹配的方法，即可得到匹配結果.時序圖上的時序圖匹配問題則更為復雜，因為不僅需要考慮數據圖上的時間信息，還需要考慮查詢圖上的時間信息，這使得構建查詢候選集的工作更為復雜.如圖4所示為時序圖精確匹配的2種情況，其中圖4(a)表示數據圖，圖4(b)表示時序圖上的時序圖匹配問題的查詢圖，圖4(d)為圖4(b)在圖4(a)中的匹配結果，邊上的標簽標示這條邊存在的時刻數據圖中頂點D，C，B分別對應查詢圖中的a，b，c，其中邊(D,C)出現在邊(C,B)之前，且邊(D,C)在時間閾值[7,9]內，邊(C,B)在時間閾值[3,4]內.圖4(c)為時序圖上的靜態圖匹配問題的查詢圖，圖4(e)為圖4(c)在圖4(a)中的匹配結果.

Fig.4 Querying temporal graph and static graph on temporal graph圖4 時序圖上的靜態圖匹配和時序圖匹配問題

對于時序圖上的靜態圖匹配問題，文獻[2]根據在子圖同構算法的不同階段使用時間和拓撲信息提出了3種方法：Time before Topology (Ti-To)，Topology before Time (To-Ti)和Time and Topology Together (Ti&To).Ti-To是先從數據圖中提取所有與查詢圖時間相關的子圖，然后應用子圖同構算法找出滿足條件的子圖.其具體做法首先在數據圖的邊上使用廣度優先算法搜索最大時序子圖.在返回時序子圖中依次檢驗是否滿足子圖同構的要求.實驗證明該方法由于得到的子圖可能具有很大程度的重疊，提取步驟非常耗時，因此效率不高.To-Ti是在整個數據圖上進行子圖同構，此時不關注時間信息，然后在返回的每個子圖中檢查時間信息，保留相符的結果.Ti&To是在進行子圖同構的過程中考慮時間限制.同構過程由狀態空間來描述，過程的每一個狀態s描述了一個局部映射結果，在一個狀態s中，首先判斷由查詢圖的一部分與數據圖的一部分組成的候選對是否是同構的，若同構，判斷候選對的時間是否匹配，如果都匹配，則根據候選對中頂點的鄰居頂點向下擴展成為新的候選對，根據上述步驟繼續判斷，直到找出所有滿足條件的子圖.Ti&To的效率要明顯快于Ti-To和To-Ti，尤其當查詢圖路徑較長時，Ti&To表現明顯優于Ti-To和To-Ti方法.但是Ti&To只能用于時序圖上的靜態圖匹配，實際應用有限.

對于時序圖上的時序圖匹配問題，文獻[42]提出了2種用來解決時序圖上的精確匹配的方法：TCGPM-V和TCGPM-E.TCGPM-V是一種基于頂點匹配的模式匹配方法，該方法首先使用深度優先搜索樹找到所有頂點匹配集，然后依據這個匹配集來枚舉出所有可能的時序子圖，從中再找出正確的時序子圖.與TCGPM-V不同的是，TCGPM-E是一種基于邊匹配的模式匹配方法.該算法的主要思想是：首先依據該文提出的排序函數在模式圖中選擇一條計算結果最小的邊；然后在模式圖中計算以所選邊為中心，其所能連接的最多邊的數量r；再在數據圖中找出所有與所選邊匹配的邊集，把數據圖分解為邊集中邊的數量個子圖，每一個子圖中都含邊集中的一條邊并且子圖中邊的數量為r；最后在每一個子圖上做子圖同構匹配，枚舉出匹配的時序子圖.這2種方法雖然可以解決時序圖上的時序圖匹配問題，但是解決思路只是單純地將時間作為一個限制條件，而忽略了時間之間的關聯性.

2.4 社交網絡上時序查詢問題

隨著社交網絡用戶的不斷增多，社交信息的數量越來越龐大，根據用戶和開發者需求進行搜索成為了社交網絡必不可少的功能.在社交網絡信息數據中，時間維度是最常見也是最重要的信息之一，例如當用戶登錄或注銷賬戶時，后臺數據庫都會有一個時間戳來記錄此類操作；當2個用戶成為好友時，后臺數據庫也會有一個時間戳來記錄這個事件；當用戶發布一條狀態、圖片或者鏈接時，這類社交活動都被記錄在時間戳上并保存下來.與傳統查詢只能反映出用戶之間的關系不同，引入時間維度的社交網絡時序查詢可以區分出新與舊，活躍關系和不活躍關系等.包含時序信息的社交網絡上的查詢都是由一組基本查詢構成的，基本的查詢問題包括：

1) FIA查詢

FIA查詢是用來找出參與給定社交活動的好友.例如，用戶想要在他的好友中找到在之前2個星期中發表了關于咖啡的微博.這個查詢可以用來幫助用戶通過時間找到感興趣的事件或者人.

2) UTF查詢

UTF查詢是用來找到在一個時間閾值內活躍的用戶，并且該用戶的好友也參加了給定的興趣活動.例如廣告商希望找到在最近幾個月都活躍的用戶，并且該用戶的好友已經參與了包含利益關系的活動，這樣廣告商就可以通過好友的影響說服用戶購買他們的產品.

3) GURD查詢

GURD查詢是用來將用戶按照給定數量分組，每組用戶間的平均親密度滿足給定值，且所有的成員都參與了相同的活動.例如，餐館為用戶發放優惠券，目的是找到4人組(根據桌子大小)，每組的親密關系持續時間不少于一年，且4位成員都參加該餐館的活動.

文獻[43]在MVB樹[44]的基礎上提出了2種適應時序圖的樹形結構為時序社交網絡構建索引：TUR樹和TUA樹.在MVB樹中每個葉子頂點表示為key,ts,te，其中key是索引的值，[ts,te)是key的可用時間閾值.對于非葉子頂點key,ts,te,subnodeid，subnodeid表示子樹的根頂點.因為MVB樹只能用來表示用戶，所以該文提出了TUR樹用來表示用戶關系.對于用戶vi的key，用0|uidi表示，對于uidi和uidj之間的關系用1|uidi|uidj表示.當用戶參與一個活動時，只需要用時間戳而不是時間閾值來表示時序信息，因此該文在B+樹和Bloom Filter[90]的基礎上提出了TUA樹來為用戶活動構建索引.對于TUA樹，葉子頂點表示為key,ptr，其中ptr表示活動，key表示用戶的ID和用戶參與活動的時間，通過key來進行頂點的拆分，合并和重新分配操作.當內存溢出時，進行頂點的拆分操作，形成了一個新的根頂點來連接2個葉子頂點.然后該文通過由TUR樹和TUA樹構建搜索算法來計算3個基本查詢.例如FIA查詢首先用TUR樹檢查2個用戶之間是否存在關系，然后通過TUA樹判斷用戶是否參加了相應的活動.

3 時序圖挖掘方法

數據挖掘，也稱為知識發現(knowledge discovery from dataset，KDD)是用來抽取數據中隱含的、具有潛在用途的、人類可以理解的模式[45].長期以來，圖數據挖掘問題得到了廣泛的研究，并且在生物醫學、社交網絡分析等領域得到了廣泛的應用，大量的圖數據挖掘方法被相繼提出.但是與靜態圖相比，時序圖包含了時間信息，所以圖的結構更為復雜，頂點和邊包含的信息更多，這為時序圖上的數據挖掘工作帶來了巨大的挑戰.

3.1 時序圖上最小生成樹問題

最小生成樹問題是指為原圖生成原圖的極小連通子圖，該連通子圖包含原圖的所有頂點，且連通子圖的邊數最小.最小生成樹的應用十分廣泛，許多復雜的查詢都基于最小生成樹問題，而且許多高效的圖算法都是以構建最小生成樹為基礎的.所以解決最小生成樹問題是進行時序圖上查詢處理與挖掘問題的基礎.靜態圖上經典的最小生成樹算法是Prim算法[46]和Kruskal算法[47]，這2種方法都是基于貪心算法的，并且都能保證得到全局最優解.由于時序圖引入了時間的因素，因此最小生成樹問題由可以在多項式時間內解決的P問題變成了NP問題，而且其查詢條件也與靜態圖上不同.如圖5所示，時序圖5(a)上的最小生成樹分為2種情況：圖5(b)MSTa和圖5(c)MSTw：

Fig.5 Temporal graph G and two types of minimum spanning tree圖5 時序圖及其2種形式的最小生成樹

1) MSTa(具有最小持續時間的生成樹)

MSTa是指對于一個生成樹ST(r)=(VST,EST)，根頂點r，當且僅當?v∈VST，v≠r，在ST(r)中存在一條路徑P使得r到v之間有最小的持續時間時，則稱ST(r)是MSTa.

2) MSTw(具有最小權重的生成樹)

文獻[48]提出了解決時序圖上最小生成樹的方法.對于MSTa問題，該文作者首先把每條邊按照起始時間的非遞減順序進行排序，然后輸入根頂點和時間閾值，初始化頂點u的到達時間為無窮大，接下來對于序列中的所有邊依次進行判斷，如果該邊的出發時間比上一頂點的到達時間大，或該邊的到達時間比下一頂點的到達時間小，又或者該邊的到達時間比規定的時間閾值的上限小，則將該邊加入到生成樹列表中，最后得到MSTa樹.但是MSTa樹要求每條邊的持續時間不能為零，因此作者對該方法提出了改進.對于u的每一條出邊按照出發時間的非遞增順序進行排列，然后對序列中的邊進行判斷，得到MSTa.對于MSTw問題，作者將其近似為最小斯坦納樹(steiner tree)問題，即找到指定集合中頂點連通且邊權重總和最小的生成樹.該方法為時序圖構建頂點副本，將時序圖完全轉換成靜態圖，然后在靜態圖上構建最小斯坦納樹，從而解決時序圖上的MSTw問題.

3.2 時序圖上稠密子圖挖掘問題

稠密子圖是指圖中內部邊相對密集的子區域，即在這個區域中頂點與頂點間的關系相較其他部分更為緊密.稠密子圖問題是圖數據挖掘中一個重要的組成部分，是社區發現問題中基于密度聚類的分支，在社交網絡分析、電子商務、生物學等領域應用廣泛.此外一些圖上的查詢處理與挖掘問題，如圖聚類、圖壓縮、可達查詢等，都可以以稠密子圖挖掘為基礎進行研究.現有的許多研究工作都是關于稠密子圖問題的[49-52]，包括極大團、k-core、k-truss等.在時序圖中，稠密子圖會隨著時間的不同而不同，而且即使在單一快照中增加或者減少一條邊，找到其中的稠密子圖已經是NP問題，而時序圖是由一系列快照組成的，因此如何處理快照之間的聯系是解決時序圖上稠密子圖問題的核心挑戰.

在時序圖上的稠密子圖問題是挖掘在某個時間閾值上存在稠密子圖，因此找到最可能存在稠密子圖的時間閾值是首先要解決的問題.文獻[53]中提出了一種挖掘稠密時序子圖的方法.這種方法首先將時序圖轉換成一系列時間的快照，通過計算每張快照邊上的權值，為時序圖構建一個橫坐標為時間戳的粘性密度曲線，該文證明了在粘性密度曲線的峰值附近最可能產生時序稠密子圖.所以通過粘性密度曲線，可以得到時序圖上最可能存在稠密子圖的時間閾值.接下來，作者將稠密時序子圖問題轉換成網絡價值最大化問題(net worth maximization optimization problem，NWM)，通過解決NWM問題的思想，在最可能的區間內找到時序圖上的稠密子圖.該方法應用了時間快照的思路，將時序圖分割成為一系列時間快照，這使得時序圖上的時間序列被劃分成為了時間片，而忽略了時間對圖稠密性的影響.

文獻[54]提出一種啟發式稠密子圖搜索策略.該方法先通過剪枝策略移除不存在于時序子圖模式中的頂點和時間閾值，然后在新的時序圖中，該文將該圖劃分成一系列快照，若這些快照是連續的，則按照一定順序移除時序圖中的頂點，然后判斷剩余頂點是否仍能構成完整的時序圖，若能則刪除該頂點與該頂點相連的所有邊；若時間快照是離散的，則根據離散的時間將新的時序圖劃分成多個子圖，然后遞歸地查找這些子圖，找到稠密子圖.該方法在一定程度上保留了時序圖上的時間關聯性，但是完成該算法所需時間較長，在大圖上不能很好地應用.

3.3 時序圖上k-匿名問題

數據挖掘的目的在于從大量的數據中抽取有價值的信息，但是網絡數據不僅保存了常規的瀏覽信息，還包含了許多敏感的私密信息，所以在數據的挖掘和使用的過程中保護個人隱私成為了研究者們考慮的一個重要問題.數據匿名是實現隱私保護的一個有效的手段，即通過隱匿和泛化技術，對數據中的部分信息進行處理，使他人無法從處理后的數據中推理出個人隱私信息.而k-匿名是隱私保護中最普遍使用的一種匿名技術.k-匿名技術最早是由文獻[55]提出，該方法通過隱藏個人標識信息，使得每條記錄至少與數據表中其他k-1條記錄具有完全相同的標識符屬性，發布精度較低的數據，從而減少被其他人推測出用戶身份信息的概率.

文獻[5]提出了一種在時序圖上進行的k-匿名方法.該方法將時序圖和多層網絡相結合，將每個時間片段看作多層網絡的一個層.該方法的流程如圖6所示.給定一個時序圖和期望的匿名k，首先該模型通過k-means衍生算法解決l1范式最小化問題從而得到一組時序度序列，該序列的每個頂點都是匿名的;然后檢查輸出的度序列是否是可實現的，即確保每個度序列都存在與之對應的時間片;最后通過匿名且可實現的度序列生成k-匿名時序圖.該方法將時序圖頂點分成了不小于k個組，每組中頂點擁有相同的時序度向量，并且確保了分組時盡量小的改變圖的結構.該方法雖然解決了時序圖上的k-匿名問題，但是該方法是基于時間片的，即只考慮當前時間的匿名保護，而忽略了時間對頂點關系的影響.

Fig.6 The framework of k-anonymity on temporal social graph圖6 時序社交網絡上的k-匿名方法框架

4 時序圖數據管理系統

目前，已經有大量的圖管理系統被提出，包括專門針對圖數據的系統Neo4j[56]，Titan[57]，大型圖處理框架包括Pregel[58]，GraphLab[59]，GraphX[60]等.但是這些數據管理系統都是基于靜態圖，即使有可以處理時序圖數據的系統，也是基于演化的圖數據庫，即通過快照來對圖數據進行管理，但是這些系統也只能保留最新的圖快照，無法獲得任意時刻上圖的信息.

Fig.7 TGraph data flow architecture圖7 TGraph數據流結構

文獻[61]提出了時序圖管理系統TGraph，該系統是由靜態圖管理系統Neo4j衍生出來，其中Neo4j是一個開源的圖數據庫，TGraph用Neo4j存儲圖中的頂點，關系和靜態屬性.而對于動態屬性，如圖7所示，TGraph先將數據寫入內存數據結構MemTable中，然后將MemTable寫入第0層的磁盤文件UnStableFile中，根據時間的改變依次遞增地合并UnStableFile文件，直到第4層為止.然后將第4層的UnStableFile文件存放入StableFile中.每個UnStableFile和StableFile都保存了一個時間閾值內的數據，然后用MetaFile記錄每個文件的名稱和其存儲數據對應的時間閾值.

TGraph將所有的變化都記錄在內存中，隨著時間的變化，數據的規模會不斷變大，很多數據可能被重復記錄，為了改善這種情況，文獻[62]也在Neo4j基礎上提出了一種利用多層索引結構實現的時序社交網絡數據管理系統.該系統使用可穿戴的傳感器收集隨時間變化的社交網絡數據，這些數據主要包括每對參與者之間建立聯系的起始時間和終止時間，以此來獲得隨時間變化的接近性網絡.頂點之間的邊表示相應時間閾值內參與者之間的接近關系，系統利用Neo4j中的多層索引結構為接近性網絡構建樹形索引，每層樹代表了不同時間尺度(如年、月、日等).該系統雖然通過多層索引結構提高了時序圖的存儲和管理效率，但是圖規模越來越大，集中式的存儲和管理已經不能滿足人們的需求.

為了更好地存儲和管理時序圖，文獻[63]提出了分布式時序圖系統，可以根據制定的時間點檢索到一個或多個歷史快照.該文還提出了類樹形的分布式分層索引結構DeltaGraph，通過索引記錄時序圖隨時間變化的情況，并行地處理快照檢索.DeltaGraph中葉子頂點是時序圖中等距離選取的快照，邊保存2個頂點之間的內容之差，當查詢某一時刻的快照時，只需要找到該時刻的最小路徑，合并路徑上邊的數據，即可獲得所需快照.DeltaGraph通過分布式的方法提高了時序圖的存儲效率，但是將時序圖劃分成快照會忽略時間之間的關聯，可能會損失部分信息，對進一步的數據管理帶來不便.

5 總結與展望

時序圖是目前最受關注的圖結構之一，在多個領域中都有很好的應用，因此研究時序圖上的查詢處理與挖掘問題具有十分重要的理論意義和應用前景，引起了學術界和工業界越來越多的關注.由于引入了時間維度并且問題的定義與靜態圖和動態圖不盡相同，時序圖上的查詢處理與挖掘問題不能完全依照已有的算法來解決，因此如何在現有的研究基礎上，提出解決時序圖上的查詢處理與挖掘問題的方法，提高現有算法的效率是今后研究工作的一個新的探索方向.而且隨著大數據時代的來到，數據規模不斷擴大，數據結構越來越復雜，這給時序圖上的查詢處理與挖掘問題帶來了更新更大的挑戰，同時也給研究者們帶了更大的機遇.

雖然時序圖模型可以有效解決隨時間變化網絡中的問題，但并不是所有這類的問題都需要在時序圖中解決.只有當一個網絡有時序性結構，符合時序圖的框架，并且涉及到時間標度時才需要用時序圖來解決問題[64].而且如果動態系統的變換速度遠快于動態連接的速度，或者圖中的邊是活躍變化的，那么就不需要將動態系統轉換成時序圖[2].例如網絡中包的傳輸要比拓撲變化快得多，上述這種情況下就不需要在時序圖上來解決包傳輸問題.總而言之，當一個系統有時序性并且拓撲連接遵循一定的動態變化，那么運用時序圖框架來解決該系統上的問題將是一個非常高效的選擇.下面本文根據當前工作的不足，給出未來可以研究的3個方面.

1) 提高時序圖上查詢處理與挖掘效率

雖然研究者們已經提出了一些時序圖上的查詢處理與挖掘方法，但這些方法的效率仍有很大的提升空間.例如在可達性查詢問題上，時序圖轉換成靜態圖后會急劇擴大圖的規模，如果能并行地處理可達性查詢問題，將會大大提高查詢的效率.對于k-匿名問題，現有的方法是基于時間片的，可是時序圖中不同時間閾值內頂點之間的影響是不同的，所以如何創建基于時間閾值的k-匿名隱私保護方法具有很高的研究價值.現有的時序圖上的查詢處理與挖掘方法多是基于離散時間，這種時序圖在現實應用中較為少見，更多的是連續時間上的時序圖.因此如何擴展現有的時序圖方法，使其不僅適用于離散的時序圖還適用于連續的時序圖，是未來研究工作需要關注的重點.

2) 提出更多時序圖上查詢處理與挖掘方法

雖然研究者們對時序圖上的查詢處理與挖掘問題已經有了初步的研究工作，但是很多在靜態圖上已經有了深入研究的經典問題在時序圖上仍沒有得到解決.如查詢處理問題中的近似匹配問題、子圖同態問題、關鍵字查詢問題等.還比如挖掘問題中的SimRank問題、PageRank問題、影響力最大化問題、頻繁子圖挖掘問題等.這些問題在實際生活中都有很高的應用價值，如果能提出適用于時序圖的方法來解決這些問題，將為圖上后續研究工作提供良好的基礎和技術支持.

3) 構建統一的時序圖管理系統

現有的時序圖管理系統都是在靜態圖管理系統的基礎上單獨保存時序信息，以此完成時序圖的存儲和管理.這種方法可能會重復保存或丟失部分時間信息，為時序圖的管理帶來不便，因此構建統一的時序圖管理機制尤為重要.而且由于現有的圖規模越來越大，集中式存儲已經不能滿足人們的需求，分布式存儲成為了最為常見的存儲方式.如果用分布式的方法來保存時序圖，就涉及到了圖分割問題.如何合理地對時序圖進行分割，保證時序圖的結構和時間信息完整是未來必須要解決的問題.