基于kd-MDD的時(shí)序圖緊湊表示

李鳳英 申會(huì)強(qiáng) 董榮勝

(廣西可信軟件重點(diǎn)實(shí)驗(yàn)室(桂林電子科技大學(xué)) 廣西桂林 541004)

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

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

1) 研究了MDD與時(shí)序圖之間的關(guān)系，設(shè)計(jì)了一種更加緊湊的時(shí)序圖表示方法——kd-MDD.在kd-MDD的構(gòu)建過程中隱式地合并了kd-tree中的同構(gòu)子樹，消除冗余節(jié)點(diǎn)，使得多維圖數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)更加緊湊.

2) 實(shí)現(xiàn)了時(shí)序圖的動(dòng)態(tài)管理.研究時(shí)序圖的查詢及編輯操作與MDD邏輯運(yùn)算之間的關(guān)系，給出了kd-MDD表示下時(shí)序圖的增加/刪除邊、增加/刪除頂點(diǎn)等編輯操作的一系列過程，解決了kd-tree不適用于表示動(dòng)態(tài)圖的問題.

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

1 相關(guān)工作

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

2 時(shí)序圖的kd-MDD表示

k2-tree是一棵用于表示圖的鄰接矩陣的非平衡k2叉樹[9]，是一種能夠有效壓縮和表示圖的鄰接矩陣的方法.在k2-tree結(jié)構(gòu)中，樹的根節(jié)點(diǎn)用于表示整個(gè)鄰接矩陣，內(nèi)部節(jié)點(diǎn)的“1”表示與葉子節(jié)點(diǎn)所在層數(shù)對(duì)應(yīng)的鄰接子矩陣，且該鄰接子矩陣中最少有一個(gè)“1”元素，每個(gè)內(nèi)部節(jié)點(diǎn)都有k2個(gè)子節(jié)點(diǎn).樹中的葉子節(jié)點(diǎn)可以是0也可以是1，當(dāng)葉子節(jié)點(diǎn)為0時(shí)，表示該葉子節(jié)點(diǎn)所在層對(duì)應(yīng)的鄰居矩陣所有單元格都為0或者該葉子節(jié)點(diǎn)對(duì)應(yīng)一個(gè)單元格且元素值為0；當(dāng)葉子節(jié)點(diǎn)為1時(shí)，表示該葉子節(jié)點(diǎn)對(duì)應(yīng)一個(gè)單元格且元素值為1.

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

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

設(shè)F是關(guān)于n個(gè)變量x1,x2,…,xn的多值函數(shù)，可以表示為

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

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

為了表示和操縱多值離散函數(shù)，文獻(xiàn)[14]提出了基于香農(nóng)分解定理的MDD.MDD是具有多個(gè)分支的有向無環(huán)樹結(jié)構(gòu)[15].如果F表示樹結(jié)構(gòu)中每一層的變量集X={x1,x2,…,xn}上的多值表達(dá)式，則可以將標(biāo)記為xi的非終端節(jié)點(diǎn)的MDD形式化定義為

其中xi∈X，MDD有h=|R|個(gè)終端節(jié)點(diǎn)，分別對(duì)應(yīng)于常數(shù)r0,r1,…,rh-1.每個(gè)非終端節(jié)點(diǎn)表示一個(gè)具有l(wèi)i=|Li|個(gè)分支的變量xi，每個(gè)分支對(duì)應(yīng)于一個(gè)多值表達(dá)式Fxi=j.因此，MDD的每個(gè)非終端節(jié)點(diǎn)都有一個(gè)具體的布爾表達(dá)式.

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

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

按照kd-tree的思想對(duì)多維圖的多維鄰接矩陣遞歸地進(jìn)行kd等分，根據(jù)劃分結(jié)果構(gòu)建出能表示該多維圖的MDD結(jié)構(gòu)，這樣的MDD稱為kd-MDD.

kd-MDD描述的是一個(gè)n元的離散多值函數(shù)關(guān)系：

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

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

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

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

kd-MDD結(jié)構(gòu)中包含2種節(jié)點(diǎn)：內(nèi)部節(jié)點(diǎn)和終端節(jié)點(diǎn).內(nèi)部節(jié)點(diǎn)用xi表示，包含kd個(gè)指向其他節(jié)點(diǎn)的指針，這些指針與函數(shù)f對(duì)應(yīng)，形式化描述為

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

kd-MDD中一個(gè)內(nèi)部節(jié)點(diǎn)的圖形化描述如圖1所示：

