基于kd-MDD的時序圖緊湊表示

李鳳英 申會強 董榮勝

(廣西可信軟件重點實驗室(桂林電子科技大學) 廣西桂林 541004)

隨著移動互聯網、物聯網等技術的發展，眾多新應用以前所未有的方式和速度產生并積累了海量數據[1].在大數據分析的過程中，圖作為一種有效描述大數據的數據結構，扮演著越來越重要的角色[2-4].時序圖是將時間維度信息添加到圖中的一種多維圖，包含了圖的演化過程，能夠為通信網絡、社交網絡等數據進行建模，例如當用戶添加或刪除在線社交網絡中的朋友時友誼關系的演變、發布新的科研論文時引文網絡的動態性、移動設備更換基站時隨時間變化的連接，或在網絡圖中出現或消失的鏈接的變更等.時序圖包含圖的演變過程，不僅可以獲取頂點之間的連通性的當前狀態，還可以獲取其歷史狀態，可以在不同時間點為諸如通信網絡和社交網絡等應用程序提供信息.如何有效、緊湊地表示包含數億個頂點和邊的時序圖數據，已成為相關領域的研究熱點[5-7].

本文在kd-tree的基礎上，引入多值決策圖(multi-valued decision diagram, MDD)技術，對時序圖的緊湊表示與管理進行研究,主要貢獻有3個方面：

1) 研究了MDD與時序圖之間的關系，設計了一種更加緊湊的時序圖表示方法——kd-MDD.在kd-MDD的構建過程中隱式地合并了kd-tree中的同構子樹，消除冗余節點，使得多維圖數據的存儲結構更加緊湊.

2) 實現了時序圖的動態管理.研究時序圖的查詢及編輯操作與MDD邏輯運算之間的關系，給出了kd-MDD表示下時序圖的增加/刪除邊、增加/刪除頂點等編輯操作的一系列過程，解決了kd-tree不適用于表示動態圖的問題.

3) 在真實的時序圖數據集上進行實驗，結果表明本文給出的kd-MDD方法表示時序圖具有適用性和高效性，為時序圖的緊湊表示和高效處理提供了新的方法和技術.

1 相關工作

隨著網絡技術的飛速發展，數據爆炸式地增長.圖作為描述數據的一種有效數據結構，大規模圖數據壓縮技術越來越受到人們的重視，圖數據的緊湊表示是圖數據壓縮中的一個重要環節和核心問題.為了更加緊湊地表示圖數據，Brisaboa等人[8-9]提出了一種基于k2-tree的表示方法，可以用來緊湊地表示稀疏圖.當使用k2-tree表示稠密圖時，k2-tree的緊湊性較低，原因是在稠密圖中能夠用來壓縮的“0”單元的數量較少[10].隨著圖數據規模的增加，k2-tree表示中產生了大量的同構子樹[11].針對該問題，董榮勝等人[12]提出了k2-MDD，該方法利用MDD的性質來合并同構子樹，進一步提高了圖數據表示的緊湊性.出于對時序圖數據緊湊表示的需要，2013年，Brisaboa等人[13]提出了kd-tree，kd-tree是k2-tree的d維擴展，用于緊湊表示多維圖.2016年，Brisaboa等人[5]為kd-tree提出了2種優化方法：ckd-tree和bckd-tree.無論是kd-tree，還是ckd-tree或bckd-tree，在表示時序圖時都存在大量的同構子樹.針對該問題，本文提出了kd-MDD，解決kd-tree在表示時序圖時出現大量同構子樹的問題，進一步提高時序圖表示的緊湊性.

2 時序圖的kd-MDD表示

k2-tree是一棵用于表示圖的鄰接矩陣的非平衡k2叉樹[9]，是一種能夠有效壓縮和表示圖的鄰接矩陣的方法.在k2-tree結構中，樹的根節點用于表示整個鄰接矩陣，內部節點的“1”表示與葉子節點所在層數對應的鄰接子矩陣，且該鄰接子矩陣中最少有一個“1”元素，每個內部節點都有k2個子節點.樹中的葉子節點可以是0也可以是1，當葉子節點為0時，表示該葉子節點所在層對應的鄰居矩陣所有單元格都為0或者該葉子節點對應一個單元格且元素值為0；當葉子節點為1時，表示該葉子節點對應一個單元格且元素值為1.

