動態圖數據上查詢與挖掘算法的研究綜述

收稿日期：2013-04-24

基金項目：國家自然科學基金（61173023）。

作者簡介：楊雅君（1983-），男，黑龍江哈爾濱人，博士研究生，主要研究方向：挖掘算法；

高宏（1966-），女，黑龍江哈爾濱人，博士，教授，博士生導師，主要研究方向：圖數據管理、海量數據管理、物聯網數據管理；

李建中（1950-），男，黑龍江哈爾濱人，教授，博士生導師，主要研究方向：并行數據庫、無線傳感器網絡、海量數據計算等。

動態圖數據上查詢與挖掘算法的研究綜述

楊雅君， 高宏， 李建中（哈爾濱工業大學 計算機科學與技術學院， 哈爾濱 150001）摘要：近年來，圖數據模型被廣泛地用于刻畫現實世界中各種各樣的實體間的復雜關系。然而，在現實世界中，描述實體對象的圖數據的結構和內容往往不是固定不變的，而是會隨著時間的推移發生演繹與進化。目前，越來越多的研究者開始關注動態圖數據方面的研究問題，也涌現除了很多優秀的研究工作。總結了近年來動態圖上查詢算法與挖掘算法方面的基礎性研究工作，討論了現有的工作和動態圖研究的發展方向。

關鍵詞：動態圖； 查詢算法； 挖掘算法

中圖分類號：TP393 文獻標識碼：A文章編號：2095-2163（2013）04-0024-05

Survey on Querying and Mining Algorithms on Dynamic Graphs

YANG Yajun ， GAO Hong， LI Jianzhong

（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001，China）

Abstract：Recently， graphs has been widely used to model the complexity relationships among various entities in real applications. However， the structure and the content in graphs to describe real entities are always changing with time evolving. Today， more and more research works focus on the dynamic graphs and there exist many excellent results. This paper summarizes the works about querying algorithm and mining algorithm on dynamic graphs in the past year， and also discusses the future work about dynamic graphs.

Key words：Dynamic Graphs； Querying Algorithm； Mining Algorithm

1動態圖研究的背景和應用意義

隨著信息科技與互聯網的高速發展，各個應用領域的信息量都呈現了爆炸性的增長趨勢。因此，不同應用領域各自關注的實體對象之間的關系也變得愈加龐大和復雜。在這些復雜關系的背后，往往蘊含著巨大的科學價值和商業價值。由此，吸引了諸多領域的研究者都開始專注于實體對象之間關系的研究，如計算生物學領域中，蛋白質和酶之間所發生的復雜的交互、調控與代謝關系的研究；社會學領域中，對不同社交網絡中人與人之間交際關系的研究；商業領域中，對金融網絡和貨幣流通網絡中商業關系的研究；以及互聯網搜索領域中，不同網頁之間超鏈接關系的研究。在這些領域中，如果采用傳統的關系數據庫來管理數據對象之間的這些錯綜復雜的關系，會用到巨量且昂貴的連接操作。因此，利用傳統的關系數據庫來研究復雜的結構化數據并不具備現實可行性。“圖”作為離散數學和計算機科學中基本的數據結構，可以有效地表示存在多種關聯的數據以及內部具有一般性結構的數據。圖中，每個頂點代表現實世界中的實體對象；兩個不同頂點之間則可能會存在一條或多條邊，由其代表不同實體之間存在的某種關系。針對這種形式的結構化的數據，研究者們將其稱作“圖數據”。

近年來，圖數據已廣泛地用于刻畫現實世界中各類實體間的復雜關系。例如，傳感器網絡中的節點拓撲結構圖；互聯網領域中的頁面超鏈接關系圖；計算生物學中的蛋白質交互和基因調控網絡；社交網絡中（如新浪微博、微信等）用戶之間交互關系圖及～Email～通信關系圖；物流學領域中的交通網絡、物流網絡等等。這些例子清楚地表示，圖數據現已無處不在，因此，對圖數據進行管理則成為一個迫切重要的問題。由于圖數據具有的重大科學意義和巨大社會價值，數據領域內的頂級學術會議SIGMOD、VLDB、ICDE、KDD以及重要學術會議CIKM、EDBT、ICDM等均設有與圖數據管理有關的研討議程。

