張 陶，于 炯，廖 彬，畢雪華

1.新疆大學(xué) 信息科學(xué)與工程學(xué)院，烏魯木齊 830046

2.新疆醫(yī)科大學(xué) 醫(yī)學(xué)工程技術(shù)學(xué)院，烏魯木齊 830011

3.新疆財(cái)經(jīng)大學(xué) 統(tǒng)計(jì)與信息學(xué)院，烏魯木齊 830012

圖是一種能夠表現(xiàn)實(shí)體及其之間復(fù)雜關(guān)系的模型。許多領(lǐng)域如Web網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、傳球網(wǎng)絡(luò)[1]等，都可以用圖數(shù)據(jù)結(jié)構(gòu)進(jìn)行描述，采用基于圖數(shù)據(jù)的方法進(jìn)行處理。然而，隨著時(shí)間的推移，圖變得越來(lái)越大，例如截止2017 年10 月，F(xiàn)acebook 的常規(guī)移動(dòng)用戶達(dá)到20 億[2]。如何從這些具有上億節(jié)點(diǎn)和千億條邊的大規(guī)模圖數(shù)據(jù)中找到和分析用戶所需要的信息，是一個(gè)極具挑戰(zhàn)性的難題。因?yàn)閷⑷绱舜笠?guī)模的圖直接加載內(nèi)存，不僅耗費(fèi)大量資源，而且導(dǎo)致可視化視圖非?；靵y。圖概要（圖聚集）技術(shù)是大圖內(nèi)存處理的一種有效的方法。它將一個(gè)大規(guī)模圖概要成一個(gè)簡(jiǎn)潔且能夠反映原始圖結(jié)構(gòu)和屬性信息的小規(guī)模圖（被稱(chēng)為“概要圖”或“摘要圖”）。概要圖代替原始大圖進(jìn)行數(shù)據(jù)分析，幫助用戶理解和分析原始圖中的有用信息。如圖1所示，圖1（右）是圖1（左）的一個(gè)摘要結(jié)果。顯然圖1（右）較圖1（左）更容易分析和理解。超點(diǎn)V4、V5，因?yàn)槔锩娴墓?jié)點(diǎn)屬性不相似，被劃分到不同超點(diǎn)中。若為了結(jié)構(gòu)更緊湊，可繼續(xù)合并超點(diǎn)V4、V5為超點(diǎn)V6。

圖1 由原始圖產(chǎn)生的摘要圖Fig.1 Summary graphs generated from original graphs

實(shí)際應(yīng)用中圖數(shù)據(jù)往往擁有大量信息，除了用節(jié)點(diǎn)來(lái)表示實(shí)體、邊表示實(shí)體之間的關(guān)系之外，還有大量的屬性信息伴隨著節(jié)點(diǎn)和邊出現(xiàn)。這種圖稱(chēng)為屬性圖。節(jié)點(diǎn)的屬性信息是非常重要的，例如在社交網(wǎng)絡(luò)、合作網(wǎng)絡(luò)等圖應(yīng)用領(lǐng)域中頂點(diǎn)所代表的實(shí)體都帶有某些語(yǔ)義的屬性，而語(yǔ)義的含義是不可忽視的。此種情形下，同時(shí)利用結(jié)構(gòu)信息和屬性信息意味著會(huì)得到更加準(zhǔn)確和有意義的分析結(jié)果，使聚集圖具有更全面的原始圖信息。但這也為屬性圖概要研究帶來(lái)了許多挑戰(zhàn)，如結(jié)構(gòu)信息和屬性信息在語(yǔ)義上是相互獨(dú)立的實(shí)體，如何能夠同時(shí)考慮到節(jié)點(diǎn)屬性和結(jié)構(gòu)信息[2]，實(shí)際應(yīng)用中，當(dāng)圖中節(jié)點(diǎn)附加有多個(gè)屬性，且屬性維度具有多種表現(xiàn)形式，如離散值、連續(xù)變量、字符串等時(shí)，那么屬性值距離的度量方式也會(huì)不一樣。如何確立統(tǒng)一的屬性相似性度量公式是需解決的問(wèn)題之一。本文通過(guò)對(duì)屬性圖概要問(wèn)題進(jìn)行分析和建模，結(jié)合最小描述長(zhǎng)度原則（Minimum Description Length，MDL），提出了兩種多屬性圖概要方法（Greedy algorithm-based Multi-Attributed Graph Summarization，Greedy-MAGS）和（Random algorithmbased Multi-Attributed Graph Summarization，Random-MAGS）。

本文所做工作如下：

（1）基于MDL 原則，對(duì)屬性圖概要問(wèn)題進(jìn)行分析建模。

（2）借鑒Levenshtein Distance 思想，本文提出了一種計(jì)算節(jié)點(diǎn)屬性相似性的方法。該屬性度量方法對(duì)節(jié)點(diǎn)屬性的限制較小，不要求節(jié)點(diǎn)屬性的距離或表現(xiàn)形式是一致的，節(jié)點(diǎn)的屬性可以是不同形式，不同的類(lèi)型。并且將節(jié)點(diǎn)間的相似性統(tǒng)一為存儲(chǔ)代價(jià)，實(shí)現(xiàn)了節(jié)點(diǎn)結(jié)構(gòu)相似和屬性相似的協(xié)同考慮。