給定圖的n×n鄰接矩陣，若n等于k的若干次冪，將其k2等分，即等分成k×k個子矩陣，且每個子矩陣中的單元格個數為n2/k2.當且僅當子矩陣中至少有一個非0單元格時，需要對該子矩陣遞歸地進行k2等分，直至得到了一個所有單元格都為0的子矩陣或者該子矩陣僅包含一個單元格.若n不等于k的若干次冪，對鄰接矩陣的行列進行補0操作，使得矩陣的行列數等于k的若干次冪，再按上述方法構建其對應的k2-tree.

kd-tree是k2-tree的拓展，其被用于處理多維圖的多維矩陣，其中d指的是圖數據的維度[13].kd-tree的構建過程與k2-tree類似，用kd-tree的根節點表示整個d維矩陣，將d維矩陣遞歸地進行kd等分，直至得到一個所有元素都為0的子矩陣或該子矩陣只包含一個元素.需要注意的問題是，d維矩陣的每一維度都必須是相等的，并且是k的若干次冪，否則需要進行補0操作，然后再對其進行遞歸劃分，構建對應的kd-tree.

設F是關于n個變量x1,x2,…,xn的多值函數，可以表示為

F:L1×L2×…×Ln→R，

其中,li={0,1,…,li-1}是變量xi可能的取值，R={r0,r1,…,rh-1}是函數F的值域.

為了表示和操縱多值離散函數，文獻[14]提出了基于香農分解定理的MDD.MDD是具有多個分支的有向無環樹結構[15].如果F表示樹結構中每一層的變量集X={x1,x2,…,xn}上的多值表達式，則可以將標記為xi的非終端節點的MDD形式化定義為

其中xi∈X，MDD有h=|R|個終端節點，分別對應于常數r0,r1,…,rh-1.每個非終端節點表示一個具有li=|Li|個分支的變量xi，每個分支對應于一個多值表達式Fxi=j.因此，MDD的每個非終端節點都有一個具體的布爾表達式.

當2個MDD的變量序相同時，這2個MDD可以進行邏輯運算，得到1個新的MDD.假設W=case(a,Wa=0,Wa=1,…,Wa=la-1)和U=case(b,Ub=0,Ub=1,…,Ub=lb-1)是2個MDD，并且它們具有相同的變量序，則W和U的邏輯運算表示為

其中,“°”表示MDD之間的邏輯運算，例如UNION，DIFFERENCE，INTERSECTION等.Index(a)是變量a在給定變量序中的所在位置.

按照kd-tree的思想對多維圖的多維鄰接矩陣遞歸地進行kd等分，根據劃分結果構建出能表示該多維圖的MDD結構，這樣的MDD稱為kd-MDD.

kd-MDD描述的是一個n元的離散多值函數關系：

f:Z1×Z2×…×Zi×…×Zn→S.

1)n=logkmax(|V|,|T|)，其中V是頂點的集合，T是時間點的集合，max(|V|,|T|)是求2個集合基數中最大值的函數.n的值與對時序圖的多維矩陣遞歸劃分的層數相同.kd-MDD的高度為其劃分層數加1，即n+1.

2)Zi表示對多維矩陣的第i次劃分.Zi={1,2,…,kd}為所有變量的有限值域，與每次對(子)矩陣劃分得到的kd個子矩陣一一對應.

3)S是多值函數f的有限值域，即kd-MDD終端節點的取值范圍，可以是布爾集合、有限整數集合或有限實數集合，本文取有限整數集合.

kd-MDD結構中包含2種節點：內部節點和終端節點.內部節點用xi表示，包含kd個指向其他節點的指針，這些指針與函數f對應，形式化描述為

fxi=c=f(x1,x2,…,xi-1,c,xi+1,…,xn).

kd-MDD中一個內部節點的圖形化描述如圖1所示：

Fig. 1 Graphical description of non-terminal node in kd-MDD圖1 kd-MDD中內部節點的圖形化描述

從圖1可以看出，給定多值變量x1到xn的1組取值，可以得到唯一的終端節點取值.

