大規(guī)模圖數(shù)據(jù)的k2-MDD表示方法與操作研究

董榮勝 張新凱 劉華東 古天龍

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

?

大規(guī)模圖數(shù)據(jù)的k2-MDD表示方法與操作研究

董榮勝 張新凱 劉華東 古天龍

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

對(duì)包含億萬個(gè)頂點(diǎn)和邊的圖數(shù)據(jù)進(jìn)行高效、緊湊的表示和操作是大規(guī)模圖數(shù)據(jù)分析處理的基礎(chǔ).針對(duì)該問題提出了基于決策圖的大規(guī)模圖數(shù)據(jù)的一種表示方法——k2-MDD，給出了k2-MDD的構(gòu)造過程以及圖的邊查詢、外(內(nèi))鄰查詢、出(入)度查詢、添加(刪除)邊等基本操作.該表示方法在k2樹的基礎(chǔ)上進(jìn)行優(yōu)化與改進(jìn)，對(duì)圖的鄰接矩陣進(jìn)行k2劃分后，采用多值決策圖進(jìn)行存儲(chǔ)，從而達(dá)到存儲(chǔ)結(jié)構(gòu)更為緊湊的目的.通過對(duì)來自米蘭大學(xué)LAW實(shí)驗(yàn)室的一系列真實(shí)網(wǎng)頁圖和社交網(wǎng)絡(luò)圖數(shù)據(jù)的實(shí)驗(yàn)結(jié)果可以看出，k2-MDD結(jié)構(gòu)在節(jié)點(diǎn)數(shù)上僅為k2樹的2.59%～4.51%，達(dá)到了預(yù)期效果.通過對(duì)隨機(jī)圖的實(shí)驗(yàn)結(jié)果可以看出，k2-MDD結(jié)構(gòu)不僅適用于稀疏圖，同樣也適用于稠密圖.圖數(shù)據(jù)的k2-MDD表示，既具有k2樹表示的緊湊型和查詢的高效性，又能實(shí)現(xiàn)符號(hào)決策圖表示下圖模式的高效操作，從而實(shí)現(xiàn)了描述和計(jì)算能力的統(tǒng)一.

圖數(shù)據(jù)；存儲(chǔ)優(yōu)化；k2-MDD；k2樹；決策圖

隨著移動(dòng)互聯(lián)網(wǎng)、物聯(lián)網(wǎng)等技術(shù)的發(fā)展，眾多新應(yīng)用以前所未有的方式和速度產(chǎn)生并積累著大量數(shù)據(jù).在眾多類型的大數(shù)據(jù)中，圖數(shù)據(jù)作為一種有效描述大數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，扮演著越來越重要的角色[1-2].由于圖數(shù)據(jù)的規(guī)模日益龐大，如何對(duì)圖數(shù)據(jù)進(jìn)行高效的存儲(chǔ)以及如何對(duì)圖數(shù)據(jù)進(jìn)行高效的操作是當(dāng)前面臨的兩大挑戰(zhàn).以社交網(wǎng)絡(luò)為例，根據(jù)GlobalWebIndex統(tǒng)計(jì)，F(xiàn)acebook用戶量已經(jīng)超過11億，平均每個(gè)人的好友超過100位，使用鄰接表來存儲(chǔ)所有用戶的關(guān)系信息，需要接近1TB的存儲(chǔ)空間[3]；以互聯(lián)網(wǎng)為例，根據(jù)中國互聯(lián)網(wǎng)絡(luò)信息中心(CNNIC)發(fā)布的《第37次中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》[4]，截至2015年12月中國網(wǎng)頁數(shù)量為2 123億個(gè)，超鏈接數(shù)量據(jù)估計(jì)超過1013，使用鄰接表來存儲(chǔ)網(wǎng)頁直接的鏈接關(guān)系信息需要超過16 TB的存儲(chǔ)空間.同時(shí)隨著用戶量和信息量的快速增長，問題也只會(huì)變得越來越嚴(yán)峻.

為了對(duì)圖數(shù)據(jù)進(jìn)行緊湊表示，在傳統(tǒng)的鄰接矩陣表示法的基礎(chǔ)上，Brisaboa等人[5]于2009年提出了基于k2樹(k2-tree)的方法，樹中的每一層對(duì)應(yīng)于鄰接矩陣或分塊子矩陣的分塊子矩陣，節(jié)點(diǎn)對(duì)應(yīng)于鄰接矩陣的分塊子矩陣，生成的k2樹使用2個(gè)位向量T和L來存儲(chǔ)，該方法不僅能夠緊湊表示鄰接矩陣，而且能實(shí)現(xiàn)鄰接節(jié)點(diǎn)的正向或逆向高效查詢操作[6].施佺等人[7-8]給出了k2樹表示方法的2種優(yōu)化技術(shù)：啟發(fā)式深度優(yōu)先節(jié)點(diǎn)重排序和自適應(yīng)修正k，使得所表示的結(jié)構(gòu)更為緊湊，節(jié)點(diǎn)得到明顯的減少.