然而，在現實世界中，實體對象間的關系卻每時每刻都在發生著變化。以社交網絡為例，根據Facebook網站2010年的Yearbook報告，僅僅2010一年間，其用戶就從3.37億人增至5.85億人，平均每秒新增7.9位用戶，同時，平均每分鐘，會發生47 553個好友關系的建立或解除。2011年，Google+在上線后的兩周時間內，增長了1 000萬的用戶。同年，Twitter～平均每天都活躍著2億的用戶，并且發生著超過16億次的交互。這些數據無不在顯示與說明，現實世界中實體對象間的關系都無時無刻地經歷著變化。因此，描述實體對象的圖數據的結構和內容往往不是固定不變的，而是會隨著時間的推移發生各種演繹與進化的。

動態圖，又稱為演繹圖（evolving graph），是指會隨時間而發生變化的圖模型或者圖數據。動態圖可以根據其變化的形式分為兩類：

（1） 圖中拓撲結構關系發生變化；

（2） 圖中頂點和邊所代表數據對象內容、或者圖中某一特定對象的評價方式發生變化。

由此，可將這兩種情況分別簡稱為圖的結構變化和圖的內容變化。在第一種情況中， 圖中的頂點和邊會隨著時間發生插入和刪除，從而導致圖的結構發生變化。在第二種情況下，頂點或者邊上的權值會隨著時間發生數值上的改變，或者對圖中某一特定對象的評價方式會隨著時間變化。比如，對圖中每條路徑，存在一個評分函數隨時給出該路徑的得分。對一組固定的起點和終點，評分函數不同，其評分最優路徑也就不同。因此，當評分函數隨時間發生變化時，同一對起點和終點間的評分最優路徑也會隨著時間發生相應的變化。

動態圖數據在現實生活中的廣泛存在，比如：在蛋白質交互網絡中，各類蛋白質分子的相互作用有著隊列順序，這使得整個蛋白質交互過程要隨著時間而順序進行；在社會關系網絡中，各類人群和各類團體之間的相互關系也會隨著時間發生變化；在交通網絡中，通過每條公路的時間和費用因交通堵塞的發生均會隨著時間發生變化。因此，對動態圖數據的管理就有著重要的實踐研究意義，主要體現為：在計算生物學領域中，研究基因組結構和功能的協同進化關系；在社會學領域中，通過從動態圖數據挖掘知識，發現各類社會團體之間關系的演變規律和原因；在交通網絡中，通過交通網絡拓撲結構的變化，研究網絡中某區域變化對全局網絡的影響等等。

盡管如此，傳統靜態圖數據上各類問題的解決算法卻無法應用于動態圖數據上各類問題的高效解決，主要有以下幾個原因：第一，傳統的靜態圖模型無法描述圖數據隨時間發生演繹與進化的情況；第二，傳統的靜態圖模型上的各類問題的定義在動態圖數據模型上不再適用；第三，圖數據的動態性使得各類問題的計算復雜性大大增加，原有靜態圖上的各類方法將無法有效地解決這些問題。此外，現有的動態數據管理的研究主要集中于數據流和傳統關系數據的動態維護，但卻無法處理結構復雜的圖數據。因此，必須提出更為優質的方法能夠隨著時間變化高效地維護圖結構，并且能夠實時返回用戶所需要的結果或者從動態圖數據中挖掘得到更加實用的知識。第4期楊雅君，等：動態圖數據上查詢與挖掘算法的研究綜述智能計算機與應用第3卷

2動態圖上的查詢與挖掘算法的研究工作

相比傳統靜態圖數據上的研究，動態圖數據上的研究工作才剛剛起步。但在較近的幾年，越來越多的成果開始在動態圖數據管理研究方面得以展現。在本節中，將對動態圖上的相關工作進行簡單的介紹，包括基于結構變化的動態圖上的研究工作和基于內容變化的動態圖上的研究工作。

