王一舒 袁 野 劉 萌 王國(guó)仁

1(東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 沈陽(yáng) 110004) 2 (北京理工大學(xué)計(jì)算機(jī)學(xué)院 北京 100081) (yishuwang@stumail.neu.edu.cn)

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

時(shí)序圖(temporal graph，也被稱(chēng)為temporal net-work[2-3]，time-dependent network[4]，time-varying graph[5])是一種會(huì)隨著時(shí)間不斷變化的圖結(jié)構(gòu).時(shí)序圖本質(zhì)上是帶有隨時(shí)間變化標(biāo)簽(label)的圖，即圖中的標(biāo)簽帶有某種特定的時(shí)間屬性.與強(qiáng)調(diào)維護(hù)查詢(xún)處理與挖掘結(jié)果正確性的動(dòng)態(tài)圖(dynamic graph)和對(duì)過(guò)去快照(snapshot)進(jìn)行查詢(xún)的歷史網(wǎng)絡(luò)(historical network)不同，時(shí)序圖強(qiáng)調(diào)在一個(gè)時(shí)間閾值內(nèi)數(shù)據(jù)的變化.時(shí)序圖的應(yīng)用非常廣泛，許多網(wǎng)絡(luò)模型都可以通過(guò)時(shí)序圖來(lái)構(gòu)建模型，或者說(shuō)只要存在動(dòng)態(tài)邏輯的圖都可以通過(guò)時(shí)序圖建模和研究.常見(jiàn)的時(shí)序圖應(yīng)用有5個(gè)方面：

1) 點(diǎn)對(duì)點(diǎn)通信

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

2) 一對(duì)多的消息傳播

與一對(duì)一的通信網(wǎng)絡(luò)不同，一對(duì)多的消息傳播形式更多是強(qiáng)調(diào)單一個(gè)體對(duì)一個(gè)群體進(jìn)行消息的傳播，即消息以廣播的形式擴(kuò)散，最常見(jiàn)的一對(duì)多的傳播形式是微博和朋友圈.現(xiàn)有的研究大多還沒(méi)有將時(shí)間維度作為一個(gè)考慮因素，但是Yasseri等人在文獻(xiàn)[7]中分析維基百科的編輯們活動(dòng)的作息規(guī)律時(shí)，引入了時(shí)間維度來(lái)估計(jì)編輯們的地理位置.

3) 生物信息網(wǎng)絡(luò)

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

4) 道路交通網(wǎng)絡(luò)

道路交通網(wǎng)絡(luò)是指各種運(yùn)輸網(wǎng)、郵電網(wǎng)構(gòu)成的整體交通網(wǎng).道路交通網(wǎng)絡(luò)通常有一些固定的網(wǎng)絡(luò)路線，有一組運(yùn)輸單位在這些路線上隨時(shí)間不斷地改變位置.道路交通網(wǎng)絡(luò)可以說(shuō)是最適合用時(shí)序圖建模的網(wǎng)絡(luò)之一，因?yàn)楹芏嗲闆r下，在道路交通網(wǎng)絡(luò)上時(shí)間本身就是一個(gè)必須考慮的因素，例如航班運(yùn)輸網(wǎng)絡(luò)中，當(dāng)需要轉(zhuǎn)乘航班時(shí)，轉(zhuǎn)乘航班的起飛時(shí)間必須在轉(zhuǎn)乘之前的航班到達(dá)之后，才能保證轉(zhuǎn)乘成功.文獻(xiàn)[12]就是以火車(chē)行程表為例，給出了在時(shí)序圖上的可達(dá)性查詢(xún)和基于時(shí)間的路徑查詢(xún)方法.

5) 在線社交網(wǎng)絡(luò)

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

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

Fig.1 Difference between static graph and temporal graph, and the time sequence of temporal graph圖1 靜態(tài)圖和時(shí)序圖的區(qū)別以及時(shí)序圖中的時(shí)間序列

1 時(shí)序圖數(shù)據(jù)定義與模型

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

1.1 時(shí)序圖基本定義

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

