王澤奧，吳 斌，吳心宇，張子興

北京郵電大學(xué) 計(jì)算機(jī)學(xué)院，北京 100080

大規(guī)模多維網(wǎng)絡(luò)數(shù)據(jù)分析框架的研究與實(shí)現(xiàn)*

王澤奧+，吳 斌，吳心宇，張子興

北京郵電大學(xué) 計(jì)算機(jī)學(xué)院，北京 100080

隨著互聯(lián)網(wǎng)的快速發(fā)展和計(jì)算機(jī)應(yīng)用的不斷增加，大量的圖數(shù)據(jù)特別是社會(huì)網(wǎng)絡(luò)數(shù)據(jù)不斷生成。多維信息網(wǎng)絡(luò)已經(jīng)成為表示這些圖數(shù)據(jù)的通用方式。但是在多維信息網(wǎng)絡(luò)中，節(jié)點(diǎn)的類(lèi)型多種多樣，節(jié)點(diǎn)的屬性也不盡相同，如何對(duì)多維信息網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行多角度多粒度的分析，挖掘其中的隱藏信息，成為人們關(guān)注的焦點(diǎn)。圖聯(lián)機(jī)分析處理技術(shù)（graph online analytical processing，GraphOLAP）可以對(duì)圖數(shù)據(jù)進(jìn)行快速的聯(lián)機(jī)分析以及查詢(xún)操作。借助于GraphOLAP的現(xiàn)有成果，針對(duì)多維信息網(wǎng)絡(luò)的特點(diǎn)，提出了新的數(shù)據(jù)立方體框架。引入主節(jié)點(diǎn)的概念來(lái)指導(dǎo)元路徑的生成，通過(guò)元路徑指導(dǎo)網(wǎng)絡(luò)的上卷下鉆，提出屬性轉(zhuǎn)化和同質(zhì)轉(zhuǎn)化來(lái)豐富OLAP操作。最后討論了優(yōu)化的物化策略，使用并行計(jì)算框架Spark來(lái)實(shí)現(xiàn)算法，通過(guò)多個(gè)數(shù)據(jù)集驗(yàn)證了框架的有效性和高效性。

GraphOLAP；數(shù)據(jù)立方體；元路徑；Spark

1 背景介紹

近年來(lái)隨著社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)以及化合物網(wǎng)絡(luò)等領(lǐng)域的不斷發(fā)展，出現(xiàn)了大量的多屬性圖數(shù)據(jù)。研究如何對(duì)圖數(shù)據(jù)進(jìn)行多層次多角度的分析有著重要的意義。這些網(wǎng)絡(luò)如DBLP合作網(wǎng)絡(luò)、社交網(wǎng)絡(luò)FACEBOOK、IMDB電影合作網(wǎng)絡(luò)等，其中蘊(yùn)含大量的實(shí)體信息以及實(shí)體之間的關(guān)聯(lián)信息，深層次挖掘此類(lèi)信息是非常有必要的。實(shí)體類(lèi)型和聯(lián)系的多元化是分析和挖掘此類(lèi)信息網(wǎng)絡(luò)的難點(diǎn)。聯(lián)機(jī)分析處理技術(shù)（online analytical processing，OLAP）能夠提供用戶從不同維度、不同粒度觀察對(duì)象的視圖，是數(shù)據(jù)倉(cāng)庫(kù)和數(shù)據(jù)挖掘領(lǐng)域的核心技術(shù)之一，近年來(lái)得到了廣泛的研究應(yīng)用。但是OLAP基于的傳統(tǒng)數(shù)據(jù)立方體是同一種實(shí)體類(lèi)型的多維數(shù)據(jù)模型，不能有效契合圖數(shù)據(jù)分析的需求。

圖聯(lián)機(jī)分析處理技術(shù)（graph online analytical processing，GraphOLAP）結(jié)合了復(fù)雜網(wǎng)絡(luò)分析與聯(lián)機(jī)分析處理技術(shù)，將數(shù)據(jù)倉(cāng)庫(kù)中專(zhuān)門(mén)用于分析多維數(shù)據(jù)的聯(lián)機(jī)分析處理技術(shù)引入到復(fù)雜網(wǎng)絡(luò)分析當(dāng)中，用來(lái)解決復(fù)雜網(wǎng)絡(luò)中的多維度多角度分析問(wèn)題，從而展示不同層次和不同粒度上的網(wǎng)絡(luò)結(jié)構(gòu)和特性。

在傳統(tǒng)信息模型中，信息存儲(chǔ)為事實(shí)表和維度表。事實(shí)表中包含所有實(shí)體及其之間的關(guān)系，維度表中包含數(shù)據(jù)的多維屬性。通過(guò)立方體來(lái)指導(dǎo)OLAP的維度操作，通過(guò)聚集函數(shù)來(lái)描述不同維度聚集時(shí)的聚集方式，通過(guò)度量來(lái)描述不同維度下的分析結(jié)果。對(duì)于多屬性圖數(shù)據(jù)來(lái)說(shuō)，數(shù)據(jù)與數(shù)據(jù)之間存在關(guān)聯(lián)，這些關(guān)聯(lián)蘊(yùn)含著許多隱藏信息有待挖掘與分析。但是傳統(tǒng)的數(shù)據(jù)是記錄的形式，數(shù)據(jù)之間沒(méi)有關(guān)聯(lián)，利用傳統(tǒng)OLAP分析會(huì)丟掉這些關(guān)聯(lián)關(guān)系，不能對(duì)圖進(jìn)行充分有效的挖掘與分析。

對(duì)于多屬性圖的分析，除了傳統(tǒng)圖分析方法如最短路徑、中介行、模式匹配等，采用OLAP查詢(xún)來(lái)進(jìn)行信息發(fā)現(xiàn)和決策制定也有很大的發(fā)揮空間。這里根據(jù)用戶可能感興趣的點(diǎn)舉幾個(gè)簡(jiǎn)單的例子：

查詢(xún)1獲取點(diǎn)屬性或邊屬性信息。這些查詢(xún)往往能夠通過(guò)對(duì)點(diǎn)屬性或邊屬性的簡(jiǎn)單查詢(xún)得到。如“用戶群體中有多少中國(guó)人”或者是“電影都有哪些類(lèi)型”。

查詢(xún)2獲取點(diǎn)和邊的屬性組合之后的聚集信息，這些查詢(xún)需要將實(shí)體節(jié)點(diǎn)按照某一維度進(jìn)行聚集操作之后得到結(jié)果。如“有多少男人喜歡看喜劇片”“演員國(guó)籍與電影類(lèi)別之間的網(wǎng)絡(luò)結(jié)構(gòu)是什么樣子的”。

查詢(xún)3查詢(xún)特定實(shí)體關(guān)系的網(wǎng)絡(luò)屬性信息。這些查詢(xún)需要合并實(shí)體間的關(guān)系，形成新的實(shí)體關(guān)系以及新網(wǎng)絡(luò)。如“男人喜歡的電影是由哪個(gè)國(guó)家的演員參演的”。

對(duì)于查詢(xún)1，可以直接在節(jié)點(diǎn)表中進(jìn)行查詢(xún)，得到節(jié)點(diǎn)的維度屬性。查詢(xún)2需要將原圖中的一些節(jié)點(diǎn)按照需要進(jìn)行聚集操作得到新的聚集網(wǎng)絡(luò)。查詢(xún)3關(guān)注的是不同實(shí)體間的相互關(guān)系，根據(jù)異質(zhì)網(wǎng)絡(luò)元路徑聚集進(jìn)一步得到新的實(shí)體關(guān)系。