（3）提出了兩種屬性圖概要算法：貪心算法Greedy-MAGS，追求全局最優(yōu)，每次選擇圖中最佳的節(jié)點(diǎn)對(duì)進(jìn)行合并，最后輸出一個(gè)高度壓縮的概要圖；隨機(jī)算法Random-MAGS，不追求全局最優(yōu)，而是隨機(jī)選擇一個(gè)節(jié)點(diǎn)，將其與其附近的最佳節(jié)點(diǎn)合并。此算法提高了生成概要圖的速度，可以更好地適應(yīng)更大原始圖的圖概要需求。

（5）通過(guò)在真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集上實(shí)驗(yàn)，表明了本文所提算法的有效性。

1 相關(guān)工作

圖概要研究的目的是減少大型圖的結(jié)構(gòu)復(fù)雜度和描述長(zhǎng)度，通過(guò)壓縮、總結(jié)原始圖，來(lái)創(chuàng)建一個(gè)有意義的摘要圖，它近似地保留了底層圖的結(jié)構(gòu)特性。目前的研究可以根據(jù)原始圖類(lèi)型的不同分為僅結(jié)構(gòu)圖[3-9]、屬性圖[10-17]或動(dòng)態(tài)圖[18-19]的總結(jié)。綜述可在[20-23]中找到，以便全面了解。圖概要的算法采用的主要核心技術(shù)分類(lèi)如表1所示。

表1 圖概要算法的核心技術(shù)分類(lèi)Table 1 Technical classification of graph summarization algorithm

文獻(xiàn)[3-5]基于鄰接節(jié)點(diǎn)一致性，使得同一分組內(nèi)部各節(jié)點(diǎn)具有相同的鄰接節(jié)點(diǎn)。Tian 等人[13]基于每個(gè)聚類(lèi)中的節(jié)點(diǎn)屬性一致原則，根據(jù)節(jié)點(diǎn)的屬性對(duì)屬性圖進(jìn)行聚類(lèi)（k-SNAP）。該算法將屬性完全相同的點(diǎn)聚到一組，通過(guò)允許用戶下鉆和上取，實(shí)現(xiàn)了OLAP 形式的多粒度的圖聚。但這些算法都僅僅是考慮節(jié)點(diǎn)結(jié)構(gòu)或?qū)傩詥畏矫娴男畔?，這樣往往會(huì)造成某些分組中的屬性或者節(jié)點(diǎn)結(jié)構(gòu)聯(lián)系非常松散。

而絕大部分方法考慮屬性相似性的方法一般先考慮屬性相似，然后根據(jù)結(jié)構(gòu)相似性進(jìn)行聚合摘要，不能實(shí)現(xiàn)結(jié)構(gòu)和屬性的協(xié)同考慮，如文獻(xiàn)[10，12-14]；或者要求同一維度屬性的距離或表現(xiàn)形式是一樣的，工整的。

尹丹等人[10]研究了屬性圖的聚集方法，該算法將整個(gè)聚集過(guò)程分為了兩個(gè)階段，首先根據(jù)節(jié)點(diǎn)屬性的Jaccard相似性將節(jié)點(diǎn)劃分為M≤k個(gè)分組，然后根據(jù)邊的分布，選取節(jié)點(diǎn)，不斷迭代劃分至k個(gè)分組。此算法需預(yù)先設(shè)定超點(diǎn)的數(shù)量k，當(dāng)用戶對(duì)數(shù)據(jù)沒(méi)有充分了解時(shí)，無(wú)法生成高質(zhì)量的概要圖。

Navlakha 等人[4]提出了一種利用MDL 原則進(jìn)行圖概要的方法，該算法既壓縮了原始圖，又產(chǎn)生了高層次抽象的概要圖，此方法奠定了基礎(chǔ)。但他們僅考慮了節(jié)點(diǎn)的結(jié)構(gòu)相似性，未考慮屬性相似性。當(dāng)輸入圖中的節(jié)點(diǎn)附加屬性時(shí)，它極可能合并具有高鄰域相似性但屬性不相似的節(jié)點(diǎn)。

Khan 等人[15-16]將MDL 與局部敏感哈希（Locality Sensitive Hashing，LSH）相結(jié)合，提出了一種基于集合的相似散列的總結(jié)方法。

本文借鑒了文獻(xiàn)[4]將MDL 原則應(yīng)用于圖概要，可以實(shí)現(xiàn)圖壓縮和圖概要雙重目標(biāo)的思路，改進(jìn)了其衡量節(jié)點(diǎn)相似度的代價(jià)計(jì)算模型，同時(shí)考慮節(jié)點(diǎn)的結(jié)構(gòu)相似性和屬性相似性這兩個(gè)信息來(lái)生成候選的相似節(jié)點(diǎn)，以解決屬性圖概要的問(wèn)題。

2 問(wèn)題描述

在本章中，定義了本文中的各種關(guān)鍵概念以及陳述問(wèn)題。

2.1 基本概念及定義

定義1原始圖G。