時(shí)序圖可以分為2種情況:1)頂點(diǎn)間的相互作用.是指在一個(gè)確切時(shí)間上發(fā)生的、持續(xù)時(shí)間可以忽略不計(jì)的時(shí)序圖，即λ(e)=0.在這種情況下，時(shí)序圖可以用三元組(u,v,t)表示，對(duì)于e存在一組時(shí)間序列Te={t1,t2,…,tn}作為標(biāo)簽.這種時(shí)序圖常用來(lái)表示郵件網(wǎng)絡(luò)、電話(huà)網(wǎng)絡(luò)、信息網(wǎng)絡(luò)等即時(shí)通信網(wǎng)絡(luò)或者持續(xù)時(shí)間不重要的網(wǎng)絡(luò).2)時(shí)序圖中的邊在時(shí)間閾值中被激活，即λ(e)≠0.這種時(shí)序圖常用來(lái)表示持續(xù)時(shí)間很重要的時(shí)序圖，例如在道路交通網(wǎng)絡(luò)中，常用這種時(shí)序圖來(lái)表示飛機(jī)運(yùn)輸網(wǎng)絡(luò)，用頂點(diǎn)表示機(jī)場(chǎng)，頂點(diǎn)間的邊表示2個(gè)機(jī)場(chǎng)之間存在航班，邊上時(shí)間的標(biāo)簽表示在標(biāo)簽時(shí)間時(shí)有飛機(jī)經(jīng)過(guò).雖然，時(shí)序圖上部分拓?fù)浣Y(jié)構(gòu)的性質(zhì)與靜態(tài)圖類(lèi)似，如頂點(diǎn)的定義.但是由于時(shí)序圖引入了時(shí)間標(biāo)簽，頂點(diǎn)與頂點(diǎn)的關(guān)系將會(huì)受到時(shí)間影響，所以一些圖上的基本拓?fù)湫再|(zhì)不能直接引用靜態(tài)圖上的定義，而動(dòng)態(tài)圖上很多拓?fù)湫再|(zhì)是不能被定義的，只能根據(jù)動(dòng)態(tài)圖的性質(zhì)提出信息維護(hù)方式來(lái)找到這些性質(zhì).下面本文將根據(jù)靜態(tài)圖上的定義，給出常見(jiàn)時(shí)序圖上的拓?fù)湫再|(zhì)定義.

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

在靜態(tài)圖中，頂點(diǎn)之間的距離(distance)是指2個(gè)頂點(diǎn)之間的最短路徑長(zhǎng)度；在時(shí)序圖中，頂點(diǎn)之間的距離是指2個(gè)頂點(diǎn)可達(dá)的最短時(shí)間.在靜態(tài)圖中，圖的直徑(diameter)是指任意2個(gè)頂點(diǎn)距離最大值；在時(shí)序圖中，2個(gè)頂點(diǎn)不是在任意時(shí)間都是連通的，因此時(shí)序圖的直徑是最小的頂點(diǎn)距離，以此來(lái)保證在時(shí)序圖G的激活時(shí)間內(nèi)，不會(huì)有過(guò)多的頂點(diǎn)距離小于直徑.

1.2 時(shí)序圖模型

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

Fig.2 Graph transformation from temporal graph to static graph圖2 時(shí)序圖轉(zhuǎn)化為靜態(tài)圖實(shí)例

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

2 時(shí)序圖數(shù)據(jù)查詢(xún)處理方法

靜態(tài)圖的拓?fù)浣Y(jié)構(gòu)可以通過(guò)大量的特征信息來(lái)度量[19]，這些特征信息一般是基于頂點(diǎn)之間的鄰接關(guān)系(如頂點(diǎn)的度或聚類(lèi)系數(shù))或者較大的頂點(diǎn)集合之間的連接關(guān)系(如網(wǎng)絡(luò)直徑).這些特征信息的度量方式在靜態(tài)圖中已經(jīng)非常成熟，有些方法只需要稍作改變就可以直接應(yīng)用到時(shí)序圖中，如時(shí)序圖中頂點(diǎn)的度是由某一時(shí)間時(shí)間閾值內(nèi)激活的邊的數(shù)量決定的.但是大部分的方法并不能很好地適應(yīng)時(shí)序圖，如時(shí)序圖中路徑是隨時(shí)間不斷變化的，若想要研究2個(gè)頂點(diǎn)之間的路徑，要考慮時(shí)間先后對(duì)路徑的影響.下面本文將介紹4個(gè)時(shí)序圖上已經(jīng)提出的查詢(xún)處理問(wèn)題.