傳統(tǒng)的基于RDB（relation data base）的OLAP系統(tǒng)已經(jīng)難以滿足這些查詢(xún)需求，除了查詢(xún)1中的實(shí)體類(lèi)型查詢(xún)可以基于節(jié)點(diǎn)的維度表進(jìn)行查詢(xún)，其他查詢(xún)操作都要經(jīng)過(guò)多表連接操作。當(dāng)數(shù)據(jù)量很大時(shí)，數(shù)據(jù)庫(kù)的多表連接經(jīng)常會(huì)成為數(shù)據(jù)庫(kù)計(jì)算的瓶頸。而且傳統(tǒng)的數(shù)據(jù)立方體也不能很好地表現(xiàn)圖的結(jié)構(gòu)以及圖的復(fù)雜網(wǎng)絡(luò)屬性。因此設(shè)計(jì)適合大規(guī)模多維信息網(wǎng)絡(luò)的立方體，建立多維信息網(wǎng)絡(luò)的OLAP操作是十分有必要的。

隨著社交網(wǎng)絡(luò)的興起，網(wǎng)絡(luò)數(shù)據(jù)的規(guī)模也在不斷增加。傳統(tǒng)的集中式計(jì)算已經(jīng)不能滿足需求，引入并行化計(jì)算框架是非常有意義的。目前，常用的并行計(jì)算框架有Hadoop、Spark，并行圖計(jì)算框架有HAMA、GraphX、GraphLab等。這些并行圖計(jì)算框架對(duì)于圖類(lèi)型數(shù)據(jù)的迭代操作有很好的優(yōu)化，能有效地計(jì)算圖的相關(guān)結(jié)構(gòu)特征，如pagerank、shortest path、bipartite matching、semi-clustering等。但是對(duì)于多維信息網(wǎng)絡(luò)的OLAP操作會(huì)導(dǎo)致節(jié)點(diǎn)數(shù)量、屬性以及節(jié)點(diǎn)間的聯(lián)系發(fā)生改變，這種改變會(huì)進(jìn)一步導(dǎo)致網(wǎng)絡(luò)結(jié)構(gòu)改變以及網(wǎng)絡(luò)類(lèi)型改變?，F(xiàn)有的圖計(jì)算框架更適用于圖遍歷的迭代操作和圖分隔的優(yōu)化操作，對(duì)于圖中節(jié)點(diǎn)類(lèi)型以及拓?fù)浣Y(jié)構(gòu)發(fā)生重大變化的支持并不是很好。傳統(tǒng)的并行計(jì)算框架Hadoop和Spark雖然不是專(zhuān)門(mén)為了圖計(jì)算設(shè)計(jì)，但是通過(guò)建立合適的圖立方體模型，也可以進(jìn)行圖的挖掘分析[1]。因此選用Spark來(lái)完成對(duì)于立方體的相關(guān)操作。

在這些需求的引導(dǎo)下，本文提出了一種新的數(shù)據(jù)立方體模型，引入了主節(jié)點(diǎn)的概念，融入異質(zhì)網(wǎng)絡(luò)特性，并基于新的數(shù)據(jù)立方體模型賦予傳統(tǒng)的上卷下鉆新的含義。針對(duì)新的模型，設(shè)計(jì)了更多新的OLAP操作，為豐富查詢(xún)提供了模型上的支持。為了挖掘圖中的隱藏信息，設(shè)計(jì)了帶多維層次聚類(lèi)算法來(lái)進(jìn)行群體劃分和特征分析。為了提高查詢(xún)效率，設(shè)計(jì)了優(yōu)化的物化策略。模型是用并行化計(jì)算框架Spark完成的，支持大規(guī)模多維信息網(wǎng)絡(luò)的分析處理。通過(guò)多個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集實(shí)驗(yàn)，驗(yàn)證了模型的有效性和高效性。

本文的貢獻(xiàn)如下：

（1）定義了新的數(shù)據(jù)立方體模型StarGraphCube,將主節(jié)點(diǎn)的概念引入進(jìn)來(lái)指導(dǎo)網(wǎng)絡(luò)元路徑的生成，由網(wǎng)絡(luò)元路徑指導(dǎo)OLAP操作的進(jìn)行。并且根據(jù)立方體模型，豐富了GraphOLAP的操作，使得網(wǎng)絡(luò)分析更加多樣性。

（2）針對(duì)新的模型，提出了優(yōu)化的物化策略，使得維度操作的效率更高。

（3）使用并行計(jì)算框架實(shí)現(xiàn)，通過(guò)對(duì)大規(guī)模真實(shí)數(shù)據(jù)的實(shí)驗(yàn)，驗(yàn)證了模型對(duì)大規(guī)模數(shù)據(jù)能夠進(jìn)行有效并且高效的分析。

本文組織結(jié)構(gòu)如下：第2章定義了StarGraph-Cube模型以及一些新的OLAP分析操作；第3章討論了優(yōu)化的物化策略；第4章是模型在大規(guī)模數(shù)據(jù)集上的實(shí)驗(yàn)；第5章介紹相關(guān)工作；第6章總結(jié)全文。

2 星型數(shù)據(jù)模型

和傳統(tǒng)的OLAP立方體模型一樣，GraphOLAP需要通過(guò)數(shù)據(jù)立方體模型建立圖和數(shù)據(jù)倉(cāng)庫(kù)之間的關(guān)聯(lián)[2]。本文建立StarGraphCube模型，引入主節(jié)點(diǎn)的概念指導(dǎo)網(wǎng)絡(luò)元路徑的生成，能夠分析挖掘更多的潛在信息。

首先定義一些概念來(lái)清晰地描述本文的模型。由于現(xiàn)實(shí)中很多網(wǎng)絡(luò)可以被抽象成多維異質(zhì)信息網(wǎng)絡(luò)，可以定義如下。

定義1（多維異質(zhì)信息網(wǎng)絡(luò)）一個(gè)多維異質(zhì)信息網(wǎng)絡(luò)N表示為N=(V,E,T,A)，其中V表示節(jié)點(diǎn)的集合；E?V×V表示邊集合；T={T1,T2,…,Tn}表示節(jié)點(diǎn)的類(lèi)型集合，?u∈V，由于T(u)=Ti,1≤i≤n，即每個(gè)節(jié)點(diǎn)，只能取值一種節(jié)點(diǎn)類(lèi)型，當(dāng)n＞1時(shí)，網(wǎng)絡(luò)為異質(zhì)網(wǎng)絡(luò)；A={A1,A2,…,An}表示不同類(lèi)型節(jié)點(diǎn)的維度屬性集合，與節(jié)點(diǎn)類(lèi)型對(duì)應(yīng)，每一種節(jié)點(diǎn)類(lèi)型Ti有相應(yīng)的維度屬性集合Ai=(Ai1,Ai2,…,Aim)。對(duì)于?v∈V,T(v)=Tj,1≤j≤n，都有一個(gè)維度元組A(v)=(Aj1(v),Aj2(v),…,Ajm(v))，其中Ajk(v)表示節(jié)點(diǎn)v上的第k個(gè)屬性，即節(jié)點(diǎn)的第k維，1≤k≤m。

定義2（二元關(guān)系元路徑）對(duì)于多維異質(zhì)信息網(wǎng)絡(luò)模型N=(V,E,T,A)，V是節(jié)點(diǎn)集合，E是節(jié)點(diǎn)的關(guān)系集合，T為節(jié)點(diǎn)的類(lèi)型集合，A為節(jié)點(diǎn)的維度屬性集合。二元關(guān)系元路徑可表示為P(T1,Tn,list)=T1→T2→…→Ti→…→Tn，其中T1表示二元關(guān)系元路徑的起點(diǎn)，Tn表示二元關(guān)系元路徑的終點(diǎn)，Ti表示元路徑中第i個(gè)節(jié)點(diǎn)類(lèi)型，list表示二元關(guān)系路徑起點(diǎn)與終點(diǎn)間的路徑節(jié)點(diǎn)列表，路徑長(zhǎng)度為|list|+1；Ti→Ti+1是異質(zhì)網(wǎng)絡(luò)Schema的一條連通路徑。當(dāng)關(guān)系元路徑確定時(shí)，可以用P(T1,Tn)來(lái)代表P(T1,Tn,list)。為了簡(jiǎn)化問(wèn)題，不允許除了起點(diǎn)和終點(diǎn)的路徑上存在環(huán)。