Fig. 1 Graphical description of non-terminal node in kd-MDD圖1 kd-MDD中內(nèi)部節(jié)點(diǎn)的圖形化描述

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

kd-MDD是一種能夠表示多維圖的MDD，因此其具有與MDD相同的化簡(jiǎn)規(guī)則，具體有2個(gè)規(guī)則：

1) 合并規(guī)則.合并具有相同值(結(jié)構(gòu))的終端節(jié)點(diǎn)(內(nèi)部結(jié)點(diǎn)).

2) 刪除規(guī)則.刪除那些所有指針都指向同一節(jié)點(diǎn)的冗余結(jié)點(diǎn).

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

Fig. 2 Simplification rules of MDD圖2 MDD的化簡(jiǎn)規(guī)則

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

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

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

當(dāng)時(shí)序圖稀疏時(shí)，其對(duì)應(yīng)的多維矩陣中存在大量的“0”.kd-MDD利用合并規(guī)則可消除重復(fù)的“0”節(jié)點(diǎn)，僅保留一個(gè)“0”節(jié)點(diǎn)，從而得到稀疏時(shí)序圖的緊湊表示.當(dāng)時(shí)序圖稠密時(shí)，利用合并規(guī)則和刪除規(guī)則能夠消除大量重復(fù)“1”節(jié)點(diǎn)和該多維鄰接矩陣中存在的大量同構(gòu)子樹，實(shí)現(xiàn)更加緊湊的表示.因此，該方法不僅適用于稀疏時(shí)序圖，也適用于稠密時(shí)序圖.

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

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

對(duì)于圖3所示的時(shí)序圖，圓圈中的數(shù)字表示頂點(diǎn)，橫坐標(biāo)表示時(shí)間，黑色部分表示與之對(duì)應(yīng)的邊在對(duì)應(yīng)的時(shí)間點(diǎn)存在.對(duì)于圖3所示的時(shí)序圖，其3維矩陣如圖4所示,其中黑色單元格表示時(shí)間點(diǎn)t從頂點(diǎn)u到頂點(diǎn)v的邊存在，白色單元格表示該邊不存在.

Fig. 3 Temporal graph of example 1圖3 例1的時(shí)序圖

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

圖5給出了圖4所示時(shí)序圖的3維鄰接矩陣的k3-tree表示.當(dāng)使用k3-tree表示3維鄰接矩陣時(shí)，3維矩陣等分為k3個(gè)部分，并且每個(gè)子矩陣包含相同數(shù)量的單元格.樹的根節(jié)點(diǎn)代表整個(gè)矩陣，根節(jié)點(diǎn)的每個(gè)子節(jié)點(diǎn)對(duì)應(yīng)一個(gè)子矩陣.僅當(dāng)子矩陣包含至少一個(gè)黑色單元格時(shí)，子節(jié)點(diǎn)的值才對(duì)應(yīng)于子矩陣1，否則子節(jié)點(diǎn)的值將為0.將與該節(jié)點(diǎn)對(duì)應(yīng)的值為1的子矩陣遞歸劃分，直到子矩陣中每個(gè)單元格的值為0或矩陣僅包含1個(gè)單元格.從圖5能夠發(fā)現(xiàn)，該k3-tree表示中有33個(gè)節(jié)點(diǎn)，存在2個(gè)同構(gòu)子樹，用矩形框標(biāo)記.

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

例1中，時(shí)序圖的3維矩陣的k3-MDD如圖6所示，有5個(gè)節(jié)點(diǎn).圖中節(jié)點(diǎn)內(nèi)的數(shù)字僅代表該節(jié)點(diǎn)的索引號(hào)，不包含有其他意義.

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

例1的k3-tree和k3-MDD表示表明，當(dāng)將k3-tree轉(zhuǎn)換為k3-MDD時(shí)，同構(gòu)子樹被合并，這樣節(jié)點(diǎn)數(shù)量大大減少.例1中k3-tree緊湊表示中節(jié)點(diǎn)數(shù)為33，而k3-MDD緊湊表示中節(jié)點(diǎn)數(shù)為5.

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

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

Fig. 7 Temporal graph of example 2圖7 例2的時(shí)序圖

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

例2中時(shí)序圖的k3-tree如圖9所示.根據(jù)k3-tree的原理，將0數(shù)據(jù)添加到鄰接矩陣，圖9中的k3-tree還存在同構(gòu)子樹，這些子樹用框標(biāo)記，相同線型的框?yàn)橥瑯?gòu)子樹.在將例2中的時(shí)序圖的k3-tree轉(zhuǎn)換為k3-MDD之后，節(jié)點(diǎn)的數(shù)量從65個(gè)減少到8個(gè)，如圖10所示.

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

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