2.1 時(shí)序圖上路徑問(wèn)題

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

時(shí)序圖上的路徑查詢(xún)比靜態(tài)圖上的路徑查詢(xún)更為復(fù)雜，簡(jiǎn)單的求2個(gè)頂點(diǎn)間的最短路徑已經(jīng)不能滿(mǎn)足時(shí)序圖上的查詢(xún)需求.在時(shí)序圖上，路徑問(wèn)題要考慮2個(gè)部分：時(shí)間和路徑長(zhǎng)度.經(jīng)典的時(shí)序圖上的路徑問(wèn)題有最早到達(dá)路徑(earliest arrival path，EAP)、最遲離開(kāi)路徑(latest departure path，LDP)和最短持續(xù)時(shí)間路徑(shortest duration path，SDP)[25].

1) EAP問(wèn)題

EAP問(wèn)題是指給定2個(gè)頂點(diǎn)u和v和起始時(shí)間戳t，求從頂點(diǎn)u出發(fā)到達(dá)頂點(diǎn)v的需要的最短時(shí)間，即求從站A到達(dá)站B所需的最短時(shí)間和應(yīng)該選擇的路徑.

2) LDP問(wèn)題

LDP問(wèn)題是指給定2個(gè)頂點(diǎn)u和v的終止時(shí)間戳t′，求若在時(shí)刻t′之前從頂點(diǎn)u出發(fā)到達(dá)頂點(diǎn)v，最遲從頂點(diǎn)u出發(fā)的時(shí)間，即如果計(jì)劃在時(shí)刻t′之前到達(dá)站B，求最晚從站A出發(fā)的時(shí)間和應(yīng)該選擇的路線.

3) SDP問(wèn)題

SDP問(wèn)題是指給定2個(gè)頂點(diǎn)u和v、起始時(shí)間戳t和終止時(shí)間戳t′，求在時(shí)間[t,t′]內(nèi)，從頂點(diǎn)u出發(fā)到達(dá)頂點(diǎn)v最快的路徑，即最晚時(shí)刻t從站A出發(fā)，最遲時(shí)刻t′到達(dá)站B，求所需時(shí)間最短的路徑.

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

Fig.3 A temporal graph of traffic network圖3 車(chē)輛交通網(wǎng)絡(luò)的時(shí)序圖

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

因?yàn)榛谪澬乃惴ǖ穆窂讲樵?xún)思路比較簡(jiǎn)單，查詢(xún)的效率也比較低，所以文獻(xiàn)[26-27]提出了一種基于圖轉(zhuǎn)化的路徑查詢(xún)方法.這種圖轉(zhuǎn)換方法的基本思想是為時(shí)序圖中的頂點(diǎn)構(gòu)建副本，構(gòu)成我們熟悉的靜態(tài)圖，然后在靜態(tài)圖上進(jìn)行路徑查找.將時(shí)序圖轉(zhuǎn)換為靜態(tài)圖后，通過(guò)廣度優(yōu)先遍歷就可以直接解決時(shí)序圖上的路徑問(wèn)題.由于將時(shí)序圖轉(zhuǎn)化為靜態(tài)圖后會(huì)增大原有的圖規(guī)模，而且廣度優(yōu)先遍歷的效率相對(duì)較低，所以該方法不能很好地適用于大規(guī)模圖數(shù)據(jù)上.因此在文獻(xiàn)[27]最后給出了時(shí)序圖上并行處理路徑問(wèn)題的方法.

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

2.2 時(shí)序圖上可達(dá)性查詢(xún)問(wèn)題

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

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

2.3 時(shí)序圖上精確匹配問(wèn)題

圖上的精確匹配是目前應(yīng)用最為廣泛的圖匹配技術(shù)，精確匹配問(wèn)題是指給定數(shù)據(jù)圖g和查詢(xún)圖q，判斷g中是否有與q同構(gòu)的子圖.現(xiàn)有的在靜態(tài)圖上的子圖同構(gòu)方法可以分為2類(lèi)：使用索引的方法[35-38]和不使用索引的方法[39-41].而在時(shí)序圖中，若使用索引的方法來(lái)實(shí)現(xiàn)精確圖匹配，則在構(gòu)建索引時(shí)需要考慮時(shí)間的因素，這使得索引規(guī)模擴(kuò)大.而在時(shí)序圖中采用回溯的方法，由于時(shí)間會(huì)影響頂點(diǎn)之間的關(guān)系，所以很難得到查詢(xún)圖每個(gè)頂點(diǎn)的候選集.并且與靜態(tài)圖的精確匹配不同，時(shí)序圖的精確匹配分為2種情況：