但是，不論是k2樹還是施佺等人優(yōu)化過的k2樹，在對(duì)大規(guī)模圖數(shù)據(jù)表示時(shí)仍具有一定的局限性，具體表現(xiàn)在3個(gè)方面：

1) 當(dāng)圖的規(guī)模變大時(shí)，圖內(nèi)部本身就會(huì)存在大量的同構(gòu)子圖.同樣地，當(dāng)按照k2樹的思想把鄰接矩陣進(jìn)行劃分后，也存在大量的相同的子矩陣.這就造成了k2樹內(nèi)也存在大量的同構(gòu)子樹.

2)k2樹僅對(duì)稀疏圖有效，當(dāng)圖變的稠密時(shí)，由于鄰接矩陣內(nèi)可被壓縮的0節(jié)點(diǎn)變少，因此k2樹緊湊性也會(huì)變低.

3)k2樹未涉及動(dòng)態(tài)圖(需要添加或刪除頂點(diǎn)、邊以及子圖等的圖)的表示與操作[5].

因此，k2樹對(duì)上述圖的結(jié)構(gòu)特性尚缺乏必要的考慮，其在緊湊性上仍有較大的改善空間.針對(duì)k2樹目前存在的問題，有必要對(duì)其進(jìn)行進(jìn)一步的優(yōu)化與改進(jìn)，以得到一種更為緊湊并且適用面更廣的圖數(shù)據(jù)的表示方法.為此，本文提出一種基于決策圖的大規(guī)模圖數(shù)據(jù)的表示方法——k2-MDD，該表示方法采用k2樹的思想對(duì)鄰接矩陣進(jìn)行劃分，然后使用多值決策圖進(jìn)行存儲(chǔ)，使k2樹中大量的同構(gòu)子樹所造成的冗余節(jié)點(diǎn)得到合并，從而達(dá)到存儲(chǔ)結(jié)構(gòu)更為緊湊的目的.該k2-MDD的優(yōu)點(diǎn)主要有4點(diǎn)：

1) 由于采用決策圖結(jié)構(gòu)來存儲(chǔ)圖數(shù)據(jù)，因此對(duì)于劃分鄰接矩陣時(shí)產(chǎn)生相同的子矩陣，即k2樹中的同構(gòu)子樹就自然地被合并了，最終生成的k2-MDD結(jié)構(gòu)將比k2樹緊湊得多.

2)k2-MDD與k2樹所不同的是，它不論是0值還是1值，只要是同構(gòu)的，都將被合并掉.因此，在表示稠密圖時(shí)，k2-MDD節(jié)點(diǎn)數(shù)反而會(huì)變少，結(jié)構(gòu)變得更為緊湊.

3) 當(dāng)使用決策圖來存儲(chǔ)圖數(shù)據(jù)后，圖的相關(guān)基本操作就可以轉(zhuǎn)化為符號(hào)決策圖的邏輯操作，這就為動(dòng)態(tài)圖數(shù)據(jù)的高效操作提供了可能性.另外這也使得基于k2-MDD要比基于k2樹的圖的查詢操作更為簡潔.

4) 由于k2-MDD是基于決策圖的結(jié)構(gòu)，根據(jù)其本身結(jié)構(gòu)的特性，該結(jié)構(gòu)將更有利于子圖查詢、圖同構(gòu)、圖子圖匹配以及多圖匹配等方向的研究.

本文以有向無權(quán)圖為例，對(duì)k2-MDD的表示與操作進(jìn)行討論.本文提出的結(jié)構(gòu)也可以拓展用于無向圖以及加權(quán)圖的存儲(chǔ)與表示.下面給出k2-MDD的表示形式、定義、性質(zhì)、構(gòu)造過程以及對(duì)于有向圖的基本操作等.

1 有向圖的k2-MDD表示形式

首先給出k2-MDD的定義：

定義1.k2-MDD：圖的鄰接矩陣可以用一個(gè)將原始矩陣進(jìn)行遞歸的k2等分后構(gòu)造的多值決策圖(multi-valued decision diagram, MDD)[9]結(jié)構(gòu)來表示，這樣的MDD稱之為k2-MDD.

k2-MDD描述了一個(gè)帶有n個(gè)變量的離散多值函數(shù)，f:D1×D2×…×Di×…×Dn→S，其中：

2)Di代表遞歸到第i層時(shí)對(duì)(子)矩陣的劃分.Di={1,2,…,k2}為所有變量的有限值域，與每次對(duì)(子)矩陣劃分得到的k2個(gè)子矩陣一一對(duì)應(yīng)；S為多值函數(shù)f的有限值域，即k2-MDD終端節(jié)點(diǎn)的取值集合，其可能為布爾值(對(duì)應(yīng)無權(quán)圖)、有限整數(shù)集合或者有限實(shí)數(shù)集合(對(duì)應(yīng)加權(quán)圖).

3)k2-MDD的節(jié)點(diǎn)包括終端節(jié)點(diǎn)和非終端節(jié)點(diǎn).