2.1基于結構變化的動態圖上的研究工作

過去幾年間，研究者們對拓撲結構關系變化的動態圖相關研究開展了大量效果卓著的工作。這些工作主要集中在以下三個方面：

（1） 圖上經典問題在動態圖上的研究；

（2） 動態圖上子圖模式的研究；

（3） 動態圖上變化探測相關問題的研究。

現在，將在下面幾個專題中對這三方面工作進行分別的討論剖析。

2.1.1圖上經典問題在動態圖上的研究

圖上經典問題主要包括：最短路徑問題、可達性查詢問題、最小生成樹問題和連通分支問題等等。目前，已經見到很多的工作對這些問題進行了研究并取得了頗豐的研究成果。但在動態圖上，這些問題則變得更加復雜。下面，將對動態圖上重要的圖經典問題的相關工作分別加以介紹。

（1）動態圖上最短路徑問題的研究

最短路徑查詢是圖上一個基礎性的查詢問題，其應用十分廣泛。當圖的拓撲結構關系隨時間發生變化時，兩點間的最短路徑也會發生相應的變化。動態圖上最短路徑問題相關工作主要表現在：當圖的拓撲結構發生變化，即頂點和邊發生插入和刪除時，如何維護指定的頂點之間的最短路徑；以及當圖的拓撲結構發生變化，如何為任意圖中兩個頂點實時并迅速地找到兩者之間的最短路徑。其中，某些工作要求動態圖必須滿足一定的性質，如：文獻[1， 2]研究了平面圖 （planar graph） 上的最短路徑維護問題，文獻[3]和文獻[4]研究了非加權圖上最短路徑的維護問題等等。近幾年來，研究者們相繼提出一些新方法，但這些方法均未對圖性質做任何要求[5-11]。下面，即將對其中標志性的工作進行討論與分析。

文獻[5]給出一個全局動態的算法FMN來計算動態圖上的單源最短路徑問題，全局動態 （fully dynamic） 是指圖中的頂點和邊允許發生刪除與插入。與全局動態對應的是衰減動態 （decremental dynamic），卻只是允許圖中發生頂點和邊的刪除操作。給定一個頂點s，該工作的目標是維護頂點s到圖中所有其他頂點的最短距離和最短路徑。在研究中，構建了一棵以s為根的最短路徑樹T，當圖中頂點和邊發生插入和刪除時，算法就對最短路徑樹T進行相應的更新。同時，又定義了邊上“層次”的概念。文獻[5]表明每次更新T需要O（klogn）的平均時間，其中，n為圖中頂點個數，k為圖中邊的最大層次數。此外，文獻[5]也表明，完成最短距離查詢和最短路徑查詢分別需要O（1）和O（L）的時間，這里，L表示最短路徑上邊的數量。盡管FMN 算法回答查詢的時間很短，但是卻需要維護復雜的最短路徑樹結構，這就使得其算法效率并不高超。如文獻[6]中所示，動態算法SWSF-FP 在很多情況下都要優于FMN 算法。

文獻[6]中給出了一個全局動態算法SWSF-FP 來維護動態圖上的最短路徑，該工作要解決的是和文獻[5]中相同的問題。SWSF-FP 算法的主要思想是：為圖中每個頂點維護一個值rhs（v），該值記錄了起點s到頂點v的最短距離。當圖中發生邊的增加和減少時，算法逐步地更新受到這條變化邊影響的頂點上的rhs（v）取值。SWSF-FP算法的缺點是需要頻繁地計算rhs（v），這將導致較高的時間開銷。文獻[7]中對SWSF-F算法進行了改進，并提出一個基于Dijkstra的算法的更新最短路徑樹，使得SWSF-FP算法可以用于具有多重邊的動態圖上。