kd-MDD是一種能夠表示多維圖的MDD，因此其具有與MDD相同的化簡規則，具體有2個規則：

1) 合并規則.合并具有相同值(結構)的終端節點(內部結點).

2) 刪除規則.刪除那些所有指針都指向同一節點的冗余結點.

圖2進一步說明MDD的化簡規則，圖2中的圓圈表示內部節點，方框表示終端節點，邊上的數字表示內部節點的取值，方框中的數字表示函數的取值.圖2(a)表示的是一個未化簡的MDD，該MDD是關于多值函數f=x×y，x∈{1，2，3}，y∈{1，2，3}，函數f的值域為{0，1，2}.圖2(b)是按照合并規則對圖2(a)中的MDD進行合并相同終端節點的結果，合并了圖2(a)中具有相同值的終端節點，合并的終端節點的傳入指針重定向到一個終端節點.圖2(c)是按照合并規則對圖2(b)中的MDD合并相同結構的內部節點產生的結果，節點y1和節點y2是重復的非終節點，合并為1個節點y1，指向節點y2的指針重定向到節點y1.圖2(d)是按照刪除規則對圖2(c)中的MDD進行刪除冗余節點產生的結果，節點y3的所有指針都指向終端節點2，因此節點y3是冗余節點并被刪除，指向節點y3的指針被重定向到終端節點2.

Fig. 2 Simplification rules of MDD圖2 MDD的化簡規則

kd-MDD能更緊湊地表示d維矩陣.大小為n1×n2×…×nd的d維矩陣遞歸地劃分為kd個子矩陣.為了簡化分析，假設對于所有的i，ni=n.表1給出了k=2的kd-tree和kd-MDD表示多維矩陣的示例.從表1的第2行可以看出，在多維矩陣的kd-tree中，每個子樹都有kd個節點，也就是節點數會隨矩陣維數呈指數增加.表1的第3行是多維矩陣的kd-MDD表示，可以看出，不同維度矩陣的kd-MDD節點數沒有特別明顯的變化.

時序圖是頂點之間的連接性隨時間變化的圖.在時序圖G=(V,E)中，V是頂點集合，E是邊集合.E形式為(u,v,t)，表示在時間點t時節點u與節點v相連接.T是t的集合，用函數E(u,v,t)描述在時間點t從頂點u到頂點v的邊，E(u,v,t)=1表示在時間點t頂點u到頂點v之間存在邊，E(u,v,t)=0表示不存在邊.時序圖的鄰接矩陣是多維矩陣，為此，本文提出kd-MDD來緊湊表示時序圖.

Table 1 kd-trees and kd-MDD for Multidimensional Matrix表1 kd-tree和kd-MDD表示多維矩陣

當時序圖稀疏時，其對應的多維矩陣中存在大量的“0”.kd-MDD利用合并規則可消除重復的“0”節點，僅保留一個“0”節點，從而得到稀疏時序圖的緊湊表示.當時序圖稠密時，利用合并規則和刪除規則能夠消除大量重復“1”節點和該多維鄰接矩陣中存在的大量同構子樹，實現更加緊湊的表示.因此，該方法不僅適用于稀疏時序圖，也適用于稠密時序圖.

在時序圖中，max(|V|,|T|)的取值存在2種情況：1)max(|V|,|T|)等于k的若干次冪；2)max(|V|,|T|)不等于k的若干次冪.對于k=2，我們提供2個示例來說明每種情況下kd-MDD的化簡過程.該化簡過程只是為了說明kd-MDD的化簡原理，在實際kd-MDD的構建過程中是直接構建簡化的kd-MDD.

例1.max(|V|,|T|)等于k的若干次冪.

對于圖3所示的時序圖，圓圈中的數字表示頂點，橫坐標表示時間，黑色部分表示與之對應的邊在對應的時間點存在.對于圖3所示的時序圖，其3維矩陣如圖4所示,其中黑色單元格表示時間點t從頂點u到頂點v的邊存在，白色單元格表示該邊不存在.

Fig. 3 Temporal graph of example 1圖3 例1的時序圖

Fig. 4 Three-dimensional matrix of example 1圖4 例1的3維矩陣