設(shè)摘要前的屬性圖G=(V,E,A)為原始圖，其中V={v1,v2,…,vn} 表示節(jié)點(diǎn)集合；E={(vi,vj)|vi,vj∈V且i≠j}表示邊的集合；A={a1,a2,…,ak} 表示節(jié)點(diǎn)的k維屬性的集合，每個(gè)節(jié)點(diǎn)vi∈V的屬性可以表示為屬性向量attri(vi)=[a1(vi),a2(vi),…,ak(vi)]。

定義2概要圖GS。

G中的每個(gè)節(jié)點(diǎn)都分到唯一超級(jí)節(jié)點(diǎn)，形成一個(gè)節(jié)點(diǎn)分組，原始圖G關(guān)于此節(jié)點(diǎn)分組的概要圖為GS=(VS,ES,AS)。注意VS中的節(jié)點(diǎn)形成了不相交的節(jié)點(diǎn)子集，這些節(jié)點(diǎn)的聯(lián)合覆蓋了點(diǎn)集合V。

定義3圖的最小描述代價(jià)表示GMDL。

最小描述長(zhǎng)度MDL原則[24]是由Rissanen于1978年提出的一種信息論原理。MDL原理指出當(dāng)描述數(shù)據(jù)的總描述長(zhǎng)度（代價(jià)）最小時(shí)的模型就是最佳的模型。數(shù)據(jù)的總描述代價(jià)由兩部分組成：模型的大小和模型編碼的大小。在圖概要中，數(shù)據(jù)是原始圖G，模型是概要圖GS，而模型編碼就是邊和屬性修正列表C（修正列表C是在摘要過(guò)程中添加或刪除的邊，以及節(jié)點(diǎn)的屬性修正值，主要用于重構(gòu)原始圖）。當(dāng)圖表示(GS,C)是原始圖的最小描述代價(jià)表示時(shí)，那么MDL 原則認(rèn)為GS就是“最佳”的圖摘要結(jié)果。也就是說(shuō)，GS既是原始圖G的最壓縮表示，同時(shí)也是其最好的摘要圖。最小代價(jià)圖表示(GS,C)被稱(chēng)為圖G的最小描述代價(jià)表示GMDL。

GMDL由兩部分組成：GMDL=(GS,C)。第一部分是概要圖GS(VS,ES,AS)（比原始圖G小得多），它捕捉了原始圖中的重要集群和關(guān)系；第二部分是一組修正C，C可細(xì)分為兩部分：邊修正CE——原始圖G的一組邊，它們被標(biāo)注為正(+) 或負(fù)(-) ；和屬性修正CA——一組G中節(jié)點(diǎn)的屬性值，它們被標(biāo)注為插入(+)、刪除(-)或替換(→)。如果有必要，C可以幫助重新創(chuàng)建原始圖，重構(gòu)G中每個(gè)節(jié)點(diǎn)只需要展開(kāi)一個(gè)超級(jí)節(jié)點(diǎn)并讀取C中的相應(yīng)條目。

2.2 問(wèn)題定義

將MDL原則用于圖概要的目的就是找到具有最小修正C且高度緊湊的概要圖GS。

本文研究的圖概要問(wèn)題的形式化定義如下：

即給出一個(gè)靜態(tài)無(wú)向?qū)傩詧DG，圖中每個(gè)節(jié)點(diǎn)都有多個(gè)屬性，目標(biāo)是通過(guò)對(duì)具有公共鄰居且屬性相同或相似的節(jié)點(diǎn)進(jìn)行合并壓縮，求解出圖G的最小代價(jià)MDL表示GMDL=(GS,C)。圖2顯示屬性圖概要的結(jié)果示例。

圖2 屬性圖概要示例Fig.2 Example of attributed graph summarization

輸入：G(V,E,A)

輸出：GMDL=(GS(VS,ES,AS),C=CE+CA)

如果給出一組超級(jí)節(jié)點(diǎn)VS，通過(guò)查看每個(gè)超級(jí)節(jié)點(diǎn)，根據(jù)創(chuàng)建超邊及修正的規(guī)則進(jìn)行簡(jiǎn)單選擇就可以計(jì)算出最小的表示代價(jià)cost(GMDL)，然而，如何為GMDL找到最佳的超級(jí)節(jié)點(diǎn)集才是主要的挑戰(zhàn)，它是將在第3章中要解決的一個(gè)困難問(wèn)題。在第3 章中描述了關(guān)于代價(jià)模型和求解最小代價(jià)表示的算法的詳細(xì)說(shuō)明。

3 多屬性圖概要方法

在本章中，首先介紹了多屬性圖MDL 表示代價(jià)模型，然后給出了尋找原始圖G的MDL 表示GMDL=(GS,C)的兩種算法。

GMDL=(GS,C)的描述代價(jià)取決于GS和C的代價(jià)之和，即cost(GMDL)=|GS|+|C|。|GS|與模型的大小對(duì)應(yīng)，|C|對(duì)應(yīng)模型編碼的大小。與超邊集ES、屬性集AS和C的存儲(chǔ)代價(jià)相比，將節(jié)點(diǎn)分組Av映射為超級(jí)節(jié)點(diǎn)v∈Vs的存儲(chǔ)代價(jià)通常要小得多，因此忽略了它。最小描述代價(jià)表示GMDL的代價(jià)計(jì)算公式為cost(GMDL)=|ES|+|AS|+|CE|+|CA|。

3.1 代價(jià)模型