3 時(shí)序圖的kd-MDD構(gòu)建過程

Fig. 11 Codes of vertexes and time points in temporal graph圖11 時(shí)序圖中的頂點(diǎn)和時(shí)間點(diǎn)編碼

根據(jù)董榮勝等人在文獻(xiàn)[12]中給出的圖的k2-MDD相關(guān)構(gòu)建算法，給出時(shí)序圖的kd-MDD構(gòu)建過程，主要包括3個(gè)步驟：對(duì)時(shí)序圖的頂點(diǎn)和時(shí)間點(diǎn)編碼、對(duì)時(shí)序圖的邊編碼以及根據(jù)邊編碼集合構(gòu)建kd-MDD.為了更清晰地展示這些過程，以流程圖的形式給出相關(guān)算法.

3.1 對(duì)時(shí)序圖的頂點(diǎn)和時(shí)間點(diǎn)進(jìn)行編碼

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

Fig. 12 Coding for vertexes and time points in temporal graph圖12 對(duì)時(shí)序圖的頂點(diǎn)和時(shí)間點(diǎn)進(jìn)行編碼

3.2 對(duì)時(shí)序圖的邊進(jìn)行編碼

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

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

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

Fig. 13 Coding for edges in temporal graph圖13 對(duì)時(shí)序圖的邊進(jìn)行編碼

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

3.3 根據(jù)邊的編碼集合構(gòu)建kd-MDD

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

Fig. 15 Constructing kd-MDD圖15 構(gòu)建kd-MDD

4 基于kd-MDD的時(shí)序圖的操作

構(gòu)建時(shí)序圖的kd-MDD之后，可以基于kd-MDD進(jìn)行以下時(shí)序圖操作.

4.1 查詢邊在時(shí)間點(diǎn)t的狀態(tài)

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

Fig. 16 The state of edge at time t圖16 時(shí)間點(diǎn)t時(shí)邊的狀態(tài)

4.2 查詢邊在時(shí)間點(diǎn)t之后的下一個(gè)激活時(shí)間點(diǎn)

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

4.3 查詢2個(gè)頂點(diǎn)之間的連接狀態(tài)

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

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

4.4 查詢?cè)跁r(shí)間點(diǎn)t頂點(diǎn)的直接鄰居和反向鄰居

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

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

4.5 添加邊和刪除邊

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

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

5 算法復(fù)雜度分析

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

基于頂點(diǎn)或者時(shí)間點(diǎn)以及邊編碼進(jìn)行構(gòu)建kd-MDD時(shí)涉及到MDD的構(gòu)建，其算法復(fù)雜度在文獻(xiàn)[14]中已經(jīng)進(jìn)行了分析，這里不再贅述.

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

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

6 實(shí)驗(yàn)與分析

本文利用MEDDLY庫，采用C++語言實(shí)現(xiàn)時(shí)序圖的kd-MDD構(gòu)建和相關(guān)操作.實(shí)驗(yàn)用機(jī)器配置的軟件平臺(tái)為Ubuntu14.04 LTS 64位操作系統(tǒng)(內(nèi)核Linux 3.19.0-61-generic)；硬件平臺(tái)為Intel?CoreTMi5-4690 CPU@3.50 GHz處理器，24 GB內(nèi)存.測(cè)試數(shù)據(jù)采用公開的真實(shí)數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果具有更好的代表性.

6.1 實(shí)驗(yàn)結(jié)果

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

Out-enron是一個(gè)電子郵件網(wǎng)絡(luò)數(shù)據(jù)集，該數(shù)據(jù)包含Enron公司員工及員工之間發(fā)送的1 148 072封電子郵件組成，網(wǎng)絡(luò)中的節(jié)點(diǎn)是個(gè)體員工，網(wǎng)絡(luò)中的邊是2個(gè)員工之間的電子郵件；Flickr-growth和YouTube-u-growth是2個(gè)社交網(wǎng)絡(luò)數(shù)據(jù)集，這2個(gè)數(shù)據(jù)集包含社交網(wǎng)絡(luò)的所有用戶以及用戶之間的朋友關(guān)系.