圖5給出了圖4所示時序圖的3維鄰接矩陣的k3-tree表示.當使用k3-tree表示3維鄰接矩陣時，3維矩陣等分為k3個部分，并且每個子矩陣包含相同數量的單元格.樹的根節點代表整個矩陣，根節點的每個子節點對應一個子矩陣.僅當子矩陣包含至少一個黑色單元格時，子節點的值才對應于子矩陣1，否則子節點的值將為0.將與該節點對應的值為1的子矩陣遞歸劃分，直到子矩陣中每個單元格的值為0或矩陣僅包含1個單元格.從圖5能夠發現，該k3-tree表示中有33個節點，存在2個同構子樹，用矩形框標記.

Fig. 5 k3-tree of example 1圖5 例1的k3-tree表示

例1中，時序圖的3維矩陣的k3-MDD如圖6所示，有5個節點.圖中節點內的數字僅代表該節點的索引號，不包含有其他意義.

Fig. 6 k3-MDD of example 1圖6 例1的k3-MDD表示

例1的k3-tree和k3-MDD表示表明，當將k3-tree轉換為k3-MDD時，同構子樹被合并，這樣節點數量大大減少.例1中k3-tree緊湊表示中節點數為33，而k3-MDD緊湊表示中節點數為5.

例2.max(|V|,|T|)不等于k的若干次冪.

當時序圖中頂點數量和最大時間點兩者中的最大值不等于k的若干次冪時，可以通過補全矩陣(新增的元素全都標記為0)來滿足例1中的條件.圖7所示時序圖的3維矩陣是5×5×5的，可以通過添加0數據，使原始3維矩陣維數能夠整除k3.添加0數據后的結果如圖8所示，其中灰色區域表示添加的0數據，黑色單元格表示在時間點t頂點u與頂點v的連接.

Fig. 7 Temporal graph of example 2圖7 例2的時序圖

Fig. 8 Three-dimensional matrix of example 2圖8 例2的3維矩陣

例2中時序圖的k3-tree如圖9所示.根據k3-tree的原理，將0數據添加到鄰接矩陣，圖9中的k3-tree還存在同構子樹，這些子樹用框標記，相同線型的框為同構子樹.在將例2中的時序圖的k3-tree轉換為k3-MDD之后，節點的數量從65個減少到8個，如圖10所示.

Fig. 9 k3-tree of example 2圖9 例2的k3-tree表示

Fig. 10 k3-MDD of example 2圖10 例2的k3-MDD表示

3 時序圖的kd-MDD構建過程

Fig. 11 Codes of vertexes and time points in temporal graph圖11 時序圖中的頂點和時間點編碼

根據董榮勝等人在文獻[12]中給出的圖的k2-MDD相關構建算法，給出時序圖的kd-MDD構建過程，主要包括3個步驟：對時序圖的頂點和時間點編碼、對時序圖的邊編碼以及根據邊編碼集合構建kd-MDD.為了更清晰地展示這些過程，以流程圖的形式給出相關算法.

3.1 對時序圖的頂點和時間點進行編碼

構建時序圖的kd-MDD時，首先對頂點進行n位的二進制編碼，其中n=logkmax(|V|,|T|)，max(|V|,|T|)是max(V,T)取2個集合基數中的最大值.將max(|V|,|T|)遞歸地進行k等分方式對編號為v的頂點和值為t的時間點編碼.當k=2時，在頂點和時間點的n位編碼中每一位都是2種狀態之一(1或0).對時序圖的頂點和時間點的編碼過程如圖12所示.根據該編碼規則對圖3中的頂點和時間點進行編碼后如圖11所示:

Fig. 12 Coding for vertexes and time points in temporal graph圖12 對時序圖的頂點和時間點進行編碼

3.2 對時序圖的邊進行編碼

在時序圖中，在時間點t，頂點u到頂點v的邊可以用特征函數E(u,v,t)來描述述.當k=2時，設U=(u1,u2,…,un)，V=(v1,v2,…,vn)，T=(t1,t2,…,tn)是圖中頂點和時間點的編碼向量，在時間點t，頂點u到頂點v的邊的編碼可以表示為

eCode:{0,1}n×{0,1}n×{0,1}n→ {1,2,3,4,5,6,7,8}n.