4) 非終端節(jié)點(diǎn)用xi表示，包含k2個(gè)指向其他節(jié)點(diǎn)的指針，這些指針和函數(shù)f對(duì)應(yīng)，其形式化描述為

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

(1)

k2-MDD的圖形化描述如圖1所示：

Fig. 1 Graphical description of k2-MDD.圖1 k2-MDD的圖形化描述

Fig. 2 Reduction rules.圖2 化簡規(guī)則

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

k2-MDD的化簡規(guī)則與MDD相同，可以總結(jié)為3條：

規(guī)則1. 合并相同終端節(jié)點(diǎn).同一屬性的終端節(jié)點(diǎn)只保留一個(gè)，并刪除其余相同屬性的終端節(jié)點(diǎn)，原來指向這些已刪除的終端節(jié)點(diǎn)的指針重定向到保留的終端節(jié)點(diǎn)上.

規(guī)則2. 合并相同內(nèi)部節(jié)點(diǎn).同一屬性的內(nèi)部節(jié)點(diǎn)(非終端節(jié)點(diǎn))只保留一個(gè)，并刪除其余相同屬性的內(nèi)部節(jié)點(diǎn)，原來指向這些已刪除節(jié)點(diǎn)的指針重定向到保留的內(nèi)部節(jié)點(diǎn)上.

規(guī)則3. 刪除冗余節(jié)點(diǎn).如果一個(gè)節(jié)點(diǎn)的所有指針都指向同一節(jié)點(diǎn)，那么該節(jié)點(diǎn)就是冗余節(jié)點(diǎn)，需將其刪除，并將指向該節(jié)點(diǎn)的指針指向刪除節(jié)點(diǎn)的孩子節(jié)點(diǎn).

上述3條化簡規(guī)則實(shí)例如圖2所示，其中圖2(a)表示多值函數(shù)f=xy，x的取值范圍為x∈{1,2,3}，y的取值范圍為y∈{1,2,3}，函數(shù)f的值域?yàn)榧蟵0,1,2}.

由k2-MDD的定義可以看出，圖的鄰接矩陣中任一單元均對(duì)應(yīng)于n個(gè)變量的唯一一組取值，根據(jù)這組取值可以得到唯一函數(shù)值，即終端節(jié)點(diǎn)的值，并且該值與原始矩陣中對(duì)應(yīng)單元格的元素值相等.

本文以無權(quán)圖進(jìn)行說明，因此函數(shù)f的值域取布爾值.對(duì)圖中頂點(diǎn)數(shù)量等于k的若干次冪和圖中頂點(diǎn)數(shù)量不等于k的若干次冪2種典型情況分別進(jìn)行舉例說明，其中k=2.

例1. 頂點(diǎn)數(shù)量等于k的若干次冪.

對(duì)于圖3所示的有向圖，其鄰接矩陣如圖4所示,k2樹如圖5所示.顯然，圖5中存在同構(gòu)子樹，如圖6所示.

Fig. 3 Graph structure.圖3 圖結(jié)構(gòu)

Fig. 4 Adjacency matrix of example 1.圖4 例1的鄰接矩陣

Fig. 8 k2 tree of example 2.圖8 例2的k2樹

Fig. 5 k2 tree of example 1.圖5 例1的k2樹

Fig. 6 Isomorphic subtrees in k2 tree of example 1.圖6 例1的k2樹中的同構(gòu)子樹

例2. 頂點(diǎn)數(shù)量不等于k的若干次冪.

當(dāng)圖中頂點(diǎn)數(shù)量不等于k的若干次冪時(shí)，可以通過增加鄰接矩陣的行數(shù)和列數(shù)(新增的元素全都標(biāo)記為0)來滿足條件[3].如圖7中的鄰接矩陣，其原始圖中有11個(gè)頂點(diǎn)，原始矩陣是11行乘11列的矩陣，通過增加5行5列0數(shù)據(jù)來使得矩陣可以被k2等分.從k2樹原理及圖8可以知道，這樣增加全部為0的行列對(duì)最終生成的k2樹產(chǎn)生的影響非常小.顯然，圖8的k2樹也存在同構(gòu)子樹，圖9標(biāo)出了其中一部分.

Fig.7 Adjacency matrix of example 2.圖7 例2的鄰接矩陣

當(dāng)圖的規(guī)模變大時(shí)，k2樹中相同的子樹會(huì)變得越來越多，另外還有大量的0節(jié)點(diǎn).這種現(xiàn)象在小規(guī)模圖中也有體現(xiàn)，比如上述2個(gè)例子.

為了減少k2樹中的節(jié)點(diǎn)數(shù)量，可以將k2樹中的同構(gòu)子樹進(jìn)行合并.而這正好是決策圖[10]的優(yōu)勢.另外，這種合并的過程與MDD化簡過程恰好吻合.對(duì)于無權(quán)圖，使用布爾型MDD(終點(diǎn)要么是真要么是假)；對(duì)于加權(quán)圖，使用整數(shù)或者實(shí)數(shù)型MDD(終點(diǎn)是整數(shù)或者實(shí)數(shù)).本文使用無權(quán)圖進(jìn)行說明，MDD中所有變量的有限值域均為{1,2,…,k2}.