關(guān)系元路徑代表了不同類(lèi)型節(jié)點(diǎn)之間的關(guān)系連接。兩個(gè)不同類(lèi)型的節(jié)點(diǎn)實(shí)體的關(guān)系路徑可能會(huì)存在多條，定義二元關(guān)系元路徑集合來(lái)表示這些起點(diǎn)和終點(diǎn)相同的元路徑集合。

定義3（二元關(guān)系元路徑集合）關(guān)系元路徑的定義基于異質(zhì)信息網(wǎng)絡(luò)模型N=(V,E,T,A)，V是節(jié)點(diǎn)集合，E是節(jié)點(diǎn)的關(guān)系集合，T為節(jié)點(diǎn)的類(lèi)型集合，A為節(jié)點(diǎn)的維度屬性集合。對(duì)于給定的兩個(gè)實(shí)體T1與Tn，兩個(gè)實(shí)體間可能存在多條可達(dá)路徑（規(guī)定除去起點(diǎn)與終點(diǎn)的路徑中不存在環(huán)），這些路徑的集合為二元關(guān)系元路徑集合，表示為Pset(T1,Tn)={P(T1,Tn,list1),P(T1,Tn,list2),…,P(T1,Tn,listn)}。

定義4（n元關(guān)系元路徑）基于異質(zhì)信息網(wǎng)絡(luò)模型N=(V,E,T,A)，V是節(jié)點(diǎn)集合，E是節(jié)點(diǎn)的關(guān)系集合，T為節(jié)點(diǎn)的類(lèi)型集合，A為節(jié)點(diǎn)的維度屬性集合。n元關(guān)系元路徑可表示為P(T1,T2,…,Ti,…,Tn,list)=T1→T2→…→Ti→…→Tn，其中Ti表示n元中的第i元節(jié)點(diǎn)類(lèi)型，list記錄了n元關(guān)系路徑除去起點(diǎn)T1與終點(diǎn)Tn的路徑序列。最終的n元關(guān)系元路徑是異質(zhì)網(wǎng)絡(luò)Schema的一條路徑，并且該路徑依次經(jīng)過(guò)T1,T2,…,Ti,…,Tn。同樣，規(guī)定相鄰類(lèi)型之間的路徑不存在環(huán)，即Ti→…→Ti+1的路徑中不存在環(huán)。當(dāng)n=2時(shí)，n元關(guān)系元路徑為二元關(guān)系元路徑。

定義5（n元關(guān)系元路徑集合）基于異質(zhì)信息網(wǎng)絡(luò)模型N=(V,E,T,A)與n元關(guān)系元路徑的定義，對(duì)于給定的n個(gè)實(shí)體的序列，在異質(zhì)網(wǎng)絡(luò)Schema中可能會(huì)存在多條通過(guò)這些類(lèi)型節(jié)點(diǎn)的n元關(guān)系元路徑，所有路徑形成的集合為n元關(guān)系元路徑集合，表示為Pset(T1,T2,…,Tn)={P(T1,T2,…,Tn,list1),P(T1,T2,…,Tn,list2),…,P(T1,T2,…,Tn,listn)}。n=2時(shí)，n元關(guān)系元路徑集合為二元關(guān)系元路徑集合。

定義6（實(shí)體類(lèi)型主節(jié)點(diǎn)）給定一個(gè)異質(zhì)信息網(wǎng)絡(luò)N=(V,E,T,A)，其中T={Ti|i=1,2,…,n}。針對(duì)每個(gè)節(jié)點(diǎn)類(lèi)型Ti，引入主節(jié)點(diǎn)VTi={Vi|T=Ti}代表同類(lèi)型的所有節(jié)點(diǎn)。用R表示所有主節(jié)點(diǎn)的集合，V′=V∪R,E′=E,A′=A，則異質(zhì)信息網(wǎng)絡(luò)可以表示為N′=(V′,E′,A′)。

引入主節(jié)點(diǎn)之后可以指導(dǎo)網(wǎng)絡(luò)元路徑的生成。對(duì)于n元關(guān)系元路徑P(T1,T2,…,Ti,…,Tn,list)=T1→T2→…→Ti→…→Tn的生成，可以分為兩步進(jìn)行：第一步，用主節(jié)點(diǎn)來(lái)構(gòu)建元路徑；第二步在每個(gè)主節(jié)點(diǎn)中VTi=V1→V2→…→Vi→…→Vn。

定義7（二元關(guān)系元路徑聚集網(wǎng)絡(luò)）給定一個(gè)異質(zhì)信息網(wǎng)絡(luò)N=(V,E,T,A)以及一條二元關(guān)系元路徑P(T1,T2,…,Ti,…,Tn,list)=T1→T2→ … →Ti→ … →Tn。在二元關(guān)系元路徑的指導(dǎo)下，將T1→T2→…→Ti→…→Tn轉(zhuǎn)換為；再合并為，形成聚集網(wǎng)絡(luò)N′=(V′,E′,T′,A′)，其中T′={T1,Tn}，A′={A1,An}，V′是類(lèi)型為T(mén)1、Tn的節(jié)點(diǎn)集合，E′是合并形成的節(jié)點(diǎn)的邊集合。

定義8（n元關(guān)系元路徑聚集網(wǎng)絡(luò)）給定一個(gè)異質(zhì)信息網(wǎng)絡(luò)N=(V,E,T,A)以及一條n元關(guān)系元路徑P(T1,T2,…,Ti,…,Tn,list)，在n元關(guān)系元路徑的作用下，與二元關(guān)系元路徑網(wǎng)絡(luò)的聚集方式相同，將網(wǎng)絡(luò)中不同節(jié)點(diǎn)的類(lèi)型按照關(guān)系元路徑P(T1,T2,…,Ti,…,Tn,list)合并成聚集網(wǎng)絡(luò)N′=(V′,E′,T′,A′)，其中T′={T1,T2,…,Tn}，A′={A1,A2,…,An}，V′是類(lèi)型為T(mén)1,T2,…,Tn的節(jié)點(diǎn)集合，E′是合并形成的節(jié)點(diǎn)的邊集合。

對(duì)于由原始網(wǎng)絡(luò)可以得到的n元關(guān)系元路徑聚集網(wǎng)絡(luò)Nn與n+1元關(guān)系元路徑聚集網(wǎng)絡(luò)Nn+1，由Nn+1不一定能夠得到n元關(guān)系元路徑聚集網(wǎng)絡(luò)Nn。

本文提出StarGraphCube模型，能夠?qū)Χ嗑S異質(zhì)信息網(wǎng)絡(luò)進(jìn)行更加豐富的OLAP操作。

定義9（StarGraphCube）給定一個(gè)多維異質(zhì)信息網(wǎng)絡(luò)N=(V,E,T,A)，網(wǎng)絡(luò)中一共有n種不同類(lèi)型的節(jié)點(diǎn)，對(duì)于第Ti種類(lèi)型的節(jié)點(diǎn)共有|Ai|種不同的維度屬性，通過(guò)這些不同類(lèi)型節(jié)點(diǎn)以及不同維度進(jìn)行所有可能的聚集組合得到。將聚合操作分成兩步：第一步通過(guò)主節(jié)點(diǎn)構(gòu)建n元關(guān)系元路徑P(T1,T2,…,Ti,…,Tn,list)，得到n元關(guān)系元路徑聚集網(wǎng)絡(luò)；第二步通過(guò)在主節(jié)點(diǎn)內(nèi)進(jìn)行某一維度的聚集，選定特定的維度集合A′，得到最終的聚集網(wǎng)絡(luò)。通過(guò)對(duì)聚集網(wǎng)絡(luò)進(jìn)行查詢(xún)操作，能夠便于OLAP操作，對(duì)于進(jìn)一步處理有著重要的意義。