鄰接和屬性列表在語(yǔ)義上是兩個(gè)獨(dú)立的實(shí)體。為了能同時(shí)考慮節(jié)點(diǎn)結(jié)構(gòu)相似性和屬性相似性，將其統(tǒng)一為存儲(chǔ)代價(jià)來(lái)衡量。提出的代價(jià)模型分為結(jié)構(gòu)存儲(chǔ)代價(jià)和屬性存儲(chǔ)代價(jià)兩部分。節(jié)點(diǎn)的相似性越高，合并后的存儲(chǔ)代價(jià)越小。

定義4結(jié)構(gòu)代價(jià)CostE。

在圖中，鄰域相似性是一種廣泛使用的方法。通常，合并共享公共鄰居的任何兩個(gè)節(jié)點(diǎn)都可以降低成本，而更多的公共鄰居通常意味著更高的成本降低。

公式（1）[2]計(jì)算了總結(jié)的結(jié)構(gòu)代價(jià)，它是創(chuàng)建超級(jí)節(jié)點(diǎn)時(shí)的邊數(shù)和邊修正數(shù)之和。其中，Nu是超級(jí)節(jié)點(diǎn)u∈VS的鄰居集合。

當(dāng)原始圖中的節(jié)點(diǎn)帶有屬性時(shí)，如果僅考慮結(jié)構(gòu)相似性，減少了聚集圖的信息量，則很有可能將具有高鄰域相似性但具有不同屬性相似性的節(jié)點(diǎn)合并起來(lái)，使聚集圖的質(zhì)量下降。為了克服這個(gè)缺陷，最好同時(shí)考慮候選相似節(jié)點(diǎn)對(duì)的結(jié)構(gòu)信息及屬性信息。

定義5屬性代價(jià)CostA。

圖中的每個(gè)節(jié)點(diǎn)都有多個(gè)屬性，這些屬性都是該節(jié)點(diǎn)的某些方面的特征信息，屬性取值可能是離散型的（如布爾值），可能是連續(xù)型的，也可能是文本型的。如社交網(wǎng)絡(luò)中的用戶，不僅具有性別、年齡屬性，還具有興趣愛(ài)好等復(fù)雜屬性。屬性維度間不一樣的表現(xiàn)形式會(huì)導(dǎo)致一樣的相似性度量方式。有的文獻(xiàn)是將屬性轉(zhuǎn)化為屬性值矩陣，用0/1表示屬性是否存在；有的方法是將屬性值轉(zhuǎn)化為集合的形式，然后使用距離度量函數(shù)（比如Jaccard相似度）衡量其相似性；也有方法將屬性值映射到具體數(shù)值上，例如局部敏感哈希（Local Sensitive Hash）方法、SimHash 算法。但上述方法都需要節(jié)點(diǎn)屬性的距離或表現(xiàn)形式是一樣的，工整的。在實(shí)際的應(yīng)用中圖中節(jié)點(diǎn)的屬性具有多樣性，不同屬性維度的距離往往是不一樣的。針對(duì)這個(gè)弊端，本文提出了一種統(tǒng)一的屬性相似性方法。本文借鑒了字符串相似性算法Levenshtein Distance的思想，來(lái)衡量節(jié)點(diǎn)屬性的相似，該方法對(duì)節(jié)點(diǎn)屬性的限制較小，節(jié)點(diǎn)的屬性可以是不同形式、不同的類(lèi)型，并將其轉(zhuǎn)為屬性存儲(chǔ)代價(jià)，與結(jié)構(gòu)代價(jià)相統(tǒng)一。

編輯距離（Edit Distance），是由1956年俄國(guó)科學(xué)家Vladimir Levenshtein給字符串相似度提出的定義，又稱(chēng)Levenshtein距離。是指兩個(gè)字符串之間，由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯操作次數(shù)。許可的編輯操作包括將一個(gè)字符替換成另一個(gè)字符，插入一個(gè)字符，刪除一個(gè)字符。例如從aware 到award 需要一步（一次替換），從has 到have 則需要兩步（替換s 為v 和再加上e）。字符越相似，編輯操作則越少。若兩個(gè)字符串等長(zhǎng)時(shí)，編輯距離即為漢明距離。

本文受上述思想的啟發(fā)，提出了用屬性編輯距離（Attributed Edit Distance，AED）來(lái)計(jì)算節(jié)點(diǎn)屬性相似度。此方法將每個(gè)節(jié)點(diǎn)的屬性分布看作是字符串，其中的每個(gè)屬性維度值則類(lèi)似于一個(gè)字符。

公式（2）是節(jié)點(diǎn)間的屬性編輯距離，距離值越小，屬性分布越相似，編輯操作則越少。產(chǎn)生的編輯操作列表作為屬性修正，加入CE。

公式（3）計(jì)算了總結(jié)的屬性代價(jià)，它是創(chuàng)建超級(jí)節(jié)點(diǎn)時(shí)的屬性維度個(gè)數(shù)和屬性修正數(shù)之和。au(i)表示節(jié)點(diǎn)u第i維屬性值，k是節(jié)點(diǎn)的屬性維度個(gè)數(shù)。