Fig. 9 Isomorphic subtrees in k2 tree of example 2.圖9 例2的k2樹中的同構(gòu)子樹

將上述2個(gè)例子的k2樹轉(zhuǎn)換為MDD后分別如圖10和圖11所示.圖10、圖11中節(jié)點(diǎn)內(nèi)的數(shù)字僅代表該節(jié)點(diǎn)的索引號(hào)，并沒有其他意義，圖10、圖11中左側(cè)的數(shù)字為圖中節(jié)點(diǎn)的層次序號(hào).

從以上2例可以看出，從k2樹轉(zhuǎn)換為MDD后同構(gòu)子樹都被合并了，節(jié)點(diǎn)數(shù)量大大減少.例1從21個(gè)節(jié)點(diǎn)減少為6個(gè)節(jié)點(diǎn)，例2從73個(gè)節(jié)點(diǎn)減少為16個(gè)節(jié)點(diǎn).

Fig. 10 The MDD of example 1.圖10 例1的MDD

Fig. 11 The MDD of example 2.圖11 例2的MDD

2 構(gòu)造k2-MDD的算法過程

構(gòu)造k2-MDD的過程分為對(duì)圖的頂點(diǎn)進(jìn)行編碼、對(duì)邊進(jìn)行編碼、根據(jù)邊的編碼來構(gòu)造k2-MDD3個(gè)步驟，具體如下：

1) 對(duì)圖的頂點(diǎn)編碼

Fig. 12 Coding vertexs and coding edges.圖12 頂點(diǎn)編碼和邊編碼

算法1. 對(duì)圖的頂點(diǎn)進(jìn)行編碼.

輸入: 要進(jìn)行編碼的頂點(diǎn)的編號(hào)nodeID；

輸出: 對(duì)應(yīng)該頂點(diǎn)的編碼數(shù)組nodeCode[].

①EncodingNode(nodeCode[],nodeID)*將編號(hào)為nodeID的頂點(diǎn)編碼并存到數(shù)組nodeCode[]中*

②codeNum←CeilingLog_2(nodeNum);*codeNum為編碼長度，nodeNum為頂點(diǎn)數(shù)量*

③low←1;

④high←Pow(2,codeNum);*取不小于nodeNum的2的若干次冪*

⑤i←1;

⑥ While (low≤high) Do*二分編碼*

⑦mid←(low+high)2;

⑧ IfnodeID≤midThen

⑨nodeCode[i]←0;

⑩high←mid-1;

2) 對(duì)圖的邊編碼

有向邊可理解為頂點(diǎn)之間的關(guān)系，頂點(diǎn)v0到頂點(diǎn)v1的邊可用特征函數(shù)E(v0,v1)來描述.當(dāng)k=2時(shí)，設(shè)X=(x1,x2,…,xn),Y=(y1,y2,…,yn)是圖中頂點(diǎn)的編碼向量，則頂點(diǎn)X到頂點(diǎn)Y邊的特征函數(shù)表示為

E(X,Y):{0,1}n×{0,1}n→{1,2,3,4}n,

即每一位上2個(gè)頂點(diǎn)的2種狀態(tài)會(huì)組合出4種狀態(tài).因此，邊的編碼長度依然是n位，每一位是4種狀態(tài)之一(1,2,3或4).邊編碼過程的偽代碼如算法2所示.根據(jù)該編碼規(guī)則對(duì)圖3所示圖的邊編碼后如圖12所示.

算法2. 對(duì)圖的邊進(jìn)行編碼.

輸入: 要進(jìn)行編碼的邊的起止頂點(diǎn)編號(hào)nodeFrom和nodeTo；

輸出: 對(duì)應(yīng)該條邊的編碼數(shù)組edgeCode[].

①EncodingEdge(edgeCode[],nodeFrom,nodeTo)*根據(jù)邊的起止頂點(diǎn)得到邊的編碼*

②EncodingNode(nodeCodeA[],nodeFrom)*對(duì)邊的起始頂點(diǎn)進(jìn)行編碼*

③EncodingNode(nodeCodeB[],nodeTo)*對(duì)邊的終止頂點(diǎn)進(jìn)行編碼*

④ Fori=1 TocodeNumDo*根據(jù)起止頂點(diǎn)的編碼來對(duì)這條邊進(jìn)行編碼*

⑤edgeCode[i]←nodeCodeA[i]×2+nodeCodeB[i]+1;

⑥ EndFor

3) 根據(jù)邊編碼的集合來構(gòu)造k2-MDD