Enwikibooks和Enwikinews是英文維基百科的雙向編輯網(wǎng)絡(luò)，這2個(gè)網(wǎng)絡(luò)包含英文版的Wikipedia用戶和頁面，用戶和頁面之間通過編輯事件建立連接.Wikipedia-discussions是一個(gè)德國維基百科的討論主題的數(shù)據(jù)集，用戶之間通過回復(fù)建立連接，網(wǎng)絡(luò)的節(jié)點(diǎn)代表德文版本的Wikipedia用戶.若數(shù)據(jù)類型為3維，數(shù)據(jù)每一列的含義分別是：起始頂點(diǎn)編號(hào)、終止頂點(diǎn)編號(hào)、邊的時(shí)間戳.若數(shù)據(jù)類型為4維，數(shù)據(jù)每一列的含義分別是：起始頂點(diǎn)編號(hào)、終止頂點(diǎn)編號(hào)、邊的權(quán)重、邊的時(shí)間戳.

社交網(wǎng)絡(luò)中同一社區(qū)內(nèi)的用戶之間的鏈接比較多，不同社區(qū)中的用戶之間的鏈接相對(duì)較少，這使此類網(wǎng)絡(luò)具有2個(gè)特征：

1) 本地性.大多數(shù)連接都是社區(qū)內(nèi)的.

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

針對(duì)這些真實(shí)數(shù)據(jù)集的特征，本文提出的kd-MDD存儲(chǔ)結(jié)構(gòu)可以充分利用決策圖合并同構(gòu)子樹的優(yōu)勢(shì)，從而大大減少存儲(chǔ)節(jié)點(diǎn)的數(shù)量.分別使用kd-tree，ckd-tree，bckd-tree，kd-MDD表示這些數(shù)據(jù)集，表3給出了這4種方法應(yīng)用于這些數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果，表3中的數(shù)據(jù)為這4種存儲(chǔ)結(jié)構(gòu)的節(jié)點(diǎn)數(shù).

Table 2 Description of 6 Datasets for Testing表2 用于測(cè)試的6個(gè)數(shù)據(jù)集的描述

Table 3 Experimental Results表3 實(shí)驗(yàn)結(jié)果

6.2 實(shí)驗(yàn)分析

表3中的實(shí)驗(yàn)結(jié)果表明，對(duì)于6個(gè)測(cè)試數(shù)據(jù)集，kd-MDD結(jié)構(gòu)中的節(jié)點(diǎn)數(shù)僅為kd-tree的1.58%～4.65%，為ckd-tree的11.13%～20.39%，為bckd-tree的23.27%～41.95%.從實(shí)驗(yàn)結(jié)果可以看出，使用kd-MDD結(jié)構(gòu)存儲(chǔ)時(shí)序圖能大大減少節(jié)點(diǎn)數(shù)量，實(shí)現(xiàn)更好的壓縮效果.分析實(shí)驗(yàn)結(jié)果可知，真實(shí)的時(shí)序圖數(shù)據(jù)具有較強(qiáng)的稀疏性，同時(shí)用戶的活躍時(shí)間也是相當(dāng)集中的，因此在使用kd-tree表示時(shí)序圖時(shí)，內(nèi)部會(huì)存在大量的同構(gòu)子樹中，而使用kd-MDD表示時(shí)序圖時(shí)，由于合并了同構(gòu)子樹和消除了大量的冗余節(jié)點(diǎn)，使得結(jié)構(gòu)更加緊湊，節(jié)點(diǎn)數(shù)大大減少，從而節(jié)省了存儲(chǔ)空間.

在查詢時(shí)間方面，因?yàn)樵谙嗤?guī)模的時(shí)序圖數(shù)據(jù)集下，kd-MDD，kd-tree，ckd-tree，bckd-tree具有相同的高度，因此kd-MDD中邊查詢的時(shí)間復(fù)雜度與kd-tree相同，查詢時(shí)間基本相同.通過對(duì)真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證也確是如此.因此，本文未給出kd-MDD與kd-tree在查詢時(shí)間方面的數(shù)據(jù)對(duì)比.

7 總 結(jié)

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

作者貢獻(xiàn)聲明：李鳳英負(fù)責(zé)本文研究方案和實(shí)驗(yàn)的主要設(shè)計(jì)與構(gòu)建，以及論文主體的寫作;申會(huì)強(qiáng)參與實(shí)驗(yàn)執(zhí)行和論文的修改;董榮勝參與研究方案設(shè)計(jì)、實(shí)驗(yàn)設(shè)計(jì)、數(shù)據(jù)分析和論文修改.