即2個頂點和1個時間點的編碼中每一位上的2種狀態能夠組合出8種不同的狀態.因此，時序圖中邊的編碼長度仍然還是n位，每一位對應于8種狀態(1,2,3,4,5,6,7,8)之一.邊編碼過程如圖13所示.根據該編碼規則以及圖11的頂點編碼，對圖3所示時序圖的邊進行編碼后如圖14所示.

Fig. 13 Coding for edges in temporal graph圖13 對時序圖的邊進行編碼

Fig. 14 Codes of edges in temporal graph圖14 時序圖的邊編碼

3.3 根據邊的編碼集合構建kd-MDD

根據kd-MDD的定義，可以構建與邊編碼相對應的時序圖的kd-MDD.如果n個變量的值全部在邊集中，則終端節點為1;否則，終端節點為0.例如，根據圖13的邊編碼過程，可以構建對應的kd-MDD結構.在構建kd-MDD時，可以借助愛荷華州立大學在Linux平臺下開發的MEDDLY(multi-terminal and edge-valued decision diagram library)函數庫，該函數庫為構建和操作kd-MDD提供了豐富功能函數.其中，可以用establishRange()函數生成構建kd-MDD時所需的變量個數以及每個變量的定義域；用establishVerge()函數根據給定變量序的1組變量的值生成1個kd-MDD；用apply()函數以及UNION運算將2個kd-MDD進行合并.借助MEDDLY庫，我們可以根據邊編碼生成時序圖的kd-MDD.圖15給出了構建kd-MDD的過程.

Fig. 15 Constructing kd-MDD圖15 構建kd-MDD

4 基于kd-MDD的時序圖的操作

構建時序圖的kd-MDD之后，可以基于kd-MDD進行以下時序圖操作.

4.1 查詢邊在時間點t的狀態

根據邊的起始頂點u、終止頂點v以及對應的時間點t的值得到對應的邊編號E(u,v,t)，在時序圖的kd-MDD中檢測E(u,v,t)的函數值，如果得到的值為T，則可判定該邊在時間點t存在，反之則該邊在時間點t不存在.使用MEDDLY庫中提供的INTERSECTION運算求2個kd-MDD的交，可以實現邊的狀態檢測.因此，將原圖的kd-MDD與要查詢的邊生成的kd-MDD進行INTERSECTION運算，查看運算結果是否為空即可，如果結果非空則邊E(u,v,t)在時間點t是存在的.查詢邊在時間點t的狀態的過程如圖16所示:

Fig. 16 The state of edge at time t圖16 時間點t時邊的狀態

4.2 查詢邊在時間點t之后的下一個激活時間點

為了檢查邊是否處于激活狀態，將需要查詢的邊的起始頂點、終止頂點賦值為u，v，時序圖中時間點t之后的時間點依次賦值給t0，檢測E(u,v,t0)的函數值.若返回的函數值為T，則該邊的下一個激活時間點為t0，反之則不是.

4.3 查詢2個頂點之間的連接狀態

首先將2個頂點的值賦值給u，v，然后將時間間隔內的時間點分別賦值給t，把2個節點之間的連接在某時間點為激活狀態時看作1條邊.將這些邊看作一個獨立的時序圖，并為其建立一個kd-MDD.通過將新生成的kd-MDD與原kd-MDD進行邏輯INTERSECTION運算，從而判斷給定2個節點之間的連接在時間間隔內是否一直處于激活狀態.

高校教師應積極參與校級、省級或全國范圍內的各種教學競賽，如課件制作競賽，微課教學競賽，“翻轉課堂”教學競賽等。無論哪一種形式的教學競賽，對參賽教師都有一定的要求，都需參賽教師進行認真的準備。另外，參賽教師可通過賽事進行交流、借鑒和學習，教學水平和信息素養能力也會因此而得到一定的提高。

4.4 查詢在時間點t頂點的直接鄰居和反向鄰居

在時間點t檢索頂點的直接鄰居等效于找到所有在時間點t從該頂點開始并終止于另一個頂點的活動邊.首先將時間點賦值為t，將要進行直接鄰居查詢的頂點賦值為u，時序圖中的其他所有頂點依次賦值為v，檢測E(u,v,t)的函數值.若返回的函數值為T，則該頂點v為u在時間點t的直接鄰居，反之則不是.通過統計直接鄰居的個數可以得到在時間點t頂點u的出度.