根據(jù)k2-MDD的定義，我們可以構(gòu)造一個(gè)含有n個(gè)變量的k2-MDD，然后令這n個(gè)變量的值等于邊編碼集合里的值時(shí)，函數(shù)值為T，否則為F.這樣就得到了與有向圖G對(duì)應(yīng)的k2-MDD.例如，根據(jù)圖12中的邊編碼，可以得到圖的k2-MDD結(jié)構(gòu)如圖10所示.在構(gòu)造k2-MDD時(shí)可以借助MEDDLY(multi-terminal and edge-valued decision diagram library)函數(shù)庫[11].MEDDLY函數(shù)庫是為操控MDD提供的一個(gè)CC++開源項(xiàng)目，由愛荷華州立大學(xué)在Linux平臺(tái)下開發(fā)，其中提供了豐富的MDD構(gòu)造以及操作的函數(shù).例如：可以使用createVariablesBottomUp()函數(shù)來創(chuàng)建將要構(gòu)造MDD的變量個(gè)數(shù)以及每個(gè)變量的取值范圍；使用createEdge()函數(shù)來根據(jù)給定的一組或多組變量的值來生成一個(gè)MDD；使用apply()函數(shù)以及UNION運(yùn)算符來將2個(gè)MDD進(jìn)行合并.通過MEDDLY函數(shù)庫，根據(jù)邊編碼我們可以很方便地生成有向圖對(duì)應(yīng)的k2-MDD.構(gòu)造k2-MDD的偽代碼如算法3所示.

算法3. 構(gòu)造k2-MDD.

輸入: 圖的所有邊；

輸出: 與輸入圖對(duì)應(yīng)的k2-MDD.

①CreateK2MDD()*根據(jù)邊生成k2-MDD*

② Fori=1 TocodeNumDo*設(shè)置變量個(gè)數(shù)以及每個(gè)變量的值域*

③Bounds[i]←4;

④ EndFor

⑤createVariablesBottomUp(bounds[],codeNum);*創(chuàng)建變量*

⑥EncodingEdge(edgeCode[],nodeFrom[1],nodeTo[1]);*對(duì)第1條邊進(jìn)行編碼*

⑦createEdge(edgeCode[],1,all);*根據(jù)第1條邊的編碼生成一個(gè)初始化MDD*

⑧ Fori=2 ToedgeNumDo

⑨EncodingEdge(edgeCode[],nodeFrom[i],nodeTo[i]);*對(duì)第i條邊進(jìn)行編碼*

⑩createEdge(edgeCode[],1,rest);*根據(jù)第i條邊編碼生成MDD并存到rest*

3 基于k2-MDD的有向圖的操作

下面給出在k2-MDD存儲(chǔ)結(jié)構(gòu)下有向圖的一些基本操作.

1) 邊查詢

根據(jù)邊的起止頂點(diǎn)v1和頂點(diǎn)v2的編號(hào)得到該條邊的編號(hào)E(v1,v2)，在圖的k2-MDD中檢測E(v1,v2)的函數(shù)值.若值為T，則該邊存在，否則不存在.MEDDLY庫中提供的INTERSECTION運(yùn)算符可以幫我們完成此操作.INTERSECTION用來求2個(gè)MDD的交運(yùn)算.因此，我們只要將原圖的k2-MDD與要查詢的邊生成的k2-MDD進(jìn)行INTERSECTION運(yùn)算，查看運(yùn)算結(jié)果是否為空即可.邊查詢的偽代碼如算法4所示.

算法4. 邊查詢算法.

輸入: 要查詢的邊的起止頂點(diǎn)編號(hào)nodeFrom和nodeTo；

輸出: 該邊是否存在.

①edgeQuery(nodeFrom,nodeTo)*根據(jù)邊的起止頂點(diǎn)查詢圖中是否存在該邊*

②EncodingEdge(edgeCode[],nodeFrom,nodeTo);*對(duì)邊進(jìn)行編碼*

③createEdge(edgeCode[],1,tmp);*生成這條邊的MDD*

④apply(INTERSECTION,K2MDD,tmp,res);*進(jìn)行交運(yùn)算，結(jié)果存到res中*

⑤ Ifres.getNode()=0 Then*如果結(jié)果為空，則邊不存在；否則存在*

⑥Print(不存在);

⑦ Else

⑧Print(存在);

⑨ EndIf

2) 外鄰查詢(包括求出度)

借助邊查詢，將要進(jìn)行外鄰查詢的頂點(diǎn)賦值為v1，圖中所有頂點(diǎn)依次賦值為v2，檢測E(v1,v2)的函數(shù)值.若值為T，則當(dāng)前v2是一個(gè)外鄰點(diǎn)，否則不是.通過統(tǒng)計(jì)外鄰點(diǎn)個(gè)數(shù)可以得到該頂點(diǎn)的出度.

3) 內(nèi)鄰查詢(包括求入度)

查詢方法與外鄰查詢類似，只不過要查詢的點(diǎn)賦值為v2，圖中所有頂點(diǎn)依次賦值為v1.

4) 增加邊

根據(jù)要增加邊的起止頂點(diǎn)v1和v2的編號(hào)得到該條邊的編號(hào)E(v1,v2)，生成該條邊的k2-MDD;然后與原圖的k2-MDD進(jìn)行UNION運(yùn)算，即得到增加了該邊的新圖的k2-MDD.

5) 刪除邊