文獻[8]中提出了一個為圖序列中每一個快照計算兩點間最短路徑的基本框架FVF。該文獻假定在圖的動態演繹過程中，會有一些歷史信息得到保存。該文獻中，動態圖序列根據其相似性可劃分為若干個圖快照的集合。FVF方法為每一個集合保存一個并集圖和一個交集圖，通過并集圖和交集圖上保留的兩點間的最短路徑信息，可以快速回答每個圖快照中兩點間的最短路徑。FVF的方法也存在著不足，其缺點是：通過并集圖和交集圖上的信息，只能找到圖快照上一部分頂點對間的最短路徑。當并集圖和交集圖上的信息不能幫助回答某一對頂點間的最短路徑時，FVF 需要調用靜態圖上的最短路徑算法為該圖快照上的這一對頂點計算彼此之間的最短路徑。

此外，文獻[9]中首次給出了計算動態圖中所有頂點對之間最短路徑的全局動態算法。文獻[10]中則給出了一個改進的算法用于維護動態圖中所有頂點對的最短路徑。

（2）動態圖上最小生成樹問題的研究

文獻[11]中給出了一個全局動態的算法來維護動態圖上的最小生成樹，該方法利用了圖分解理論將圖劃分成一組連通圖的集合。當圖中的邊發生動態更新時（插入或者刪除），只有集合中的一部分連通圖會受到影響。因此，算法將這部分連通圖在最小生成樹上的對應部分更新即可。文獻[11]證明了：對每一次邊的更新，算法維護最小生成樹的時間復雜度均為O（m1/2） ，其中，m表示圖中邊的數量。特別地，當動態圖是一個平面圖時，算法的時間復雜度還可進一步降低為O（（log m）2）。

文獻[12] 采用Sparsification技術對文獻[11] 中的工作進行了改進，使得對每次邊的更新，維護最小生成樹的時間復雜度能夠降至O（n1/2）。文獻[12] 表明，當只允許圖中的邊進行插入更新操作時，可以利用Sleator-Tarja 動態樹來維護動態圖的最小生成樹。此時，對每一次邊的更新，算法均需要O（log n）的時間完成最小生成樹的更新。當只允許圖中的邊進行刪除更新操作時，文獻[12]表明，并不存在全局動態的算法能比O（log n）更快。進一步地，文獻[13]給出了一個最壞情況下時間復雜度為O（log n）的全局動態算法，當動態圖中的邊每次發生更新時（插入或者刪除），該算法用于維護最小生成樹的平攤時間即為O（n1/3 log n） ，而回答最小生成樹的查詢卻只需要O（1）的時間。

（3）動態圖上k連通分支問題的研究

文獻[14]首次研究了動態圖上連通分支（k = 1）的動態維護問題，其中給出一個時間復雜度為O（q+|V ||E|） 的算法，可以實時回答所要查詢的q個頂點是否在同一連通分支中。然而，該工作只能對k=1的連通分支進行動態維護，且只能允許動態圖中發生邊的刪除。

文獻[15]首次提出了一個部分動態算法用于維護2-頂點連通分支。該研究假設動態圖中只會發生頂點和邊的插入更新操作。文中對Sleator-Tarja動態樹結構進行了改進，使其可以適用于文中給出的遞歸算法。文獻[15]表明：對每一次頂點或邊的更新，其維護連通分支的時間復雜度為O（nlog n+m），空間復雜度為O（n）。即便如此，該工作提出的算法也不是全局動態算法，即其僅能處理動態圖中只發生頂點或邊插入更新操作的情況。

文獻[16] 中研究了并行環境下動態圖上對k=2和k=3的k連通分支的維護問題，并給出一系列的理論結果。文獻[17]中提出一個抽象化模型用于描述圖的連通結構，該模型能夠有效地反應動態圖中連通結構的變化，并能回答圖中任意兩個頂點是否屬于同一個5-連通分支。文獻[17]中的方法仍然不是全局動態的，即僅能解決圖中邊只發送插入更新的情況。