StarGraphCube首先根據(jù)關(guān)系元路徑的指導(dǎo)在主節(jié)點(diǎn)構(gòu)成實(shí)體立方體，立方體的每個(gè)方體是對(duì)應(yīng)的n元關(guān)系元路徑合集，每一個(gè)實(shí)體方體可以產(chǎn)生2|T|-1個(gè)聚集方體，每個(gè)方體對(duì)應(yīng)的n元關(guān)系元路徑集合包含的關(guān)系元路徑不確定，因此聚集網(wǎng)絡(luò)的數(shù)量不能確定。對(duì)于聚集得到的實(shí)體方體，在n元關(guān)系元路徑的指導(dǎo)下進(jìn)一步聚集，有n種節(jié)點(diǎn)類(lèi)型T1,T2,…,Tn，對(duì)應(yīng)維度A1,A2,…,An一共有個(gè)聚集立方體。

圖1（a）展示了異質(zhì)網(wǎng)絡(luò)的架構(gòu)。一共有3種實(shí)體A、B、C。A對(duì)應(yīng)于User，B對(duì)應(yīng)于Movie，C對(duì)應(yīng)于Actor。A有1個(gè)維度屬性，B有兩個(gè)維度屬性，C有兩個(gè)維度屬性。該多維異質(zhì)網(wǎng)絡(luò)形成的實(shí)體關(guān)系體模型如圖1（b）所示，共可以形成23-1=7個(gè)聚集方體，其中<*,*,*＞為特殊方體，每個(gè)方體中可能包括多條元路徑，如方體

在StarGraphCube中實(shí)體立方體通過(guò)關(guān)系元路徑引導(dǎo)網(wǎng)絡(luò)聚集，可以滿足查詢(xún)3的需求；實(shí)體立方體通過(guò)關(guān)系元路徑引導(dǎo)維度上的聚集操作，可以滿足查詢(xún)2的需求，實(shí)體立方體結(jié)合維度聚集操作，可以滿足查詢(xún)1、查詢(xún)2和查詢(xún)3的復(fù)合查詢(xún)需求。如在第1章提到的“有多少男人喜歡看喜劇片”，首先選取

在傳統(tǒng)OLAP中，上卷與下鉆是最重要的兩個(gè)操作。在StarGraphCube中，上卷下鉆操作主要在實(shí)體立方體上進(jìn)行。上卷意味著從底層的n元關(guān)系元路徑聚集得到相應(yīng)的n-m元關(guān)系元路徑聚集網(wǎng)絡(luò)(0＜m＜n)，對(duì)應(yīng)的逆向操作為下鉆操作。

同質(zhì)轉(zhuǎn)換操作：給定一個(gè)多維異質(zhì)信息網(wǎng)絡(luò)N=(V,E,T,A)，選定節(jié)點(diǎn)類(lèi)型集合T，對(duì)其中某一個(gè)節(jié)點(diǎn)類(lèi)型Ti，若在實(shí)體立方體中類(lèi)型為T(mén)i的節(jié)點(diǎn)Vi、Vj與同一個(gè)節(jié)點(diǎn)存在邊的關(guān)系，則在節(jié)點(diǎn)Vi與Vj之間構(gòu)建同質(zhì)的邊。

同質(zhì)轉(zhuǎn)換操作給人們發(fā)現(xiàn)同質(zhì)節(jié)點(diǎn)之間的隱藏信息做鋪墊。在多維異質(zhì)信息網(wǎng)絡(luò)中，實(shí)體的類(lèi)型多種多樣，同實(shí)體間的關(guān)系主要通過(guò)其他類(lèi)型實(shí)體節(jié)點(diǎn)進(jìn)行建立。通過(guò)同質(zhì)轉(zhuǎn)換操作，發(fā)掘異質(zhì)網(wǎng)絡(luò)中的同質(zhì)網(wǎng)絡(luò)信息，進(jìn)行群體劃分和分析。

屬性轉(zhuǎn)換：給定一個(gè)多維異質(zhì)信息網(wǎng)絡(luò)N=(V,E,T,A)，選定某一類(lèi)型節(jié)點(diǎn)集合Tt，對(duì)每一個(gè)節(jié)點(diǎn)類(lèi)型Tti與維度集合Ai中的m個(gè)維度屬性{Aij,1≤j≤m}，將這m個(gè)維度屬性值變換成節(jié)點(diǎn)加入節(jié)點(diǎn)集合形成新的節(jié)點(diǎn)集合V′與類(lèi)型集合T′。對(duì)于新節(jié)點(diǎn)Aij與Aij′，若屬于同一節(jié)點(diǎn)或者隸屬的節(jié)點(diǎn)之間存在邊，則建立兩者之間的邊關(guān)系并加入邊集形成E′。最終得到屬性轉(zhuǎn)換網(wǎng)絡(luò)N′=(V′,E′,T′,A)。

同質(zhì)轉(zhuǎn)換操作的算法如下：

算法1同質(zhì)轉(zhuǎn)換

屬性轉(zhuǎn)換操作的算法如下：

算法2屬性轉(zhuǎn)化

3 優(yōu)化物化策略

在實(shí)體立方體上的上卷下鉆操作需要根據(jù)關(guān)系元路徑重組網(wǎng)絡(luò)節(jié)點(diǎn)，計(jì)算的復(fù)雜度很高。對(duì)于大規(guī)模網(wǎng)絡(luò)這些操作是十分耗時(shí)的，因此提出了下面的一些優(yōu)化算法。

3.1 操作優(yōu)化

二元關(guān)系元路徑聚集操作將網(wǎng)絡(luò)中的多個(gè)實(shí)體屬性在二元關(guān)系元路徑P(T1,Tn,list)=T1→T2→…→Ti→…→Tn的指導(dǎo)下，形成以起點(diǎn)和終點(diǎn)類(lèi)型構(gòu)成的網(wǎng)絡(luò)?？梢詫⑾噜彽墓?jié)點(diǎn)做join操作，逐步合并中間路徑節(jié)點(diǎn)，最終得到T1→Tn的網(wǎng)絡(luò)。join操作的復(fù)雜度和邊的大小與計(jì)算方法有關(guān)系，若原始網(wǎng)絡(luò)有l(wèi)條邊，join的復(fù)雜度為O(α(l))。二元關(guān)系元路徑長(zhǎng)度為|list|+1，則最終的復(fù)雜度為O(α(l)×(|list|+1))。二元關(guān)系元路徑的長(zhǎng)度增加，計(jì)算復(fù)雜度也會(huì)逐漸增加，同時(shí)起點(diǎn)與終點(diǎn)的關(guān)聯(lián)性越弱，得到的網(wǎng)絡(luò)可分析性越弱。因此一般聚集網(wǎng)絡(luò)的二元關(guān)系元路徑不會(huì)太長(zhǎng)，否則得到的圖就沒(méi)有分析的意義。二元關(guān)系元路徑的聚集網(wǎng)絡(luò)的計(jì)算可以表示N′=agg2meta(N,T1,Tn,list)，其中N表示多維信息網(wǎng)絡(luò)，T1表示起點(diǎn)類(lèi)型，Tn表示終點(diǎn)類(lèi)型，list表示二元關(guān)系元路徑序列。N′為二元關(guān)系元路徑聚集網(wǎng)絡(luò)，生成算法見(jiàn)算法1。遍歷的循環(huán)可以使用Spark的map函數(shù)生成對(duì)應(yīng)邊的RDD，利用RDD的join函數(shù)對(duì)算法1進(jìn)行并行操作。