根據(jù)要?jiǎng)h除邊的起止頂點(diǎn)v1和頂點(diǎn)v2的編號(hào)得到該條邊的編號(hào)E(v1,v2)，生成該條邊的k2-MDD;然后將原圖的k2-MDD與要?jiǎng)h除邊的k2-MDD進(jìn)行DIFFERENCE運(yùn)算，即得到刪除了該邊的新圖的k2-MDD.DIFFERENCE是求2個(gè)MDD的差運(yùn)算，執(zhí)行函數(shù)apply(DIFFERENCE,A,B,res)后，res={x|x∈A且x?B}.

根據(jù)上述圖的基本操作，可以很方便地拓展到圖的一些復(fù)雜操作，比如圖中寬度優(yōu)先搜索、求最短路、網(wǎng)絡(luò)流等.

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

由邊編碼集合構(gòu)造k2-MDD以及基于k2-MDD的有向圖的添加和刪除邊，由于涉及到MDD的初始化、生成、求交集、求并集及化簡等運(yùn)算過程，在文獻(xiàn)[9]中已經(jīng)進(jìn)行了復(fù)雜度分析，這里不再分析.

在構(gòu)造k2-MDD時(shí)，對(duì)圖的單個(gè)頂點(diǎn)編碼的時(shí)間復(fù)雜度為O(logk|V|)；同理，對(duì)圖的單條邊編碼的時(shí)間復(fù)雜度也是O(logk|V|)；因此對(duì)圖的所有邊進(jìn)行編碼的時(shí)間復(fù)雜度即為O(|E|logk|V|).

對(duì)于大規(guī)模圖數(shù)據(jù)存儲(chǔ)于操作，在實(shí)際應(yīng)用中，通常評(píng)價(jià)指標(biāo)是存儲(chǔ)結(jié)果和查詢時(shí)間，對(duì)于構(gòu)造時(shí)的復(fù)雜度一般并不關(guān)心.

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

本文利用MEDDLY庫，采用C++語言實(shí)現(xià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處理器，8 GB內(nèi)存.測試數(shù)據(jù)采用公開的真實(shí)數(shù)據(jù)集和隨機(jī)數(shù)據(jù)集.真實(shí)數(shù)據(jù)集使得實(shí)驗(yàn)結(jié)果具有更好的代表性，隨機(jī)數(shù)據(jù)集可以看出存儲(chǔ)結(jié)構(gòu)在不同規(guī)模圖數(shù)據(jù)下的節(jié)點(diǎn)數(shù)變化趨勢.

5.1 基于真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)

表1列出了測試中使用的真實(shí)網(wǎng)頁圖和社交網(wǎng)絡(luò)數(shù)據(jù)，數(shù)據(jù)均來自米蘭大學(xué)LAW(Laboratory for Web Algorithmics)[12].表1分別給出了這些數(shù)據(jù)集的頂點(diǎn)數(shù)、邊數(shù)、頂點(diǎn)數(shù)與邊數(shù)的比值以及這些數(shù)據(jù)集在網(wǎng)站的文件名.

Table 1 Description of Testing Real Graphs

在網(wǎng)頁圖中同一個(gè)域內(nèi)的網(wǎng)頁之間的鏈接數(shù)比較多，而域之間的鏈接數(shù)就比較少，其具備2個(gè)特征：

1) 本地性.大多數(shù)鏈接都是域內(nèi)的，它們通常會(huì)指向字典序比較靠近的頁面.

2) 相似性.在字典序中鄰近頁面的鄰居集合也是相似的.

而社交網(wǎng)絡(luò)圖并不可以直接對(duì)其中的節(jié)點(diǎn)進(jìn)行排序，但是也包含著類似于網(wǎng)頁圖體現(xiàn)的特征，例如同一個(gè)社區(qū)內(nèi)的好友關(guān)系數(shù)量比較多，而社區(qū)之間的好友關(guān)系數(shù)量就比較少.

對(duì)于這些真實(shí)數(shù)據(jù)集的特性，本文提出的k2-MDD結(jié)構(gòu)正好可以發(fā)揮其同構(gòu)子樹合并的優(yōu)勢.

針對(duì)這些數(shù)據(jù)集，分別使用k2樹、k2-MDD以及有序二叉決策圖(ordered binary decision diagram, OBDD)[10]共3種方法進(jìn)行了測試.表2給出了這些數(shù)據(jù)集在上述3種方法下的實(shí)驗(yàn)結(jié)果，表2中的數(shù)據(jù)為這3種存儲(chǔ)結(jié)構(gòu)的節(jié)點(diǎn)數(shù).

Table 2 The Experimental Results

5.2 基于隨機(jī)數(shù)據(jù)集的實(shí)驗(yàn)

除上述真實(shí)數(shù)據(jù)集外，我們隨機(jī)生成了11組圖數(shù)據(jù)，頂點(diǎn)數(shù)均為1 000，邊數(shù)分別為10 000，100 000，200 000，…，900 000，1 000 000.這些圖中頂點(diǎn)之間的連接關(guān)系完全隨機(jī)，因此沒有網(wǎng)頁圖和社交網(wǎng)絡(luò)的特性.需要說明的是，當(dāng)邊數(shù)為1 000 000時(shí)，圖為完全圖.圖13給出了k2樹和k2-MDD在這些隨機(jī)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果.