目前，在動態圖上，關于圖經典問題的研究工作主要集中在最短路徑維護，最小生成樹維護和k-連通分支維護等問題方面。這些工作只是討論了動態圖上對某些特殊性質進行動態維護的復雜度，以及給出一些理論結果，卻不曾關注圖中“何時”并且“何處”發生了顯著的變化。

2.1.2動態圖上子圖模式挖掘的研究

子圖模式挖掘是圖挖掘中一類十分重要的問題。針對靜態圖上的子圖模式挖掘已經開展了大量深入的研究工作并取得了不俗的研究成果。然而，動態圖上的子圖模式挖掘問題的研究卻只是剛剛開始。目前，動態圖上關于子圖模式的研究主要集中兩方面：動態圖上頻繁子圖模式挖掘和動態圖上緊密子圖挖掘。

動態圖上的頻繁子圖模式挖掘是指在一個圖的演繹過程中（或者演繹圖序列中）找到具有相同變化過程的子圖。目前關于動態圖上的頻繁子圖模式挖掘已經取得了一定的進展，其研究目的都是從動態演繹圖序列中找到一組子圖序列，使得其滿足：

（1） 這些子圖在動態圖序列中的出現是頻繁的；

（2） 這些子圖的圖序列隨時間變化的情況保持一致。

文獻[18]將圖中每一個頂點上或者每一條邊上的一次變化稱為一次“原子操作”，圖序列中任意兩個連續子圖之間的變化可用一系列的原子操作來表達。文中定義了原子操作表達的文法規則，因此，對動態圖上頻繁子圖模式的挖掘等價于在原子操作序列上的頻繁項集的挖掘問題。文獻[18]提出了名為GTRACE 方法來計算序列中具有相同操作順序的原子操作序列，并將其轉化為動態圖上的頻繁子圖模式。

文獻[19]提出一種基于約束的挖掘算法來計算動態圖上具有相同進化模式的頻繁子圖，其目的是根據用戶給出的兩種約束參數：緊密度參數和頻繁度參數，在動態圖序列中找到足夠緊密并且足夠頻繁的具有相同變化模式的子圖。文獻[20]提出了在動態圖序列中尋找一種新的模式，即圖中的某幾部分區域會以一定相關的方式發生進化。文獻[21]研究了如何在動態圖集合中挖掘頻繁子圖模式。在該問題中，動態圖集合是指一些圖的集合，集合中的每一張圖均會隨時間發生變化。文獻[21]的目的是在這些動態圖集合中找到一組具有相同演變模式的頻繁子圖。該問題與圖數據庫中頻繁子圖模式挖掘的問題相類似。文獻[21]對現有靜態圖數據庫中的頻繁子圖模式挖掘算法進行了改進，使其可以適用于動態圖集合上的頻繁子圖模式挖掘問題。文獻[22]研究了在動態圖序列中挖掘具有相同變化模式的頻繁樹結構的問題。文獻[23]中考慮了如何在多項式時間內計算得到周期性或者近似周期性的子圖變化模式。文獻[24，25]則研究了如何在社會網絡的進化過程中找到滿足一定進化規律的團體組織（community） 。

2.1.3動態圖上變化探測相關問題的研究

文獻[26]和文獻[27]利用熵等信息論方法，適當分割圖流，并在每一個流片段中發現相對高度互連的結點社團（community）。文獻[26]提出了一種動態張量分析的方法，將圖的動態演變抽象為一個較小核心張量流和其對應圖的映射矩陣。GraphScope方法[27]用于在大規模的動態演變圖上發現聯系緊密的社團（community），并探測這些社團發生顯著變化的時間。文獻[28，29]提出了三種不同的代價函數，如最大公共子圖，來檢測圖數據流在何時發生了顯著改變。文獻[30]提出了在圖數據流中計算圖與圖之間距離的優化方法。該文定義了圖與圖之間距離的概念，并設計了一個算法，僅需要有限的內存開銷，即能以任意順序處理圖數據流中發生變化的邊。這些方法都提出了各自的目標函數來定義動態圖數據發生顯著變化的概念，但這些代價函數都是落定于動態圖整體來進行考慮的。而在現實世界中，計算動態圖序列中所有子圖的代價函數值卻是不切實際的，因此這些方法都不能發現并確定動態圖中的哪一子部分發生了顯著變化。