1) 時(shí)序圖上的靜態(tài)圖匹配

時(shí)序圖上的靜態(tài)圖匹配是指數(shù)據(jù)圖為時(shí)序圖，查詢(xún)圖為靜態(tài)圖.

2) 時(shí)序圖上的時(shí)序圖匹配

時(shí)序圖上的時(shí)序圖匹配是指數(shù)據(jù)圖為時(shí)序圖，查詢(xún)圖也為時(shí)序圖.

對(duì)于時(shí)序圖上的靜態(tài)圖匹配只需考慮數(shù)據(jù)圖上的時(shí)間信息，然后參考靜態(tài)圖上精確匹配的方法，即可得到匹配結(jié)果.時(shí)序圖上的時(shí)序圖匹配問(wèn)題則更為復(fù)雜，因?yàn)椴粌H需要考慮數(shù)據(jù)圖上的時(shí)間信息，還需要考慮查詢(xún)圖上的時(shí)間信息，這使得構(gòu)建查詢(xún)候選集的工作更為復(fù)雜.如圖4所示為時(shí)序圖精確匹配的2種情況，其中圖4(a)表示數(shù)據(jù)圖，圖4(b)表示時(shí)序圖上的時(shí)序圖匹配問(wèn)題的查詢(xún)圖，圖4(d)為圖4(b)在圖4(a)中的匹配結(jié)果，邊上的標(biāo)簽標(biāo)示這條邊存在的時(shí)刻數(shù)據(jù)圖中頂點(diǎn)D，C，B分別對(duì)應(yīng)查詢(xún)圖中的a，b，c，其中邊(D,C)出現(xiàn)在邊(C,B)之前，且邊(D,C)在時(shí)間閾值[7,9]內(nèi)，邊(C,B)在時(shí)間閾值[3,4]內(nèi).圖4(c)為時(shí)序圖上的靜態(tài)圖匹配問(wèn)題的查詢(xún)圖，圖4(e)為圖4(c)在圖4(a)中的匹配結(jié)果.

Fig.4 Querying temporal graph and static graph on temporal graph圖4 時(shí)序圖上的靜態(tài)圖匹配和時(shí)序圖匹配問(wèn)題

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

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

2.4 社交網(wǎng)絡(luò)上時(shí)序查詢(xún)問(wèn)題

隨著社交網(wǎng)絡(luò)用戶(hù)的不斷增多，社交信息的數(shù)量越來(lái)越龐大，根據(jù)用戶(hù)和開(kāi)發(fā)者需求進(jìn)行搜索成為了社交網(wǎng)絡(luò)必不可少的功能.在社交網(wǎng)絡(luò)信息數(shù)據(jù)中，時(shí)間維度是最常見(jiàn)也是最重要的信息之一，例如當(dāng)用戶(hù)登錄或注銷(xiāo)賬戶(hù)時(shí)，后臺(tái)數(shù)據(jù)庫(kù)都會(huì)有一個(gè)時(shí)間戳來(lái)記錄此類(lèi)操作；當(dāng)2個(gè)用戶(hù)成為好友時(shí)，后臺(tái)數(shù)據(jù)庫(kù)也會(huì)有一個(gè)時(shí)間戳來(lái)記錄這個(gè)事件；當(dāng)用戶(hù)發(fā)布一條狀態(tài)、圖片或者鏈接時(shí)，這類(lèi)社交活動(dòng)都被記錄在時(shí)間戳上并保存下來(lái).與傳統(tǒng)查詢(xún)只能反映出用戶(hù)之間的關(guān)系不同，引入時(shí)間維度的社交網(wǎng)絡(luò)時(shí)序查詢(xún)可以區(qū)分出新與舊，活躍關(guān)系和不活躍關(guān)系等.包含時(shí)序信息的社交網(wǎng)絡(luò)上的查詢(xún)都是由一組基本查詢(xún)構(gòu)成的，基本的查詢(xún)問(wèn)題包括：