對(duì)于n元關(guān)系元路徑的聚集網(wǎng)絡(luò)計(jì)算，根據(jù)定義可知n元關(guān)系元路徑可以由n-1個(gè)二元關(guān)系元路徑拼接而成，故二元關(guān)系元路徑指導(dǎo)的網(wǎng)絡(luò)聚集操作可以轉(zhuǎn)換成n-1個(gè)二元關(guān)系元路徑網(wǎng)絡(luò)指導(dǎo)的聚集操作，最后將n-1個(gè)聚集網(wǎng)絡(luò)合并。

3.2 實(shí)體立方體物化

立方體的物化策略一共有3種：不物化、部分物化和完全物化。不物化策略是指在每一次的計(jì)算過(guò)程中，都直接生成所需網(wǎng)絡(luò)再計(jì)算結(jié)果。這種策略不需要耗費(fèi)很多內(nèi)存空間，但是當(dāng)數(shù)據(jù)量很大時(shí)，每一步的計(jì)算時(shí)間會(huì)顯著增加，不適合大數(shù)據(jù)量的操作。完全物化策略是指在計(jì)算初期，就將數(shù)據(jù)立方體的所有網(wǎng)絡(luò)計(jì)算出來(lái)并保存。這種方法在數(shù)據(jù)立方體的維度較多的情況下，計(jì)算初期需要花費(fèi)大量時(shí)間并且占用大量的內(nèi)存。部分物化策略是在計(jì)算初期，按照一定方案將數(shù)據(jù)立方體的部分網(wǎng)絡(luò)計(jì)算出來(lái)并保存。這種方式兼顧了時(shí)間和空間效率，因此本文選擇這種物化策略。

對(duì)于實(shí)體立方體，由于關(guān)系元路徑的多樣性，每一個(gè)方體可能會(huì)產(chǎn)生多個(gè)聚集網(wǎng)絡(luò)，整個(gè)立方體的聚集網(wǎng)絡(luò)不容易計(jì)算出來(lái)。而由于n元關(guān)系元路徑可以利用n-1個(gè)對(duì)應(yīng)的二元關(guān)系元路徑聚集網(wǎng)絡(luò)得到，對(duì)于n元關(guān)系元路徑產(chǎn)生的聚集網(wǎng)絡(luò)，是路徑中的一點(diǎn)，則二元關(guān)系元路徑的計(jì)算可以通過(guò)將P(T1,Ti,list)和P(Ti,Tn,list)的聚集網(wǎng)絡(luò)連接得到。因此物化策略選擇優(yōu)先物化二元關(guān)系元路徑聚集網(wǎng)絡(luò)，初始物化所有二元關(guān)系元路徑集合的最短元路徑聚集網(wǎng)絡(luò)。若一共有n種類(lèi)型的實(shí)體，則物化產(chǎn)生n(n-1)/2個(gè)聚集網(wǎng)絡(luò)。

另外在物化過(guò)程中，如果要計(jì)算二元關(guān)系元路徑聚集網(wǎng)絡(luò)，可以先檢查是否已經(jīng)物化過(guò)。如果之前已經(jīng)物化過(guò)，則可以直接利用。

3.3 維度編碼

傳統(tǒng)的OLAP查詢(xún)中，事實(shí)表往往比維度表大很多，維度表所占的事實(shí)表比例基本都在1%左右，一般不會(huì)超過(guò)3%。數(shù)據(jù)規(guī)模越大，維度表所占比例越低。而且數(shù)據(jù)倉(cāng)庫(kù)查詢(xún)具有高輸入低輸出的特點(diǎn)。在SSB標(biāo)準(zhǔn)測(cè)試集中，任何一個(gè)查詢(xún)輸出記錄都在1 000條以下[3]。直接將維度表進(jìn)行維度編碼壓縮，融入事實(shí)表中，能夠大大減少事實(shí)表與維度表的連接操作，而且輸出結(jié)果數(shù)據(jù)量很小，解碼時(shí)間也很短，運(yùn)行效率會(huì)大大提升。

對(duì)于節(jié)點(diǎn)的維度進(jìn)行編碼并存入邊表中，這樣在進(jìn)行維度操作時(shí)可以只進(jìn)行邊表的計(jì)算，而不需要邊表與維度表的連接操作。使用位運(yùn)算與二進(jìn)制，對(duì)節(jié)點(diǎn)名稱(chēng)、節(jié)點(diǎn)類(lèi)型、節(jié)點(diǎn)維度一次進(jìn)行等位編碼，最終形成節(jié)點(diǎn)存入邊表中，編碼形式為節(jié)點(diǎn)類(lèi)型編碼+節(jié)點(diǎn)名稱(chēng)編碼+節(jié)點(diǎn)維度編碼。其中節(jié)點(diǎn)類(lèi)型編碼位數(shù)為，T為節(jié)點(diǎn)類(lèi)型，|T|+1表示維度上卷下鉆形成的節(jié)點(diǎn)。節(jié)點(diǎn)編碼算法如下。

（1）節(jié)點(diǎn)編碼

由定義可得編碼實(shí)例：User U3 Male China:000 010 0 01。通過(guò)前3位得到類(lèi)型，類(lèi)型000表示User；接下來(lái)3位表示用戶編碼，010表示用戶名稱(chēng)U3；接下來(lái)1位表示用戶性別，0代表男性；最后2位表示用戶國(guó)家，01表示USA。

（2）維度上卷編碼

例如圖中的movie Category聚集形成Comedy節(jié)點(diǎn)，首先是類(lèi)型編碼100，之后是上卷的類(lèi)型編碼，Movie為001，上卷維度數(shù)量為1，編碼為1。上卷維度在movie類(lèi)型中是第0個(gè)編號(hào)，編碼為0，取值Comedy編碼為01，如果后面還有編碼則表示下個(gè)類(lèi)型的上卷維度。最終Comedy編碼為1000011001。

4 實(shí)驗(yàn)驗(yàn)證

本文將在4個(gè)節(jié)點(diǎn)的本地集群上進(jìn)行模型和算法的實(shí)驗(yàn)。每個(gè)節(jié)點(diǎn)由2個(gè)E5-2620 6(12)@2.0 GHz CPU，64 GB內(nèi)存和500 GB SATA disks構(gòu)成。實(shí)驗(yàn)的環(huán)境主要是基于Hadoop 2.6.0和Spark 1.5.1。

本文將在真實(shí)數(shù)據(jù)集和模擬數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)驗(yàn)證。其中真實(shí)數(shù)據(jù)集為MAG（Microsoft academic graph）和IMDB數(shù)據(jù)集，模擬數(shù)據(jù)集為使用模擬算法生成的數(shù)據(jù)集。真實(shí)數(shù)據(jù)集主要用來(lái)驗(yàn)證模型的有效性，而模擬數(shù)據(jù)用來(lái)驗(yàn)證模型的高效性。

4.1 有效性驗(yàn)證

4.1.1 MAG數(shù)據(jù)集

該數(shù)據(jù)集是由微軟在2016年發(fā)布，主要包含作者、論文和會(huì)議的關(guān)系，其中不同的實(shí)體有不同的維度屬性。數(shù)據(jù)集中包含114 698 044個(gè)作者，126 909 021篇論文，1 283個(gè)會(huì)議。在有效性實(shí)驗(yàn)中，重點(diǎn)關(guān)注了4個(gè)領(lǐng)域：database（DB）、data mining（DM）、artificial intelligence（AI）和information retrieval（IR）。

實(shí)驗(yàn)中，通過(guò)建立StarGraphCube模型以及關(guān)系元路徑的聚集和維度的聚集進(jìn)行作者合作網(wǎng)絡(luò)的分析。