2.2基于內容變化的動態圖上的研究工作

基于內容變化的動態圖是指：圖上頂點和邊上的權值會隨著時間發生變化。目前，關于內容變化的動態圖方面的探討主要集中于時間依賴圖上最短路徑的研究。時間依賴圖上邊的代價權值被刻畫為一個會隨著時間的變化而變動的函數。目前，關于時間依賴圖上的最短路徑查詢問題（TDSP）的研究工作已經獲得了長足的進步。然而，這些工作主要解決了最短旅行時間問題，即在時間依賴圖模型上找到一條起點到終點的路徑，使得該路徑的時間代價總和最小。相應工作主要分為兩類，一類是基于離散的時間模型，另一類則基于連續的時間模型。文獻[31-33]研究了離散時間模型下的時間依賴最短路徑查詢。文獻[33]將出發時間區間平滑地離散為多個時間點，并依據這這些時間點將圖中頂點和邊復制多次。因此，時間依賴圖就轉化為一個規模增大的靜態圖。文獻[31]給出方法如何在這個靜態圖上完成最短路徑查詢。只是這一基于離散時間模型的方法并不能回答連續時間模型下的最短路徑查詢問題。文獻[32]中，圖上每一條邊均被賦予一組聚集屬性，該聚集屬性表示了這條邊在不同時刻呈現的狀態。文獻[34-38]研究了連續時間模型下的最短路徑查詢問題。文獻[34]提出了一種基于Bellman-Ford算法思想的求解方法。對圖中任意頂點，該方法迭代計算到達該頂點的最早時刻，并利用這些中間結果，最終計算可得到達終點的最早時刻。最后，根據該時刻找到旅行時間最短的結果路徑。文獻[35]提出了道路網中的速度流模型，該模型下，圖中每條邊的通過速度可以用一個分段線性的函數表示。該文提出一個基于Dijkstra算法思想的方法計算速度流模型下的最快路徑查詢問題。文獻[36]則給出了一種基于A*算法的擴展算法。該算法的主要思想是用一個優先隊列維護所有待擴展的路徑。對任意一個頂點，起點到這個頂點的最早到達時間函數就維護在優先隊列中，該算法通過該頂點到終點的歐氏距離和網絡中的最大速度，實現從頂點到終點的時間預估。算法根據預估時間彈出隊列元素，并找到起點到終點的最短旅行時間路徑。文獻[37]介紹了如何應用數據挖掘的方法找到各種條件下描述道路通過速度的模型。文獻[38]是目前最有效的解決TDSP問題的方法。該方法采用兩階段搜索策略。第一階段，用優先隊列更新圖中所有頂點最早到達的時間函數，并最終計算出終點的最早到達時間函數。第二階段，根據終點的最早到達時間函數找到旅行時間最小的路徑。文獻[39]研究了時間依賴圖下，具有時間限制的代價最優路徑的查詢問題，并給出了一個有效的兩階段算法計算時間限制下的代價最優路徑。

3結束語

動態圖作為現實世界中廣泛存在的結構化數據，已經引起人們越來越多的關注。對動態圖數據管理方面的研究，具有十分重要的學術意義和廣闊的應用前景。本文總結了動態圖數據上查詢與挖掘算法的主要工作，并對未來的研究方向進行了簡要的分析，希望能夠借此推動國內對動態圖數據開展更系統且深入的研究。

參考文獻：

[1]FAKCHAROENPHOL J， RAO S. Planar Graphs， Negative Weight Edges， Shortest Paths， and Near Linear Time [M]. Las Vegas， Nevada， USA： IEEE Computer Society， 2001：232–241.

[2]HM R， PHILIP K， SATISH R， et al. Faster shortest-path algorithms for planar graphs [J]. J. Comput. Syst. Sci.， 1997， 55：3–23.