1) FIA查詢(xún)

FIA查詢(xún)是用來(lái)找出參與給定社交活動(dòng)的好友.例如，用戶(hù)想要在他的好友中找到在之前2個(gè)星期中發(fā)表了關(guān)于咖啡的微博.這個(gè)查詢(xún)可以用來(lái)幫助用戶(hù)通過(guò)時(shí)間找到感興趣的事件或者人.

2) UTF查詢(xún)

UTF查詢(xún)是用來(lái)找到在一個(gè)時(shí)間閾值內(nèi)活躍的用戶(hù)，并且該用戶(hù)的好友也參加了給定的興趣活動(dòng).例如廣告商希望找到在最近幾個(gè)月都活躍的用戶(hù)，并且該用戶(hù)的好友已經(jīng)參與了包含利益關(guān)系的活動(dòng)，這樣廣告商就可以通過(guò)好友的影響說(shuō)服用戶(hù)購(gòu)買(mǎi)他們的產(chǎn)品.

3) GURD查詢(xún)

GURD查詢(xún)是用來(lái)將用戶(hù)按照給定數(shù)量分組，每組用戶(hù)間的平均親密度滿(mǎn)足給定值，且所有的成員都參與了相同的活動(dòng).例如，餐館為用戶(hù)發(fā)放優(yōu)惠券，目的是找到4人組(根據(jù)桌子大小)，每組的親密關(guān)系持續(xù)時(shí)間不少于一年，且4位成員都參加該餐館的活動(dòng).

文獻(xiàn)[43]在MVB樹(shù)[44]的基礎(chǔ)上提出了2種適應(yīng)時(shí)序圖的樹(shù)形結(jié)構(gòu)為時(shí)序社交網(wǎng)絡(luò)構(gòu)建索引：TUR樹(shù)和TUA樹(shù).在MVB樹(shù)中每個(gè)葉子頂點(diǎn)表示為key,ts,te，其中key是索引的值，[ts,te)是key的可用時(shí)間閾值.對(duì)于非葉子頂點(diǎn)key,ts,te,subnodeid，subnodeid表示子樹(shù)的根頂點(diǎn).因?yàn)镸VB樹(shù)只能用來(lái)表示用戶(hù)，所以該文提出了TUR樹(shù)用來(lái)表示用戶(hù)關(guān)系.對(duì)于用戶(hù)vi的key，用0|uidi表示，對(duì)于uidi和uidj之間的關(guān)系用1|uidi|uidj表示.當(dāng)用戶(hù)參與一個(gè)活動(dòng)時(shí)，只需要用時(shí)間戳而不是時(shí)間閾值來(lái)表示時(shí)序信息，因此該文在B+樹(shù)和Bloom Filter[90]的基礎(chǔ)上提出了TUA樹(shù)來(lái)為用戶(hù)活動(dòng)構(gòu)建索引.對(duì)于TUA樹(shù)，葉子頂點(diǎn)表示為key,ptr，其中ptr表示活動(dòng)，key表示用戶(hù)的ID和用戶(hù)參與活動(dòng)的時(shí)間，通過(guò)key來(lái)進(jìn)行頂點(diǎn)的拆分，合并和重新分配操作.當(dāng)內(nèi)存溢出時(shí)，進(jìn)行頂點(diǎn)的拆分操作，形成了一個(gè)新的根頂點(diǎn)來(lái)連接2個(gè)葉子頂點(diǎn).然后該文通過(guò)由TUR樹(shù)和TUA樹(shù)構(gòu)建搜索算法來(lái)計(jì)算3個(gè)基本查詢(xún).例如FIA查詢(xún)首先用TUR樹(shù)檢查2個(gè)用戶(hù)之間是否存在關(guān)系，然后通過(guò)TUA樹(shù)判斷用戶(hù)是否參加了相應(yīng)的活動(dòng).

3 時(shí)序圖挖掘方法