首先以二元關(guān)系元路徑P(Author,Author)=Author→Paper→Author聚集得到作者合作網(wǎng)絡(luò)。選定Philip S Yu作為研究對(duì)象，可以得到與他合作最緊密的作者，在field維度上聚集得到選定的4個(gè)領(lǐng)域之間的關(guān)系。從圖2（a）中可以知道，DB領(lǐng)域作者與DM領(lǐng)域作者合作的頻率比和AI、IR領(lǐng)域作者合作的頻率更高，而且DB領(lǐng)域的作者更傾向于跟自己領(lǐng)域的作者合作。IR領(lǐng)域的作者傾向于跟非自己領(lǐng)域的作者合作，跟DB領(lǐng)域作者合作的頻率比AI、DM的頻率更高。對(duì)P(Author,Paper)=Author→Paper聚集網(wǎng)絡(luò)進(jìn)行field維度上卷，可以得到作者與field的網(wǎng)絡(luò)。從圖2（c）中可以看出，Philip S Yu的主要領(lǐng)域是datamining，并且和CharuCAggarwal的合作最為緊密。

4.1.2 IMDB數(shù)據(jù)集

該數(shù)據(jù)集從IMDB的官網(wǎng)爬取，主要包含用戶、電影和演員之間的關(guān)系，其中不同的實(shí)體有不同的維度屬性。數(shù)據(jù)集中包含Movies:129 918，Actors:832 087。在有效性實(shí)驗(yàn)中，主要選取了4種電影類(lèi)型Drama、Comedy、Short和Adult進(jìn)行研究。

在本次實(shí)驗(yàn)中，重點(diǎn)關(guān)注了Drama、Comedy、Short、Adult這4種類(lèi)型的電影。通過(guò)建立Star Graph-Cube模型以及關(guān)系元路徑的聚集與維度的聚集進(jìn)行科研網(wǎng)絡(luò)的分析。

首先以二元關(guān)系元路徑P(Movie,Movie)=Movie→Actor→Movie聚集得到電影的關(guān)系網(wǎng)絡(luò)圖。將Movie進(jìn)行類(lèi)型維度的上卷，聚集函數(shù)采用count(*)，得到4個(gè)類(lèi)型電影的關(guān)系如圖3（a）。

同時(shí)也可以對(duì)單點(diǎn)進(jìn)行分析。通過(guò)二元關(guān)系元路徑P(Actor,Movie)=Actor→Movie的聚集網(wǎng)絡(luò)進(jìn)行Movie的類(lèi)型維度上卷，可以得到Actor和電影類(lèi)型的關(guān)系網(wǎng)絡(luò)。通過(guò)電影的發(fā)行國(guó)家維度上卷得到Actor和電影發(fā)行國(guó)家之間的關(guān)系。通過(guò)二元關(guān)系元路徑P(Actor,Actor)=Actor→Movie→Actor聚集得到演員合作關(guān)系網(wǎng)絡(luò)，可以知道與演員合作最密切的其他演員。如圖3（c）中Jonny Depp經(jīng)常出演的電影類(lèi)型是Comedy和Drama，大多數(shù)電影都是由美國(guó)公司發(fā)行的。

4.2 高效性驗(yàn)證

4.2.1 實(shí)體立方體效能驗(yàn)證

在該實(shí)驗(yàn)中使用MAG數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，將MAG數(shù)據(jù)集分為5份，每一份的大小分別為2×106，4×106，6×106，8×106，10×106。

Fig.2 Experiments on MAG datasets圖2 MAG實(shí)驗(yàn)結(jié)果

Fig.3 Experiments on IMDB datasets圖3 IMDB實(shí)驗(yàn)結(jié)果

首先對(duì)不同的二元關(guān)系元路徑聚集網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)。選取P1(Author,Paper)=Author→Paper,P2(Author,Conference)=Author→Paper→Conference,P2(Author,Author)=Author→Paper→Author。實(shí)驗(yàn)結(jié)果如圖4（a）所示。由P1(Author,Paper)與P2(Author,Conference)的比較可以看出，隨著路徑的增加，需要的時(shí)間也會(huì)增加。由P2(Author,Conference)和P3(Author,Author)的比較可以知道，P2產(chǎn)生的作者和會(huì)議的網(wǎng)絡(luò)，依賴(lài)關(guān)系緊密，產(chǎn)生的網(wǎng)絡(luò)規(guī)模較小。而P3產(chǎn)生的是作者合作網(wǎng)絡(luò)，同一篇文章的合作者較多，產(chǎn)生的網(wǎng)絡(luò)規(guī)模較大。因此相同長(zhǎng)度元路徑的聚集網(wǎng)絡(luò)，需要的時(shí)間也會(huì)不同。由圖可知，隨著邊數(shù)的增加，消耗的時(shí)間是線性變化的，即O(α(l))=O(l)，最終的時(shí)間復(fù)雜度是O(l×|list|+1)。

然后對(duì)物化策略進(jìn)行實(shí)驗(yàn)。選取關(guān)系元路徑P(Author,Author)=Author→Paper→Conference→Paper→Author進(jìn)行聚集操作。物化Author→Paper→Conference路徑的聚集網(wǎng)絡(luò)，則不物化的聚集操作需要進(jìn)行4次join操作。對(duì)于物化后，則只需要進(jìn)行1次join操作，實(shí)驗(yàn)結(jié)果如圖4（b）。通過(guò)物化可以減少重復(fù)的聚集計(jì)算，提高運(yùn)行效率。

4.2.2 維度屬性編碼

該實(shí)驗(yàn)使用模擬的多維網(wǎng)絡(luò)數(shù)據(jù)。首先驗(yàn)證維度屬性編碼對(duì)性能的提升，從維度數(shù)目和網(wǎng)絡(luò)規(guī)模兩個(gè)角度出發(fā)進(jìn)行實(shí)驗(yàn)。從維度數(shù)目角度生成維度數(shù)目為3、5、7、9的網(wǎng)絡(luò)，分別采用點(diǎn)邊join方式與本文提出維度編碼的方式進(jìn)行維度roll up，得到的結(jié)果如圖4（c）所示。從圖中可知，維度編碼能夠大大提高網(wǎng)絡(luò)聚集的效率，隨著網(wǎng)絡(luò)維度的增加，點(diǎn)邊join方法與維度編碼方法性能變化相似，消耗的時(shí)間都有所增加。這是由于維度增加，需要的存儲(chǔ)空間更多導(dǎo)致的。從網(wǎng)絡(luò)規(guī)模的角度生成了邊數(shù)分別為1×106，10×106和100×106的多維網(wǎng)絡(luò)，并分別進(jìn)行了聚集操作，得到的結(jié)果如圖4（d）所示。可以看出，隨著網(wǎng)絡(luò)規(guī)模的增加，維度編碼對(duì)效率的提升也不斷增加，維度編碼的方式也更加有優(yōu)勢(shì)。通過(guò)維度編碼能夠大大提高對(duì)大規(guī)模網(wǎng)絡(luò)的分析性能。

然后，研究了屬性轉(zhuǎn)換操作。圖4（e）呈現(xiàn)了屬性轉(zhuǎn)換的維度數(shù)量與時(shí)間的關(guān)系。可以看出，隨著屬性轉(zhuǎn)換的維度數(shù)量的增加，消耗的時(shí)間有加速上升的趨勢(shì)。這是因?yàn)閷傩赞D(zhuǎn)換生成的網(wǎng)絡(luò)以維度屬性為節(jié)點(diǎn)，隨著屬性轉(zhuǎn)換成維度，生成的網(wǎng)絡(luò)規(guī)模呈非線性增加的規(guī)律。