在時間點t查詢頂點的反向鄰居的方法與在時間點t檢索頂點的直接鄰居的方法類似.區別在于將查詢的頂點賦值為v，時序圖中其他所有頂點依次賦值為u.

4.5 添加邊和刪除邊

假設向時序圖添加一條邊E(u,v,t).根據起始頂點u、終止頂點v和時間點t的代碼獲得邊編碼.根據邊E(u,v,t)的編碼生成邊E(u,v,t)的kd-MDD.通過在邊E(u,v,t)的kd-MDD和原始時序圖的kd-MDD之間執行UNION運算，可以生成增加了該邊的新時序圖的kd-MDD.

根據要刪除邊的起始頂點u、終止頂點v和時間點t的編碼獲得要刪除邊E(u,v,t)的編碼.根據邊E(u,v,t)的編碼生成邊E(u,v,t)的kd-MDD.通過在原始時序圖的kd-MDD和邊E(u,v,t)的kd-MDD之間執行DIFFERENCE運算，可以生成刪除該邊后的新時序圖的kd-MDD.DIFFERENCE運算是求2個MDD的差，DIFFERENCE(A,B)={x|x∈A∧x?B}.

5 算法復雜度分析

在構建時序圖的kd-MDD時，是基于1組給定順序的變量的取值組合，變量個數與邊的二進制編碼長度相同.用n位二進制數對頂點進行編碼，其中n=logkmax(|V|,|T|)，即遞歸地對max(|V|,|T|)進行k等分，實現編號為v的頂點和值為t的時間點的編碼.對時序圖中單個頂點或者時間點的編碼時間復雜度為O(logkmax(|V|,|T|))；在時序圖中，在時間點t頂點u到v的邊可以用特征函數E(u,v,t)來描述.當k=2時，2個頂點和1個時間點的編碼中每一位上的2種狀態能夠組合出8種不同的狀態.因此，時序圖中邊的編碼長度仍然是n位，每一位對應于8種狀態之一.對時序圖中的每條邊進行編碼的時間復雜度也是O(logkmax(|V|,|T|))，因此對時序圖中所有邊進行編碼的時間復雜度為O(|E|logkmax(|V|,|T|)).

基于頂點或者時間點以及邊編碼進行構建kd-MDD時涉及到MDD的構建，其算法復雜度在文獻[14]中已經進行了分析，這里不再贅述.

在基于kd-MDD的時序圖的基本操作中，由于kd-MDD結構的高度為n=logkmax(|V|,|T|)，因此有關時序圖中邊操作的時間復雜度為O(|E|logkmax(|V|,|T|))，由此可知有關頂點的直接鄰居、反向鄰居的查詢操作的時間復雜度為O(max(|V|,|T|)logkmax(|V|,|T|)).

kd-MDD可以看做是k2-MDD在三維及更高維度上的擴展，從上述表示方法及算法分析可以看出，kd-MDD結構的寬度相比k2-MDD隨著維度的增大成指數級增長，但是其高度并沒有變化，基于MDD的特性，kd-MDD在空間復雜度和時間復雜度方面與k2-MDD相當.

6 實驗與分析

本文利用MEDDLY庫，采用C++語言實現時序圖的kd-MDD構建和相關操作.實驗用機器配置的軟件平臺為Ubuntu14.04 LTS 64位操作系統(內核Linux 3.19.0-61-generic)；硬件平臺為Intel?CoreTMi5-4690 CPU@3.50 GHz處理器，24 GB內存.測試數據采用公開的真實數據集，實驗結果具有更好的代表性.

6.1 實驗結果

在真實的時序圖數據集上進行了實驗.這些數據均來自于KONECT(the Koblenz network collection)[16]，KONECT是由科布倫茨-蘭道大學網絡科學與技術研究所為研究網絡科學而建立的大型網絡數據集項目.表2給出了這些時序圖的主要特征：名稱、類型、頂點數、邊數、頂點數與邊數的比值以及這些數據集在網站上的文件名.