數(shù)據(jù)挖掘，也稱(chēng)為知識(shí)發(fā)現(xiàn)(knowledge discovery from dataset，KDD)是用來(lái)抽取數(shù)據(jù)中隱含的、具有潛在用途的、人類(lèi)可以理解的模式[45].長(zhǎng)期以來(lái)，圖數(shù)據(jù)挖掘問(wèn)題得到了廣泛的研究，并且在生物醫(yī)學(xué)、社交網(wǎng)絡(luò)分析等領(lǐng)域得到了廣泛的應(yīng)用，大量的圖數(shù)據(jù)挖掘方法被相繼提出.但是與靜態(tài)圖相比，時(shí)序圖包含了時(shí)間信息，所以圖的結(jié)構(gòu)更為復(fù)雜，頂點(diǎn)和邊包含的信息更多，這為時(shí)序圖上的數(shù)據(jù)挖掘工作帶來(lái)了巨大的挑戰(zhàn).

3.1 時(shí)序圖上最小生成樹(shù)問(wèn)題

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

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

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

MSTa是指對(duì)于一個(gè)生成樹(shù)ST(r)=(VST,EST)，根頂點(diǎn)r，當(dāng)且僅當(dāng)?v∈VST，v≠r，在ST(r)中存在一條路徑P使得r到v之間有最小的持續(xù)時(shí)間時(shí)，則稱(chēng)ST(r)是MSTa.

2) MSTw(具有最小權(quán)重的生成樹(shù))

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

3.2 時(shí)序圖上稠密子圖挖掘問(wèn)題

稠密子圖是指圖中內(nèi)部邊相對(duì)密集的子區(qū)域，即在這個(gè)區(qū)域中頂點(diǎn)與頂點(diǎn)間的關(guān)系相較其他部分更為緊密.稠密子圖問(wèn)題是圖數(shù)據(jù)挖掘中一個(gè)重要的組成部分，是社區(qū)發(fā)現(xiàn)問(wèn)題中基于密度聚類(lèi)的分支，在社交網(wǎng)絡(luò)分析、電子商務(wù)、生物學(xué)等領(lǐng)域應(yīng)用廣泛.此外一些圖上的查詢(xún)處理與挖掘問(wèn)題，如圖聚類(lèi)、圖壓縮、可達(dá)查詢(xún)等，都可以以稠密子圖挖掘?yàn)榛A(chǔ)進(jìn)行研究.現(xiàn)有的許多研究工作都是關(guān)于稠密子圖問(wèn)題的[49-52]，包括極大團(tuán)、k-core、k-truss等.在時(shí)序圖中，稠密子圖會(huì)隨著時(shí)間的不同而不同，而且即使在單一快照中增加或者減少一條邊，找到其中的稠密子圖已經(jīng)是NP問(wèn)題，而時(shí)序圖是由一系列快照組成的，因此如何處理快照之間的聯(lián)系是解決時(shí)序圖上稠密子圖問(wèn)題的核心挑戰(zhàn).

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

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

3.3 時(shí)序圖上k-匿名問(wèn)題

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

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

Fig.6 The framework of k-anonymity on temporal social graph圖6 時(shí)序社交網(wǎng)絡(luò)上的k-匿名方法框架

4 時(shí)序圖數(shù)據(jù)管理系統(tǒng)

目前，已經(jīng)有大量的圖管理系統(tǒng)被提出，包括專(zhuān)門(mén)針對(duì)圖數(shù)據(jù)的系統(tǒng)Neo4j[56]，Titan[57]，大型圖處理框架包括Pregel[58]，GraphLab[59]，GraphX[60]等.但是這些數(shù)據(jù)管理系統(tǒng)都是基于靜態(tài)圖，即使有可以處理時(shí)序圖數(shù)據(jù)的系統(tǒng)，也是基于演化的圖數(shù)據(jù)庫(kù)，即通過(guò)快照來(lái)對(duì)圖數(shù)據(jù)進(jìn)行管理，但是這些系統(tǒng)也只能保留最新的圖快照，無(wú)法獲得任意時(shí)刻上圖的信息.

Fig.7 TGraph data flow architecture圖7 TGraph數(shù)據(jù)流結(jié)構(gòu)