接著，研究了同質(zhì)轉(zhuǎn)換操作，圖4（f）呈現(xiàn)了同質(zhì)轉(zhuǎn)換的邊數(shù)量與時(shí)間的關(guān)系。可以看出，隨著同質(zhì)轉(zhuǎn)換的邊數(shù)量呈指數(shù)增長(zhǎng)，消耗的時(shí)間也在不斷增加。這是因?yàn)殡S著邊數(shù)量的增加，同一個(gè)節(jié)點(diǎn)的鄰居數(shù)量也在不斷增加，建立同類(lèi)型節(jié)點(diǎn)間的關(guān)系概率也在不斷增加。

5 相關(guān)工作

Fig.4 Efficiency experiment results圖4 高效性驗(yàn)證

傳統(tǒng)OLAP的研究起步較早，技術(shù)規(guī)范相對(duì)比較成熟，對(duì)于相關(guān)領(lǐng)域的應(yīng)用也比較深入。但是對(duì)于圖數(shù)據(jù)的GraphOLAP研究尚且處于起步階段。

最開(kāi)始吳巍[4]提出了Link OLAP的概念，通過(guò)將面向?qū)嶓w的分析擴(kuò)展到面向連接的分析，結(jié)合復(fù)雜網(wǎng)絡(luò)中的網(wǎng)絡(luò)可視化技術(shù)，將OLAP技術(shù)應(yīng)用到面向連接的分析，突破了以往傳統(tǒng)OLAP系統(tǒng)中單調(diào)的二維表格表現(xiàn)形式，OLAP的研究也逐漸轉(zhuǎn)向關(guān)聯(lián)的屬性度量和圖。

Chen等人[5]首次正式提出了GraphOLAP的概念，并且定義了信息維、拓?fù)渚S以及在這些維度上面的上卷下鉆切塊切片等操作，第一次較為系統(tǒng)地提出了GraphOLAP的概念，但是對(duì)于整個(gè)GraphOLAP的系統(tǒng)框架沒(méi)有進(jìn)行概述。

李川等人[6]設(shè)計(jì)了一種適合GraphOLAP的數(shù)據(jù)倉(cāng)庫(kù)模型——雙星模型，提出了信息維聚集算法和拓?fù)渚S聚集算法，并將理論的GraphOLAP進(jìn)行了實(shí)現(xiàn)，但是使用的功能場(chǎng)景相對(duì)單一。

Zhao等人[7]針對(duì)數(shù)據(jù)倉(cāng)庫(kù)和多維網(wǎng)絡(luò)分析的Graph Cube模型，將傳統(tǒng)OLAP中立方體的概念與圖融合，并利用傳統(tǒng)OLAP的概念，將方體查詢(xún)引入到圖數(shù)據(jù)分析上，提出了crossboid查詢(xún)，使得圖數(shù)據(jù)也可以像表數(shù)據(jù)進(jìn)行復(fù)雜的查詢(xún)。除此之外還實(shí)現(xiàn)了物化操作，將圖數(shù)據(jù)對(duì)應(yīng)到傳統(tǒng)數(shù)據(jù)倉(cāng)庫(kù)以及OLAP操作，重點(diǎn)實(shí)現(xiàn)了OLAP多維分析的查詢(xún)功能，使得傳統(tǒng)的數(shù)據(jù)倉(cāng)庫(kù)以及OLAP的功能得到拓展。

Yin等人[8]提出了HMGraph OLAP模型，引入了實(shí)體維的概念，支持異質(zhì)網(wǎng)絡(luò)的分析，并且加入了旋轉(zhuǎn)和拉伸操作，在物化方面也采用相應(yīng)的策略。

Denis等人[9]將GraphOLAP的操作算法用并行框架實(shí)現(xiàn)，并與傳統(tǒng)的集中式算法進(jìn)行了對(duì)比，對(duì)大規(guī)模數(shù)據(jù)有著較好的效果。

Wang等人[10]利用Hadoop實(shí)現(xiàn)了Pagrol并行圖分析系統(tǒng)，并且改進(jìn)了圖立方體模型，加入了邊維度屬性的上卷下鉆，通過(guò)一些優(yōu)化操作使得系統(tǒng)有效高效地運(yùn)行。

Wang等人[11]針對(duì)異質(zhì)網(wǎng)絡(luò)分析能力不足的問(wèn)題，引入了關(guān)系元路徑的概念，設(shè)計(jì)了TSMH Graph Cube模型，并且擴(kuò)展了上卷下鉆的語(yǔ)義，給出了優(yōu)化的物化策略，引入了并行計(jì)算框架來(lái)進(jìn)行大數(shù)據(jù)處理。

除此之外，Hannachi[12]、Weiler[13]、Liu等人[14]也提出了針對(duì)社交網(wǎng)絡(luò)的立方體模型，Qu[15]、Jakawat等人[16]對(duì)文獻(xiàn)數(shù)據(jù)以及知識(shí)網(wǎng)絡(luò)實(shí)現(xiàn)了GraphOLAP的模型系統(tǒng)，Sun[17]、Shi等人[18]將數(shù)據(jù)庫(kù)和內(nèi)鏈接的數(shù)據(jù)視為異質(zhì)信息網(wǎng)絡(luò)，并研究如何利用實(shí)體的語(yǔ)義信息和網(wǎng)絡(luò)中的內(nèi)鏈接，Junghanns等人[19]將Hadoop引入到OLAP中以處理大規(guī)模的圖數(shù)據(jù)，Beheshti等人[20]擴(kuò)展了應(yīng)用場(chǎng)景以便于能夠?qū)DF數(shù)據(jù)進(jìn)行處理。Cuzzocrea等人[21]研究了如何將云計(jì)算應(yīng)用到大數(shù)據(jù)上以處理大規(guī)模的圖數(shù)據(jù)。

6 總結(jié)

本文針對(duì)現(xiàn)有GraphOLAP對(duì)異質(zhì)網(wǎng)絡(luò)分析能力不足的問(wèn)題，引入關(guān)系元路徑的概念，提出了主節(jié)點(diǎn)引導(dǎo)元路徑聚集，并且設(shè)計(jì)了星型數(shù)據(jù)模型以便于在異質(zhì)網(wǎng)絡(luò)中引入關(guān)系元路徑，在此基礎(chǔ)上提出了同質(zhì)轉(zhuǎn)換操作和屬性轉(zhuǎn)換操作以豐富模型操作。針對(duì)模型提出了優(yōu)先物化二元關(guān)系元路徑的物化策略和維度聚集時(shí)的維度編碼算法來(lái)進(jìn)行join操作的優(yōu)化。最后引入了Spark并行計(jì)算框架，使得模型處理大規(guī)模的圖數(shù)據(jù)的能力大大加強(qiáng)。通過(guò)真實(shí)數(shù)據(jù)與模擬數(shù)據(jù)的實(shí)驗(yàn)，驗(yàn)證了本文模型框架的有效性與高效性。

[1]Cohen J.Graph twiddling in a MapReduce world[J].Computing in Science&Engineering,2009,11(4):29-41.

[2]Li Chuan,Yu P S,Zhao Lei,et al.Infonetolaper:integrating InfoNetWarehouse and InfoNetCube with InfoNetOLAP[J].Proceedings of the VLDB Endowment,2011,4(12):1422-1425.

[3]Wang Huiju,Qin Xiongpai,Wang Shan,et al.Scalable OLAP queries processing towards large cluster[J].Chinese Journal of Computers,2015,38(1):45-58.

[4]Wu Wei.Complex network virtualization and link OLAP[D].Beijing:Beijing University of Posts and Telecommunications,2007.

[5]Chen Chen,Yan Xifeng,Zhu Feida,et al.Graph OLAP:towards online analytical processing on graphs[C]//Proceedings of the 8th International Conference on Data Mining,Pisa,Italy,Dec 15-19,2008.Washington:IEEE Computer Society,2008:103-112.

[6]Li Chuan,Zhao Lei,Tang Changjie,et al.Modeling,design and implementation of Graph OLAPing[J].Journal of Software,2011,22(2):258-268.