Out-enron是一個電子郵件網絡數據集，該數據包含Enron公司員工及員工之間發送的1 148 072封電子郵件組成，網絡中的節點是個體員工，網絡中的邊是2個員工之間的電子郵件；Flickr-growth和YouTube-u-growth是2個社交網絡數據集，這2個數據集包含社交網絡的所有用戶以及用戶之間的朋友關系.

Enwikibooks和Enwikinews是英文維基百科的雙向編輯網絡，這2個網絡包含英文版的Wikipedia用戶和頁面，用戶和頁面之間通過編輯事件建立連接.Wikipedia-discussions是一個德國維基百科的討論主題的數據集，用戶之間通過回復建立連接，網絡的節點代表德文版本的Wikipedia用戶.若數據類型為3維，數據每一列的含義分別是：起始頂點編號、終止頂點編號、邊的時間戳.若數據類型為4維，數據每一列的含義分別是：起始頂點編號、終止頂點編號、邊的權重、邊的時間戳.

社交網絡中同一社區內的用戶之間的鏈接比較多，不同社區中的用戶之間的鏈接相對較少，這使此類網絡具有2個特征：

1) 本地性.大多數連接都是社區內的.

2) 相似性.同一個社區中的用戶的好友集合也是相似的.

針對這些真實數據集的特征，本文提出的kd-MDD存儲結構可以充分利用決策圖合并同構子樹的優勢，從而大大減少存儲節點的數量.分別使用kd-tree，ckd-tree，bckd-tree，kd-MDD表示這些數據集，表3給出了這4種方法應用于這些數據集的實驗結果，表3中的數據為這4種存儲結構的節點數.

Table 2 Description of 6 Datasets for Testing表2 用于測試的6個數據集的描述

Table 3 Experimental Results表3 實驗結果

6.2 實驗分析

表3中的實驗結果表明，對于6個測試數據集，kd-MDD結構中的節點數僅為kd-tree的1.58%～4.65%，為ckd-tree的11.13%～20.39%，為bckd-tree的23.27%～41.95%.從實驗結果可以看出，使用kd-MDD結構存儲時序圖能大大減少節點數量，實現更好的壓縮效果.分析實驗結果可知，真實的時序圖數據具有較強的稀疏性，同時用戶的活躍時間也是相當集中的，因此在使用kd-tree表示時序圖時，內部會存在大量的同構子樹中，而使用kd-MDD表示時序圖時，由于合并了同構子樹和消除了大量的冗余節點，使得結構更加緊湊，節點數大大減少，從而節省了存儲空間.

在查詢時間方面，因為在相同規模的時序圖數據集下，kd-MDD，kd-tree，ckd-tree，bckd-tree具有相同的高度，因此kd-MDD中邊查詢的時間復雜度與kd-tree相同，查詢時間基本相同.通過對真實數據集進行實驗驗證也確是如此.因此，本文未給出kd-MDD與kd-tree在查詢時間方面的數據對比.

7 總 結

本文設計并實現了一種更加緊湊表示時序圖的方法——kd-MDD，該方法通過將時序圖相對應的多維矩陣等分為kd個部分子矩陣，然后將每個部分轉換為多值布爾函數.利用決策圖的性質，合并了大量的同構子樹，獲得更加緊湊的結構.在kd-MDD緊湊表示時序圖的基礎上，繼續給出了查詢邊的狀態、查詢邊的激活時間點、查詢頂點的直接鄰居和反向鄰居、添加邊和刪除邊等基本操作的MDD方法，基于這些操作，可以進行時序圖的搜索、最短路、網絡流等復雜操作.在真實的數據集上進行了實驗，結果表明，kd-MDD中的節點數遠遠小于kd-tree，ckd-tree，bckd-tree中的節點數，實現了時序圖的高效緊湊表示.時序圖的kd-MDD表示，既具有kd-tree表示的緊湊性，又能實現符號決策圖表示下圖模式的高效操作，實現了緊湊表示和高效計算的統一.

作者貢獻聲明：李鳳英負責本文研究方案和實驗的主要設計與構建，以及論文主體的寫作;申會強參與實驗執行和論文的修改;董榮勝參與研究方案設計、實驗設計、數據分析和論文修改.