文獻(xiàn)[61]提出了時(shí)序圖管理系統(tǒng)TGraph，該系統(tǒng)是由靜態(tài)圖管理系統(tǒng)Neo4j衍生出來(lái)，其中Neo4j是一個(gè)開(kāi)源的圖數(shù)據(jù)庫(kù)，TGraph用Neo4j存儲(chǔ)圖中的頂點(diǎn)，關(guān)系和靜態(tài)屬性.而對(duì)于動(dòng)態(tài)屬性，如圖7所示，TGraph先將數(shù)據(jù)寫(xiě)入內(nèi)存數(shù)據(jù)結(jié)構(gòu)MemTable中，然后將MemTable寫(xiě)入第0層的磁盤(pán)文件UnStableFile中，根據(jù)時(shí)間的改變依次遞增地合并UnStableFile文件，直到第4層為止.然后將第4層的UnStableFile文件存放入StableFile中.每個(gè)UnStableFile和StableFile都保存了一個(gè)時(shí)間閾值內(nèi)的數(shù)據(jù)，然后用MetaFile記錄每個(gè)文件的名稱(chēng)和其存儲(chǔ)數(shù)據(jù)對(duì)應(yīng)的時(shí)間閾值.

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

為了更好地存儲(chǔ)和管理時(shí)序圖，文獻(xiàn)[63]提出了分布式時(shí)序圖系統(tǒng)，可以根據(jù)制定的時(shí)間點(diǎn)檢索到一個(gè)或多個(gè)歷史快照.該文還提出了類(lèi)樹(shù)形的分布式分層索引結(jié)構(gòu)DeltaGraph，通過(guò)索引記錄時(shí)序圖隨時(shí)間變化的情況，并行地處理快照檢索.DeltaGraph中葉子頂點(diǎn)是時(shí)序圖中等距離選取的快照，邊保存2個(gè)頂點(diǎn)之間的內(nèi)容之差，當(dāng)查詢(xún)某一時(shí)刻的快照時(shí)，只需要找到該時(shí)刻的最小路徑，合并路徑上邊的數(shù)據(jù)，即可獲得所需快照.DeltaGraph通過(guò)分布式的方法提高了時(shí)序圖的存儲(chǔ)效率，但是將時(shí)序圖劃分成快照會(huì)忽略時(shí)間之間的關(guān)聯(lián)，可能會(huì)損失部分信息，對(duì)進(jìn)一步的數(shù)據(jù)管理帶來(lái)不便.

5 總結(jié)與展望

時(shí)序圖是目前最受關(guān)注的圖結(jié)構(gòu)之一，在多個(gè)領(lǐng)域中都有很好的應(yīng)用，因此研究時(shí)序圖上的查詢(xún)處理與挖掘問(wèn)題具有十分重要的理論意義和應(yīng)用前景，引起了學(xué)術(shù)界和工業(yè)界越來(lái)越多的關(guān)注.由于引入了時(shí)間維度并且問(wèn)題的定義與靜態(tài)圖和動(dòng)態(tài)圖不盡相同，時(shí)序圖上的查詢(xún)處理與挖掘問(wèn)題不能完全依照已有的算法來(lái)解決，因此如何在現(xiàn)有的研究基礎(chǔ)上，提出解決時(shí)序圖上的查詢(xún)處理與挖掘問(wèn)題的方法，提高現(xiàn)有算法的效率是今后研究工作的一個(gè)新的探索方向.而且隨著大數(shù)據(jù)時(shí)代的來(lái)到，數(shù)據(jù)規(guī)模不斷擴(kuò)大，數(shù)據(jù)結(jié)構(gòu)越來(lái)越復(fù)雜，這給時(shí)序圖上的查詢(xún)處理與挖掘問(wèn)題帶來(lái)了更新更大的挑戰(zhàn)，同時(shí)也給研究者們帶了更大的機(jī)遇.

雖然時(shí)序圖模型可以有效解決隨時(shí)間變化網(wǎng)絡(luò)中的問(wèn)題，但并不是所有這類(lèi)的問(wèn)題都需要在時(shí)序圖中解決.只有當(dāng)一個(gè)網(wǎng)絡(luò)有時(shí)序性結(jié)構(gòu)，符合時(shí)序圖的框架，并且涉及到時(shí)間標(biāo)度時(shí)才需要用時(shí)序圖來(lái)解決問(wèn)題[64].而且如果動(dòng)態(tài)系統(tǒng)的變換速度遠(yuǎn)快于動(dòng)態(tài)連接的速度，或者圖中的邊是活躍變化的，那么就不需要將動(dòng)態(tài)系統(tǒng)轉(zhuǎn)換成時(shí)序圖[2].例如網(wǎng)絡(luò)中包的傳輸要比拓?fù)渥兓斓枚?，上述這種情況下就不需要在時(shí)序圖上來(lái)解決包傳輸問(wèn)題.總而言之，當(dāng)一個(gè)系統(tǒng)有時(shí)序性并且拓?fù)溥B接遵循一定的動(dòng)態(tài)變化，那么運(yùn)用時(shí)序圖框架來(lái)解決該系統(tǒng)上的問(wèn)題將是一個(gè)非常高效的選擇.下面本文根據(jù)當(dāng)前工作的不足，給出未來(lái)可以研究的3個(gè)方面.