如圖3所示，以某社交網(wǎng)絡(luò)精簡(jiǎn)的屬性分布為例說(shuō)明本文屬性相似度計(jì)算方法。每行代表一個(gè)用戶節(jié)點(diǎn)v1～v5，列表示其屬性（4 個(gè)屬性維度A、B、C、D）。A的屬性域?yàn)橐粋€(gè)0～1分布；B的屬性域是數(shù)值類(lèi)型的連續(xù)變量；C的屬性域包含三種取值：a、b、c；D的屬性域是一個(gè)集合，代表用戶的興趣愛(ài)好，比如音樂(lè)music或者閱讀reading等。編輯操作列表是每個(gè)節(jié)點(diǎn)屬性變?yōu)槟骋粚傩苑植妓璧淖钌倬庉嫴僮?。假設(shè)節(jié)點(diǎn)v1與節(jié)點(diǎn)v2～v5具有完全相同的鄰居節(jié)點(diǎn)，此時(shí)僅考慮它們的屬性相似性。其中，節(jié)點(diǎn)v2具有與v1完全相同的屬性分布，因此不產(chǎn)生編輯操作，是v1最佳的合并節(jié)點(diǎn)。而節(jié)點(diǎn)v5與v1屬性完全不同，因此將產(chǎn)生4 個(gè)編輯操作。節(jié)點(diǎn)的屬性越相似，則產(chǎn)生的編輯操作越少，屬性代價(jià)越小。

圖3 節(jié)點(diǎn)屬性相似度計(jì)算示例Fig.3 Example of computing attribute similarity of node

對(duì)于節(jié)點(diǎn)集v1～v5，A屬性維度是（0，0，1，0，1），A維度下重復(fù)出現(xiàn)次數(shù)最多的屬性值（即最大頻率屬性值）是0。當(dāng)將每個(gè)節(jié)點(diǎn)的A 維屬性都變?yōu)樽畲箢l率屬性值0，將產(chǎn)生最少的編輯操作次數(shù)（2 個(gè)）。按照屬性值的出現(xiàn)頻率節(jié)點(diǎn)集v1～v54 個(gè)屬性維度下的最大頻率屬性分布為(0,10,a,Music)，可得節(jié)點(diǎn)v1～v5變?yōu)榇藢傩苑植妓a(chǎn)生的編輯操作之和是最小的，因此得到的屬性修正是最小。因此，在圖概要過(guò)程中，為了產(chǎn)生最少的編輯操作，生成最小的屬性修正列表CE，將合并后超級(jí)節(jié)點(diǎn)的屬性設(shè)置為最大頻率屬性分布的值。

定義6總代價(jià)Cost(u,v)。

公式（4）計(jì)算了總結(jié)的總代價(jià)，通過(guò)參數(shù)β∈[0,1]調(diào)整兩種代價(jià)的權(quán)重。β越大表示結(jié)構(gòu)代價(jià)的權(quán)重越大，合并更側(cè)重于結(jié)構(gòu)的相似性。

定義7代價(jià)降低比率s(u,v)。

在一個(gè)大圖中，通過(guò)合并許多節(jié)點(diǎn)對(duì)可以降低圖的存儲(chǔ)代價(jià)。通常，任何兩個(gè)具有相似結(jié)構(gòu)和屬性的節(jié)點(diǎn)合并就可以降低存儲(chǔ)代價(jià)，比如兩個(gè)節(jié)點(diǎn)擁有共同的鄰居節(jié)點(diǎn)且屬性值也相同，就可以將它們折疊成一個(gè)超級(jí)節(jié)點(diǎn)，用單個(gè)超邊替換到每個(gè)公共鄰居的兩條邊。顯然，這將大大減少需要存儲(chǔ)的總邊數(shù)，同時(shí)節(jié)點(diǎn)屬性的存儲(chǔ)空間也會(huì)降低50%，從而大大降低了內(nèi)存需求。而擁有更多共同鄰居和相似屬性的節(jié)點(diǎn)通常意味著更高的成本降低。在此基礎(chǔ)上，定義了合并節(jié)點(diǎn)對(duì)(u,v)后的代價(jià)降低比率s(u,v)，如公式（5）。s(u,v)被定義為合并節(jié)點(diǎn)u和v（形成一個(gè)新的超節(jié)點(diǎn)w）帶來(lái)的存儲(chǔ)代價(jià)降低值和合并節(jié)點(diǎn)u和v前存儲(chǔ)總代價(jià)的比值。只要有利于存儲(chǔ)代價(jià)降低的點(diǎn)合并都會(huì)進(jìn)行，只是會(huì)根據(jù)s(u,v)值的大小調(diào)整其被合并的順序。在貪心算法中，迭代地將圖中具有對(duì)s(u,v)的最大值的節(jié)點(diǎn)對(duì)合并。算法的核心思想是選擇具有最大共同鄰居數(shù)及屬性相似的節(jié)點(diǎn)對(duì)進(jìn)行合并，以創(chuàng)建將s(u,v)降低到最大值的超級(jí)節(jié)點(diǎn)。隨著算法的發(fā)展，維護(hù)了一組超級(jí)節(jié)點(diǎn)VS，它們構(gòu)成了圖概要中的超級(jí)節(jié)點(diǎn)。