[3]SURENDER B， RAMESH H， SANDEEP S. Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths [C]//Proceedings of the 34th Annual ACM Symposium on Theory of computing （STOC’02）. Montreal， Quebec， Canada： ACM， 2002：117–123.

[4]FRIGIONI D， MARCHETTI-SPACCAMELA A， NANNI U. Semidynamic algorithms for maintaining single-source shortest path trees [J]. Algorithmica， 1998， 22：250–274.

[5]FRIGIONI D， MARCHETTI-SPACCAMELA A， NANNI U. Fully dynamic output bounded single source shortest path problem [C]//Proceeding of ACM-SIAM Symposium on Discrete Algorithms （SODA’96）. Atlanta， Georgia： ACM， 1996：212–221.

[6]RAMALINGAM G， REPS T. An incremental algorithm for a generalization of the shortest-path problem [J]. J. Algorithms， 1996， 21：267–305.

[7]CHAN E P F， YANG Y. Shortest path tree computation in dynamic graphs [J]. IEEE Trans. Computers， 2009， 58（4）：541–557.

[8]REN C， LO E， KAO B， et al. On querying historical evolving graph sequences [J]. PVLDB， 2011， 4（11）：726–737.

[9]KING V. Fully Dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs[C]//Proceeding of 40th Annual Symposium on Foundations of Computer Science （FOCS’99）. New York， NY， USA： IEEE Computer Society， 1999：81–91.

[10]DEMETRESCU C， ITALIANO G F. A new approach to dynamic all pairs shortest paths [J]. J. ACM， 2004， 51（6）：968–992.

[11]FREDERICKSON G N. Data structures for on-line updating of minimum spanning trees， with applications [J]. SIAM J. Computer.， 1985， 14（4）：781–798.

[12]EPPSTEIN D， GALIL Z， ITALIANO G F， et al. Sparsification： a technique for speeding up dynamic graph algorithms [J]. J. ACM， 1997， 44（5）：669–696.

[13]HENZINGER M R， KING V. Maintaining minimum spanning trees in dynamic graphs [C]// Proceeding of International Colloquium on Automata， Languages and Programming （ICALP’97）. Bologna， Italy： EATCS， 1997：594–604.

[14]EVEN S， SHILOACH Y. An on-line edge-deletion problem [J]. J. ACM， 1981， 28（1）：1–4.

[15]WESTBROOK J， TARJAN R E. Maintaining bridge-connected and biconnected components on-line [J]. Algorithmica， 1992， 7（56）.

[16]LIANG W， BRENT R P， SHEN H. Fully dynamic maintenance of k-connectivity in parallel [J]. IEEE Trans. Parallel Distrib. Syst.， 2001， 12（8）：846–864.

[17]DINITZ Y， NOSSENSON R. Incremental maintenance of the 5-edge-connectivity classes of a graph [C]//Proceeding of Scandinavian Workshop on Algorithm Theory （SWAT’00）. Bergen， Norway： EATCS， 2000： 189-202.

[18]INOKUCHI A， WASHIO T. A fast method to mine frequent subsequences from graphsequence data [C]// Proceeding of the 7th IEEE International Conference on Data Mining （ICDM’08）. Pisa， Italy： IEEE， 2008： 332-341.

[19]ROBARDET C. Constraint-based pattern mining in dynamic graphs [C]// Proceeding of the 7th IEEE International Conference on Data Mining （ICDM’08）. Miami， Florida， USA： IEEE， 2009： 271-280

[20]CHAN J， BAILEY J， LECKIE C. Discovering and summarizing regions of correlated Spatio-Temporal change in evolving graphs[C]// Proceeding of the 7th IEEE International Conference on Data Mining （ICDM’06）. Hong Kong， China： IEEE， 2006： 131-140.

[21]BORGWARDT K M， KRIEGEL H P， WACKERSREUTHER P. Pattern mining in frequent dynamic subgraphs [C]// Proceeding of the 7th IEEE International Conference on Data Mining （ICDM’06）. Hong Kong， China： IEEE， 2006： 257-266.