1) 提高時(shí)序圖上查詢(xún)處理與挖掘效率

雖然研究者們已經(jīng)提出了一些時(shí)序圖上的查詢(xún)處理與挖掘方法，但這些方法的效率仍有很大的提升空間.例如在可達(dá)性查詢(xún)問(wèn)題上，時(shí)序圖轉(zhuǎn)換成靜態(tài)圖后會(huì)急劇擴(kuò)大圖的規(guī)模，如果能并行地處理可達(dá)性查詢(xún)問(wèn)題，將會(huì)大大提高查詢(xún)的效率.對(duì)于k-匿名問(wèn)題，現(xiàn)有的方法是基于時(shí)間片的，可是時(shí)序圖中不同時(shí)間閾值內(nèi)頂點(diǎn)之間的影響是不同的，所以如何創(chuàng)建基于時(shí)間閾值的k-匿名隱私保護(hù)方法具有很高的研究?jī)r(jià)值.現(xiàn)有的時(shí)序圖上的查詢(xún)處理與挖掘方法多是基于離散時(shí)間，這種時(shí)序圖在現(xiàn)實(shí)應(yīng)用中較為少見(jiàn)，更多的是連續(xù)時(shí)間上的時(shí)序圖.因此如何擴(kuò)展現(xiàn)有的時(shí)序圖方法，使其不僅適用于離散的時(shí)序圖還適用于連續(xù)的時(shí)序圖，是未來(lái)研究工作需要關(guān)注的重點(diǎn).

2) 提出更多時(shí)序圖上查詢(xún)處理與挖掘方法

雖然研究者們對(duì)時(shí)序圖上的查詢(xún)處理與挖掘問(wèn)題已經(jīng)有了初步的研究工作，但是很多在靜態(tài)圖上已經(jīng)有了深入研究的經(jīng)典問(wèn)題在時(shí)序圖上仍沒(méi)有得到解決.如查詢(xún)處理問(wèn)題中的近似匹配問(wèn)題、子圖同態(tài)問(wèn)題、關(guān)鍵字查詢(xún)問(wèn)題等.還比如挖掘問(wèn)題中的SimRank問(wèn)題、PageRank問(wèn)題、影響力最大化問(wèn)題、頻繁子圖挖掘問(wèn)題等.這些問(wèn)題在實(shí)際生活中都有很高的應(yīng)用價(jià)值，如果能提出適用于時(shí)序圖的方法來(lái)解決這些問(wèn)題，將為圖上后續(xù)研究工作提供良好的基礎(chǔ)和技術(shù)支持.

3) 構(gòu)建統(tǒng)一的時(shí)序圖管理系統(tǒng)

現(xiàn)有的時(shí)序圖管理系統(tǒng)都是在靜態(tài)圖管理系統(tǒng)的基礎(chǔ)上單獨(dú)保存時(shí)序信息，以此完成時(shí)序圖的存儲(chǔ)和管理.這種方法可能會(huì)重復(fù)保存或丟失部分時(shí)間信息，為時(shí)序圖的管理帶來(lái)不便，因此構(gòu)建統(tǒng)一的時(shí)序圖管理機(jī)制尤為重要.而且由于現(xiàn)有的圖規(guī)模越來(lái)越大，集中式存儲(chǔ)已經(jīng)不能滿(mǎn)足人們的需求，分布式存儲(chǔ)成為了最為常見(jiàn)的存儲(chǔ)方式.如果用分布式的方法來(lái)保存時(shí)序圖，就涉及到了圖分割問(wèn)題.如何合理地對(duì)時(shí)序圖進(jìn)行分割，保證時(shí)序圖的結(jié)構(gòu)和時(shí)間信息完整是未來(lái)必須要解決的問(wèn)題.