當(dāng)兩個(gè)節(jié)點(diǎn)具有完全相同的鄰接列表和屬性列表時(shí)，則被認(rèn)為是完全等價(jià)的節(jié)點(diǎn)，合并它們，s(u,v)可以取到最大值0.5。當(dāng)節(jié)點(diǎn)u,v的屬性完全不同時(shí)，屬性編碼代價(jià)的降低為0。

下面詳細(xì)描述用于尋找原始圖G的MDL 表示GMDL=(GS,C)的兩種算法。

3.2 貪心算法

貪心算法Greedy-MAGS算法迭代地將最大代價(jià)降低（全局最優(yōu)）的節(jié)點(diǎn)對(duì)合并成超級(jí)節(jié)點(diǎn)。為了有效地選擇s(·)值最大的節(jié)點(diǎn)對(duì)，使用標(biāo)準(zhǔn)的max-heap結(jié)構(gòu)H來(lái)存儲(chǔ)s(u,v)大于0的圖中的所有節(jié)點(diǎn)對(duì)。

算法1Greedy-MAGS算法

此算法分為三個(gè)階段進(jìn)行：第一階段初始化（第1～7行）：此階段任務(wù)是采用時(shí)間復(fù)雜度最優(yōu)的堆排序?qū)⑺泻蜻x合并節(jié)點(diǎn)對(duì)按照其s(?)值排序。步驟如下：首先遍歷超點(diǎn)集VS中所有2 跳節(jié)點(diǎn)對(duì)，并計(jì)算它們的s(?)值。之所以只考慮相隔2跳的節(jié)點(diǎn)對(duì)，是因?yàn)橛^察到兩個(gè)沒(méi)有共同鄰居的節(jié)點(diǎn)合并不可能降低結(jié)構(gòu)存儲(chǔ)代價(jià)，只有合并擁有公共鄰居節(jié)點(diǎn)的節(jié)點(diǎn)對(duì)才能降低結(jié)構(gòu)存儲(chǔ)代價(jià)。而相隔2 跳的節(jié)點(diǎn)對(duì)之間必然有至少一個(gè)共同鄰居節(jié)點(diǎn)。然后將(s(?)>0)的節(jié)點(diǎn)對(duì)放入一個(gè)最大堆H中進(jìn)行排序。

第二階段迭代合并：依次選擇最大s(?)值的節(jié)點(diǎn)對(duì)進(jìn)行合并，并更新超點(diǎn)集VS和最大堆H。對(duì)于每個(gè)超級(jí)節(jié)點(diǎn)，為了產(chǎn)生更少的屬性修正，通過(guò)從{ }u,v中選擇到最大頻率屬性分布的編輯距離AEDMAX更小的節(jié)點(diǎn)的屬性值來(lái)設(shè)置其屬性（第13～17行）。第23～28行重新計(jì)算了包含節(jié)點(diǎn)x∈Nw的所有對(duì)的s(?)值，并在堆H中更新它們（因?yàn)槌c(diǎn)w的鄰居節(jié)點(diǎn)x，它以前是節(jié)點(diǎn)u或v的鄰居節(jié)點(diǎn)，合并u和v可能會(huì)改變邊(u,x)（和/或(v,x)）的s(?)值）。

結(jié)果輸出階段：第31～41行生成超邊及修正列表C，包含邊修正Ce和屬性修正Ca兩部分。當(dāng)|Auv|>(|Πuv|+1)/2時(shí)，新增邊(u,v)至ES。最后輸出摘要圖GS以及邊和屬性的修正列表集C。

創(chuàng)建超邊及修正時(shí)尋求最小的內(nèi)存需求，只對(duì)高度緊湊的總結(jié)和最少的修正感興趣。具體規(guī)則如下：將Πuv定義為Au,Av∈VS之間所有可能邊的集合，Auv作為Au和Av之間的實(shí)際存在的邊集合。當(dāng)符合|Auv|>(|Πuv|+1)/2 時(shí)，超點(diǎn)間創(chuàng)建超邊(u,v)，并對(duì)Πuv-Auv里的邊創(chuàng)建負(fù)修正，內(nèi)存代價(jià)是(1+|Πuv-Auv|)；否則，不創(chuàng)建超邊，僅對(duì)Auv里的邊創(chuàng)建正修正，內(nèi)存代價(jià)為|Auv|。也就是說(shuō)為了讓圖表示更緊湊、體積更小，只有當(dāng)Au與Av間的節(jié)點(diǎn)密集連接時(shí)，才在超級(jí)節(jié)點(diǎn)u和v之間存儲(chǔ)一條超邊，并且選擇內(nèi)存代價(jià)更小的邊修正方式。

為了產(chǎn)生最少的編輯操作，生成最小的屬性修正列表CE，對(duì)于每個(gè)超級(jí)節(jié)點(diǎn)u，通過(guò)選擇Au中具最大頻率屬性分布的值來(lái)設(shè)置其屬性。其余屬性值作為屬性修正創(chuàng)建。