[7]Zhao Peixiang,Li Xiaolei,Xin Dong,et al.Graph Cube:on warehousing and OLAP multidimensional networks[C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data,Athens,Greece,Jun 12-16,2011.New York:ACM,2011:853-864.

[8]Yin Mu,Wu Bin,Zeng Zengfeng.HMGraph OLAP:a novel framework for multi-dimensional heterogeneous network analysis[C]//Proceedings of the 15th International Workshop on Data Warehousing and OLAP,Maui,USA,Nov 2,2012.New York:ACM,2012:137-144.

[9]Denis B,Ghrab A,Skhiri S.A distributed approach for graphoriented multidimensional analysis[C]//Proceedings of the 2013 International Conference on Big Data,Santa Clara,USA,Oct 6-9,2013.Piscataway,USA:IEEE,2013:9-16.

[10]Wang Zhengkui,Fan Qi,Wang Huiju,et al.Pagrol:parallel graph OLAP over large-scale attributed graphs[C]//Proceedings of the 30th International Conference on Data Engineering,Chicago,USA,Mar 31-Apr 4,2014.Washington:IEEE Computer Society,2014:496-507.

[11]Wang Pengsen,Wu Bin,Wang Bai.TSMH Graph Cube:a novel framework for large scale multi-dimensional network analysis[C]//Proceedings of the 2015 International Conference on Data Science and Advanced Analytics,Paris,France,Oct 19-21,2015.Piscataway,USA:IEEE,2015:1-10.

[12]Hannachi L,Benblidia N,Bentayeb F,et al.Social microblogging cube[C]//Proceedings of the 16th International Workshop on Data Warehousing and OLAP,San Francisco,USA,Oct 28,2013.New York:ACM,2013:19-26.

[13]Rehman N U,Weiler A,Scholl M H.OLAPing social media:the case of Twitter[C]//Proceedings of the 2013 International Conference on Advances in Social Networks Analysis and Mining,Niagara,Canada,Aug 25-29,2013.New York:ACM,2013:1139-1146.

[14]Liu Xiong,Tang Kaizhi,Hancock J,et al.A text cube approach to human,social and cultural behavior in the Twitter stream[C]//LNCS 7812:Proceedings of the 6th International Conference on Social Computing,Behavioral-Cultural Modeling,and Prediction,Washington,Apr 2-5,2013.Berlin,Heidel-berg:Springer,2013:321-330.

[15]Qu Qiang,Zhu Feida,Yan Xifeng,et al.Efficient topological OLAP on information networks[C]//LNCS 6587:Proceedings of the 16th International Conference on Database Systems for Advanced Applications,Hong Kong,China,Apr 22-25,2011.Berlin,Heidelberg:Springer,2011:389-403.

[16]Jakawat W,Favre C,Loudcher S.OLAP on information networks:a new framework for dealing with bibliographic data[J].Advances in Intelligent Systems&Computing,2013,241:361-370.

[17]Sun Yizhou,Han Jiawei,Yan Xifeng,et al.Mining knowledge from interconnected data:a heterogeneous information network analysis approach[J].Proceedings of the VLDB Endowment,2012,5(12):2022-2023.

[18]Shi Chuan,Kong Xiangnan,Yu P S,et al.Relevance search in heterogeneous networks[C]//Proceedings of the 15th International Conference on Extending Database Technology,Berlin,Germany,Mar 27-30,2012.New York:ACM,2012:180-191.

[19]Junghanns M,Petermann A,Gómez K,et al.GRADOOP:scalable graph data management and analytics with Hadoop[J].arXiv:1506.00548,2015.

[20]Beheshti S M R,Benatallah B,Motahari-Nezhad H R.Scalable graph-based OLAP analytics over process execution data[J].Distributed&Parallel Databases,2016,34(3):379-423.

[21]Cuzzocrea A,Moussa R,Xu Guandong,et al.Cloud-based OLAP over big data:application scenarios and performance analysis[C]//Proceedings of the 15th International Symposium on Cluster,Cloud and Grid Computing,Shenzhen,China,May 4-7,2015.Washington:IEEE Computer Society,2015:921-927.

附中文參考文獻(xiàn)：

[3]王會(huì)舉,覃雄派,王珊,等.面向大規(guī)模機(jī)群的可擴(kuò)展OLAP查詢(xún)技術(shù)[J].計(jì)算機(jī)學(xué)報(bào),2015,38(1):45-58.

[4]吳巍.復(fù)雜網(wǎng)絡(luò)可視化與Link OLAP[D].北京:北京郵電大學(xué),2007.

[6]李川,趙磊,唐常杰,等.Graph OLAPing的建模、設(shè)計(jì)與實(shí)現(xiàn)[J].軟件學(xué)報(bào),2011,22(2):258-268.

Research and Implementation of Framework for Large-Scale Multi-Dimensional NetworkAnalysis*

WANG Ze'ao+,WU Bin,WU Xinyu,ZHANG Zixing

College of Computer Science,Beijing University of Posts and Telecommunications,Beijing 100080,China

2016-09,Accepted 2016-11.

With the rapid development of the Internet and the increasing of computer applications,a large number of graph data especially social networks are generated.Multi-dimensional information networks have become a common way to represent these data.However in the multi-dimensional information networks there are multiple types of nodes and attributes.How to process the analysis of multi-view and multi-granularity and mine the hidden information has become the focus of current research.Graph online analytical processing(GraphOLAP)can process a quick online analysis and query operation of graph data.With the existing achievement of GraphOLAP,this paper proposes a new Graph-Cube framework according to the characteristics of multi-dimensional information network.This paper introduces the concept of meta-path and uses main node to guide the aggregation of the meta-path.Then this paper uses meta-path to guide the roll-up/drill-down operation of the network and proposes attributes transform and homogeneous transform operation of the Graph-Cube.Finally,this paper discusses the materialization strategy and implements the framework in Spark.The experimental results on real and simulation datasets prove the efficiency and effectiveness of the proposed framework.

GraphOLAP;Graph-Cube;meta-path;Spark

+Corresponding author:E-mail:tytyal@163.com

10.3778/j.issn.1673-9418.1609012

*The National Natural Science Foundation of China under Grant No.71231002(國(guó)家自然科學(xué)基金);the Special Fund for Beijing Common Construction Project(北京市共建項(xiàng)目專(zhuān)項(xiàng)).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-11-11,http://www.cnki.net/kcms/detail/11.5602.TP.20161111.1627.002.html

WANG Ze'ao,WU Bin,WU Xinyu,et al.Research and implementation of framework for large-scale multidimensional network analysis.Journal of Frontiers of Computer Science and Technology,2017,11(12)：1941-1952.

A

TP399

WANG Ze'ao was born in 1993.He is an M.S.candidate at Beijing University of Posts and Telecommunications.His research interests include data mining and social network analysis,etc.

王澤奧（1993—），男，四川安岳人，北京郵電大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，社會(huì)網(wǎng)絡(luò)分析等。

WU Bin was born in 1969.He is a professor and Ph.D.supervisor at Beijing University of Posts and Telecommunications.His research interests include data mining and complex network,etc.

吳斌（1969—），男，湖南長(zhǎng)沙人，博士，北京郵電大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，復(fù)雜網(wǎng)絡(luò)等。

WU Xinyu was born in 1993.He is an M.S.candidate at Beijing University of Posts and Telecommunications.His research interests include data mining and social network analysis,etc.

吳心宇（1993—），男，福建莆田人，北京郵電大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，社會(huì)網(wǎng)絡(luò)分析等。

ZHANG Zixing was born in 1994.He is an M.S.candidate at Beijing University of Posts and Telecommunications.His research interests include data mining and social network analysis,etc.

張子興（1994—），男，河北遵化人，北京郵電大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，社會(huì)網(wǎng)絡(luò)分析等。