[22]BIFET A， GAVALD’A R. Mining frequent closed trees in evolving data streams [J]. Intell.Data Anal.， 2011， 15（1）：29–48.

[23]LAHIRI M， BERGER-WOLF T Y. Mining periodic behavior in dynamic social networks [C]// Proceeding of the 7th IEEE International Conference on Data Mining （ICDM’08）. Miami， Florida， USA： IEEE， 2009： 169-178.

[24]TANTIPATHANANANDH C， BERGER-WOLF T Y， KEMPE D. A framework for community identification in dynamic social networks [C]// Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining （KDD’07）. San Jose， California， USA： ACM， 2007： 33-41.

[25]TANTIPATHANANANDH C， BERGER-WOLF T Y. Constant-factor approximation algorithms for identifying dynamic communities [C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining （KDD’09）. Paris， France： ACM， 2009： 102-110.

[26]SUN J， TAO D， FALOUTSOS C. Beyond streams and graphs： dynamic tensor analysis. [C]//Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining （KDD’06）. Philadelphia， PA， USA： ACM， 2006： 37-45.

[27]SUN J， FALOUTSOS C， PAPADIMITRIOU S， et al. Graphscope： parameter-free mining of large time-evolving graphs. [C]// Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining （KDD’07）. San Jose， California， USA： ACM， 2007： 86-94.

[28]SHOUBRIDGE P， MKRAETZL M， WALLIS W D， et al. Detection of abnormal change in a time series of graphs[J]. Journal of Interconnection Networks， 2002，3（1-2）：85–101.

[29]SCHWELLER R T， GUPTA A， PARSONS E， et al. Reversible sketches for efficient and accurate change detection over network data streams[C]//Internet Measurement Conference， 2004.

[30]FEIGENBAUM J， KANNAN S， MCGREGOR A， et al. Graph distances in the data-stream model[J]. SIAM J. Comput， 2008， 38（5）：1709–1727.

[31]CHABINI I. Discrete dynamic shortest path problems in transportation applications： Complexity and algorithms with optimal run time. Transportation Research Record， 1998，1645：170-175.

[32]GEORGE B， SHEKHA S. Time-aggregated graphs for modeling spatio-temporal networks[J]. Journal on Data Semantics XI， 2008：191-212.

[33]NACHTIGALL K. Time depending shortest-path problems with applications to railway networks[J]. European Journal of Operational Research， 1995，83（1）：154-166.

[34]ORDA A， ROM R. Shortest-path and minimum delay algorithms in networks with time-dependent edge-length[J]. Journal of ACM， 1990，37（3）： 607-625.

[35]SUNG K， BELL M G， SEONG M， et al. Shortest paths in a network with time-dependent flow speeds[J]. European Journal of Operational Research， 2000， 123（12）： 32-39.

[36]KANOULAS E， DU Y， XIA T， et al. Finding fastest paths on a road network with speed patterns[C] //Proceedings of the 22th IEEE International Conference on Data Engineering， Atlanta， Georgia， USA， 2006： 10-19.

[37]GONZALEZ H， HAN J， LI X， et al. Adaptive fastest path computation on a road network： a traffic mining approach[C]//Proceedings of the 25th International Conference on Very Large Database . Vienna， Austria， 2007： 794-805.

[38]DING B， YU J X， QIN L. Finding time-dependent shortest paths over large graphs [C]//Proceedings of the 12th International Conference on Extending Database Technology. Nantes， France， 2008： 205–216.

[39]楊雅君， 高宏， 李建中. 時間依賴代價函數下的最優路徑查詢問題研究 [J]. 計算機學報， 2012， 35（11）： 2247-2264.

[40]FRIGIONI D， IOFFREDA M， NANNI U， et al. Experimental analysis of dynamic algorithms for the single source shortest paths problem[J]. Journal of Algorithmics， 1998， 3.

[41]NARVAEZ P， SIU K Y， TZENG H Y. New dynamic algorithms for shortest path tree computation [J]. IEEE/ACM Trans. Network， 2000， 8：734–746.