算法1 時(shí)間復(fù)雜度分析：算法第1 行初始化復(fù)雜度為O(n) ；第2～7 行代碼為堆排序操作，時(shí)間復(fù)雜度為O(n×lbn)，其中n為超點(diǎn)集VS中所有具有正代價(jià)降低率的二跳節(jié)點(diǎn)對(duì)個(gè)數(shù)；8～26 行代碼是while 循環(huán)嵌套if判斷以及for循環(huán)，其中，第9～15每行復(fù)雜度都為O(1)，對(duì)于第一個(gè)for循環(huán)，時(shí)間復(fù)雜度由每個(gè)節(jié)點(diǎn)的度m決定；同樣，23～26 行代碼復(fù)雜度為O(m)；疊加外層while循環(huán)，所以8～26 行代碼復(fù)雜度為O(n×2m)；第30 行的時(shí)間復(fù)雜度為O(n)，31～41 行為for 循環(huán)嵌套兩個(gè)if 判斷，當(dāng)超點(diǎn)集VS里節(jié)點(diǎn)對(duì)個(gè)數(shù)為n時(shí)，每個(gè)if判斷中的代碼最多會(huì)被操作n次；所以，算法1 的時(shí)間復(fù)雜度為O(n+n×lbn+n×2m+n)≈O(n(lbn+m)) 。

3.3 隨機(jī)算法

為了更大輸入圖的圖概要需求，提高生成概要圖的速度，本文又提出了一種生成概要圖更快的策略方法——隨機(jī)算法Random-MAGS算法。Random-MAGS算法不需要堆結(jié)構(gòu)，它不追求全局最優(yōu)，不是合并全局最優(yōu)節(jié)點(diǎn)對(duì)，而是隨機(jī)選取一個(gè)節(jié)點(diǎn)，將其與其附近的最佳節(jié)點(diǎn)合并。因此節(jié)點(diǎn)合并過(guò)程比貪婪算法Greedy-MAGS算法快很多。

算法2Random-MAGS算法

算法2中，算法第1～3行的初始化操作，每行時(shí)間復(fù)雜度為O(n)，第4～18 行是while 循環(huán)嵌套if 判斷，代碼復(fù)雜度為O(n)；所以，結(jié)果輸出階段，與算法1 一樣，代碼復(fù)雜度為O(n)，所以，算法2 的時(shí)間復(fù)雜度為O(2n+1+n+n)≈O(n)。

4 實(shí)驗(yàn)結(jié)果與分析

本章從聚集效果和算法性能兩方面評(píng)估兩種屬性圖聚集算法Greedy-MAGS 和Random-MAGS。實(shí)驗(yàn)數(shù)據(jù)選取了4個(gè)真實(shí)的無(wú)向圖數(shù)據(jù)集D1～D4 和一個(gè)合成數(shù)據(jù)集D5（在數(shù)據(jù)集D4 基礎(chǔ)上，又創(chuàng)建了一維屬性并隨機(jī)生成其屬性值（10個(gè)候選值））。表2給出了每個(gè)數(shù)據(jù)集的具體信息。選取BB-ULSH算法[15]進(jìn)行對(duì)比，BBULSH 算法屬性相似性設(shè)置為50%。實(shí)驗(yàn)環(huán)境是Core i7-8750H 2.20 GHz CPU和16 GB的RAM，所有算法用Java語(yǔ)言實(shí)現(xiàn)。

表2 數(shù)據(jù)集信息Table 2 Dataset information

4.1 聚集效果

使用邊壓縮率和屬性修正代價(jià)來(lái)評(píng)價(jià)屬性圖概要的質(zhì)量。在理想的情況下，摘要圖的屬性修正應(yīng)該和超級(jí)節(jié)點(diǎn)一樣都是最小的。

使用公式（6）計(jì)算邊壓縮率，其中PreviousCost表示原始圖中實(shí)際存在的邊；CurrentCost表示摘要圖中超邊和邊修正之和。超邊和邊修正越少，此結(jié)果值就越大，代表了摘要結(jié)果越好。

如圖4，兩種算法都獲得了較高的壓縮率。這是因?yàn)閮煞N算法都采用了成對(duì)創(chuàng)建超節(jié)點(diǎn)的策略，嚴(yán)格探索查詢每個(gè)節(jié)點(diǎn)的2跳鄰居節(jié)點(diǎn)，保證了合并的每一對(duì)節(jié)點(diǎn)都是最高壓縮比，因此，都實(shí)現(xiàn)了較好的壓縮。

圖4 不同數(shù)據(jù)集下的邊壓縮率對(duì)比（越高越好）Fig.4 Compression rate comparison of different data sets（the higer the better）

4.2 算法性能

圖5 顯示了所有算法的運(yùn)行時(shí)間對(duì)比，BB-ULSH算法的運(yùn)行時(shí)間最短，是因?yàn)樗遣捎没诩蟿?chuàng)建超點(diǎn)的技術(shù)，一次迭代可以遍歷和壓縮多個(gè)節(jié)點(diǎn)；而兩種算法則都是以其迭代的成對(duì)超節(jié)點(diǎn)創(chuàng)建技術(shù)，遍歷查詢每個(gè)節(jié)點(diǎn)的2跳鄰居列表以確定最佳可壓縮節(jié)點(diǎn)，且每個(gè)迭代只壓縮一對(duì)節(jié)點(diǎn)，因此花費(fèi)了更多的時(shí)間，但隨著圖的稀疏性的降低，這兩種算法的執(zhí)行時(shí)間都不斷下降。

圖5 不同數(shù)據(jù)集下的運(yùn)行時(shí)間對(duì)比（越小越好）Fig.5 Runtime comparison of different data sets（the smaller the better）