Fig. 13 The experimental results of the random graphs.圖13 隨機(jī)圖實(shí)驗(yàn)結(jié)果

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

對(duì)于真實(shí)數(shù)據(jù)集，從表2的實(shí)驗(yàn)結(jié)果中的數(shù)據(jù)可得，在選用的4組網(wǎng)頁圖上，k2-MDD的節(jié)點(diǎn)數(shù)平均僅為k2樹的2.59%；在選用的4組社交網(wǎng)絡(luò)上，k2-MDD的節(jié)點(diǎn)數(shù)平均僅為k2樹的4.51%.可以看出使用k2-MDD結(jié)構(gòu)來存儲(chǔ)圖可以大大減少節(jié)點(diǎn)數(shù)量，達(dá)到了預(yù)期效果.另外，還可以看到，OBDD結(jié)構(gòu)在存儲(chǔ)圖時(shí)，節(jié)點(diǎn)數(shù)也比k2樹大大減少，這也體現(xiàn)出了決策圖在節(jié)點(diǎn)合并方面的優(yōu)勢.

對(duì)于隨機(jī)數(shù)據(jù)集，從圖13的實(shí)驗(yàn)結(jié)果中的數(shù)據(jù)可以看出，在圖的頂點(diǎn)數(shù)不變的情況下，隨著邊數(shù)增多，即圖變的越來越稠密，k2樹的節(jié)點(diǎn)數(shù)在持續(xù)增加，而k2-MDD的節(jié)點(diǎn)數(shù)在圖的邊數(shù)達(dá)到完全圖的一半之后開始減少.這說明k2樹只適用于稀疏圖，而k2-MDD不僅適用于稀疏圖還適用于稠密圖.因?yàn)閗2樹只對(duì)某節(jié)點(diǎn)的指針全部指向0節(jié)點(diǎn)的情況進(jìn)行了合并，所以造成了這樣的結(jié)果.

在查詢時(shí)間方面，由于邊查詢的時(shí)間復(fù)雜度與k2樹相同，而同等規(guī)模的圖，k2-MDD與k2樹結(jié)構(gòu)的高度也相同，因此查詢時(shí)間不相上下.通過對(duì)真實(shí)數(shù)據(jù)集和隨機(jī)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證也確是如此.因此本文未給出k2-MDD與k2樹在查詢時(shí)間方面的數(shù)據(jù)對(duì)比.

6 結(jié)束語

本文提出了一種新的圖數(shù)據(jù)的表示方法——k2-MDD，這種存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)跟傳統(tǒng)思想有所區(qū)別.k2-MDD把有向圖的鄰接矩陣進(jìn)行k2劃分后，轉(zhuǎn)化為多值布爾函數(shù)并使用基于MDD的相關(guān)邏輯運(yùn)算對(duì)有向圖進(jìn)行操作.實(shí)驗(yàn)表明：在處理真實(shí)數(shù)據(jù)集時(shí)，k2-MDD的節(jié)點(diǎn)數(shù)比k2樹大大減少，優(yōu)勢相當(dāng)明顯；在處理隨機(jī)數(shù)據(jù)集時(shí)，k2-MDD不僅適用于稀疏圖，同樣也適用于稠密圖.當(dāng)存儲(chǔ)結(jié)構(gòu)變得緊湊之后，對(duì)于圖的相關(guān)計(jì)算的復(fù)雜度也會(huì)相應(yīng)地變低.文中給出了k2-MDD對(duì)圖的邊進(jìn)行增加與刪除的操作，稍加拓展，即可得到對(duì)頂點(diǎn)的添加與刪除以及對(duì)子圖的添加與刪除，因此本結(jié)構(gòu)適用于動(dòng)態(tài)圖.圖數(shù)據(jù)的k2-MDD表示，既具有k2樹表示的緊湊型和查詢的高效性，又能實(shí)現(xiàn)符號(hào)決策圖表示下圖模式的高效操作，從而實(shí)現(xiàn)了描述和計(jì)算能力的統(tǒng)一.

[1]Angles R, Gutierrez C. Survey of graph database models[J]. ACM Computing Surveys, 2008, 40(1): 1-39

[2]Robinson I, Webber J, Elfrem E. Graph Databases[M]. Sebastopol, CA: O’Reilly Media Press, 2015

[3]Zhang Yu, Liu Yanbing, Xiong Gang, et al. Survey on succinct representation of graph data[J]. Journal of Software, 2014, 25(9): 1937-1952 (in Chinese)(張宇, 劉燕兵, 熊剛, 等. 圖數(shù)據(jù)表示與壓縮技術(shù)綜述[J]. 軟件學(xué)報(bào), 2014, 25(9): 1937-1952)