在D1 數(shù)據(jù)集上幾種算法的運(yùn)行時(shí)間差異不大。而數(shù)據(jù)集D5 上差異較大。這是因?yàn)椴捎贸蓪?duì)創(chuàng)建超節(jié)點(diǎn)技術(shù)的兩種算法運(yùn)行時(shí)間與每個(gè)節(jié)點(diǎn)2跳鄰居列表的大小成正比，而D5 中每個(gè)節(jié)點(diǎn)都有大量的2 跳節(jié)點(diǎn)。因此需要的運(yùn)行時(shí)間更多，其中，與本文的預(yù)測(cè)一致，Greedy-MAGS 算法追求全局結(jié)構(gòu)最緊密屬性最相似，Random-MAGS 算法要明顯快于Greedy-MAGS算法。

4.3 算法參數(shù)分析

本實(shí)驗(yàn)考察了本文兩種算法在不同數(shù)據(jù)規(guī)模數(shù)據(jù)集上在摘要表示代價(jià)和運(yùn)行時(shí)間方面的差異。

圖6結(jié)果所示，采用兩種算法都得到了遠(yuǎn)小于原始圖存儲(chǔ)代價(jià)的摘要圖。Greedy-MAGS算法追求全局最優(yōu)時(shí)間代價(jià)方面明顯大于Random-MAGS算法，但同時(shí)也獲得了存儲(chǔ)代價(jià)更小的摘要圖。

圖6 兩種算法表示成本和運(yùn)行時(shí)間對(duì)比Fig.6 Comparison of representation costs and running times

接下來(lái)，觀察了圖中MDL表示的各部分存儲(chǔ)代價(jià)。如圖7，MDL表示的存儲(chǔ)代價(jià)共有4部分組成：超點(diǎn)（節(jié)點(diǎn)分組）、摘要圖、邊修正和屬性修正。其中邊修正和屬性修正是主要的表示成本，占到80%左右。同時(shí)也觀察到，當(dāng)原始圖屬性維度增加時(shí)(D4 →D5)，屬性修正代價(jià)呈直線上升。除了因?yàn)閷傩跃S度個(gè)數(shù)增加外，新增屬性值是隨機(jī)產(chǎn)生的也是原因之一。

圖7 MDL表示成本（Greedy-MAGS算法）Fig.7 Breakup of cost of representation computed by Greedy-MAGS

整體來(lái)看，相較D5 數(shù)據(jù)集，所有算法在D4 數(shù)據(jù)集都產(chǎn)生了更少的屬性修正。這是因?yàn)檎鎸?shí)的數(shù)據(jù)集節(jié)點(diǎn)屬性通常與節(jié)點(diǎn)鄰居節(jié)點(diǎn)相關(guān)，稱(chēng)之為節(jié)點(diǎn)自然屬性同質(zhì)性的優(yōu)勢(shì)，比如社交網(wǎng)絡(luò)上通常是相同層次的人員之間進(jìn)行互動(dòng)交流，他們具有共同的朋友和興趣品味（屬性）。因此產(chǎn)生較少的屬性修正。D4 數(shù)據(jù)集具有節(jié)點(diǎn)自然屬性同質(zhì)性的優(yōu)勢(shì)。而D5 數(shù)據(jù)集因?yàn)槊總€(gè)節(jié)點(diǎn)有一維屬性值是隨機(jī)生成的，因此屬性值與鄰域之間不協(xié)調(diào)，則產(chǎn)生了更多的屬性修正。

5 結(jié)語(yǔ)

首先，本文對(duì)多屬性圖概要問(wèn)題進(jìn)行了分析，提出了多屬性圖概要問(wèn)題的MDL 模型。其次，提出了計(jì)算節(jié)點(diǎn)屬性相似性方法，將節(jié)點(diǎn)間的相似性統(tǒng)一為存儲(chǔ)代價(jià)，解決了不能同時(shí)考慮節(jié)點(diǎn)屬性相似性和領(lǐng)域相似性這兩個(gè)語(yǔ)義完全不同的實(shí)體的問(wèn)題。然后，提出了兩種多屬性圖概要算法貪心算法Greedy-MAGS和隨機(jī)算法Random-MAGS適應(yīng)不同的圖概要需求。最后，通過(guò)在真實(shí)和合成的數(shù)據(jù)集上實(shí)驗(yàn)分析，證明本文所提能屬性圖概要方法的有效性。下一步工作主要集中在以下幾個(gè)方面：基于MDL 的圖概要方法對(duì)應(yīng)的修正列表占據(jù)的空間消耗較大，幾乎占所有消耗的80%，并且發(fā)現(xiàn)修正列表中存在一些重復(fù)率較高的編輯操作，可針對(duì)這個(gè)進(jìn)行再次壓縮，比如可以使用Huffma 編碼或者串表壓縮（LZW 算法）等算法提取修正列表中的不同編輯操作，基于這些編輯操作創(chuàng)建一個(gè)編譯表，然后用編譯表中的字符的索引來(lái)替代原始修正列表中的相應(yīng)編輯操作，減少進(jìn)一步原始數(shù)據(jù)大小。另外現(xiàn)有算法僅考慮了邊的結(jié)構(gòu)信息，下一步工作多加考慮邊的類(lèi)型以及權(quán)重等信息。