[4]China Internet Network Information Center. The 37th statistical report on Internet development in China[EB/OL]. 2016[2016-01-31]. http://www.cnnic.net.cn/hlwfzyj/hlwxzbg/hlwtjbg/201601/t20160122_53271.htm (in Chinese)(中國互聯(lián)網(wǎng)絡(luò)信息中心. 第37次中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告[EB/OL]. 2016[2016-01-31]. http://www.cnnic.net.cn/hlwfzyj/hlwxzbg/hlwtjbg/201601/t20160122_53271.htm)

[5]Brisaboa N R, Ladra S, Navarro G.k2-trees for compact Web graph representation[C] //Proc of the 16th Int Symp on String Processing and Information Retrieval. Berlin: Springer, 2009: 18-30

[6]Brisaboa N R, Ladra S, Navarro G. Compact representation of Web graphs with extended functionality[J]. Information Systems, 2014, 39(1): 152-174

[7]Shi Quan, Xiao Yanghua, Lu Yiqi, et al. Towards optimizingk2-tree for large-scale graph storage[J]. Application Research of Computers, 2011, 28(7): 2488-2491 (in Chinese)(施佺, 肖仰華, 魯軼奇, 等. 基于k2樹的大圖存儲(chǔ)優(yōu)化研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2011, 28(7): 2488-2491)

[8]Shi Quan, Xiao Yanghua, Bessis N, et al. Optimizingk2-trees: A case for validating the maturity of network of practices[J]. Computers & Mathematics with Applications, 2012, 63(2): 427-436

[9]Srinivasan A, Ham T, Malik S, et al. Algorithms for discrete function manipulation[C] //Proc of ICCAD-90. Piscataway, NJ: IEEE, 1990: 92-95

[10]Gu Tianlong, Xu Zhoubo. Ordered Binary Decision Diagram and Its Application[M]. Beijing: Science Press, 2009 (in Chinese)(古天龍, 徐周波. 有序二叉決策圖及其應(yīng)用[M]. 北京: 科學(xué)出版社, 2009)

[11]Iowa State University Research Foundation. MEDDLY: Multi-terminal and edge-valued decision diagram library, Version 0.11.486[CP/OL]. 2014[2015-10-02]. http://meddly.sourceforge.net/index.html

[12]Department of Computer Science, University of Milan. Laboratory for Web algorithmics[DB/OL]. 2015[2015-11-01]. http://law.di.unimi.it/datasets.php

Dong Rongsheng, born in 1965. Professor. Senior member of China Computer Federation. His main research interests include protocol engineering and wirless sensor networks.

Zhang Xinkai, born in 1991. Master candidate. His main research interests include graph data representation and symbolic technology.

Liu Huadong, born in 1978. Lecturer. His main research interests include graph data representation and symbolic technology.

Gu Tianlong, born in 1964. PhD, professor, PhD supervisor. Senior member of China Computer Federation. His main research interests include formal method, formal computing and knowledge engineering.

Representation and Operations Research of k2-MDD in Large-Scale Graph Data

Dong Rongsheng, Zhang Xinkai, Liu Huadong, and Gu Tianlong

(Guangxi Key Laboratory of Trusted Software (Guilin University of Electronic Technology), Guilin, Guangxi 541004)

Efficient and compact representation and operation of graph data which contains hundreds of millions of vertices and edges are the basis of analyzing and processing the large scale of graph data. Aiming at the problem, this paper proposes a representation of large-scale graph data based on the decision diagram, that isk2-MDD, providing the initialization ofk2-MDD and the basic operation such as the edge query, inner(outer) neighbor query, finding out(in)-degree, adding(deleting) edge, etc. The representation method is optimized and improved on the basis ofk2tree, and after dividing the adjacency matrix of graph intok2, it is stored with the multi valued decision diagram, so as to achieve a more compact storage structure. According to the experimental results of a series of real Web graph and the social network graph data (cnr-2000, dewiki-2013, etc.) derived from the LAW laboratory at the University of Milan, it can be seen that the number ofk2-MDD’ nodes is only 2.59%-4.51% of thek2tree, which achieving the desired effect. According to the experimental results of random graphs, it can be seen that thek2-MDD structure is not only suitable for sparse graphs, but also for dense graphs. The graph data ofk2-MDD shows that both containing the compact and query efficiency representation ofk2tree and realizing the efficient operation of the graph model can thus achieve the unity of description and computing power.

graph data; storage optimization;k2-MDD;k2tree; decision diagram

2016-08-15；

2016-10-28

國家自然科學(xué)基金項(xiàng)目(U1501252,61363070,61572146,61363030)；廣西高等學(xué)校高水平創(chuàng)新團(tuán)隊(duì)及卓越學(xué)者計(jì)劃；桂林電子科技大學(xué)創(chuàng)新團(tuán)隊(duì)資助項(xiàng)目 This work was supported by the National Natural Science Foundation of China (U1501252, 61363070, 61572146, 61363030), the High Level Innovation Team of Guangxi Colleges and Universities and Outstanding Scholars Fund, and the Program for Innovative Research Team of Guilin University of Electronic Technology.

古天龍(gu@guet.edu.cn)

TP311