羅曉霞，司豐瑋，羅香玉

(西安科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，西安 710054)(*通信作者電子郵箱676915315@qq.com)

0 引言

圖是一種抽象數(shù)據(jù)結(jié)構(gòu)類(lèi)型，圖的應(yīng)用幾乎涵蓋了所有的領(lǐng)域，如大規(guī)模集成電路設(shè)計(jì)[1]、社交網(wǎng)絡(luò)[2]、煤礦安全、并行計(jì)算過(guò)程中的任務(wù)分配[3-4]等。近年來(lái)，圖數(shù)據(jù)的規(guī)模迅速增長(zhǎng)，據(jù)中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心(China Internet Network Information Center, CNNIC)統(tǒng)計(jì)，2016年Facebook在全球有15億9千萬(wàn)活躍用戶(hù)，并且其用戶(hù)以每年幾乎10%的速度增長(zhǎng)。若將用戶(hù)看作圖的頂點(diǎn)，用戶(hù)與用戶(hù)之間的關(guān)系看作邊，整個(gè)社交網(wǎng)絡(luò)就變成一張巨大的圖。如此龐大的社交網(wǎng)絡(luò)圖，傳統(tǒng)的單機(jī)模式顯然已經(jīng)無(wú)法勝任對(duì)其的處理，因此，分布式大圖處理成為了必然的趨勢(shì)。如何對(duì)大規(guī)模圖進(jìn)行劃分是影響分布式處理效率最基本也是最重要的問(wèn)題之一。

大規(guī)模圖的劃分問(wèn)題已經(jīng)成為國(guó)內(nèi)外的研究熱點(diǎn)[5-7]，許多學(xué)者提出了相關(guān)的解決思路和方法，但是這些方法一般是通過(guò)優(yōu)化規(guī)則迭代式的對(duì)大圖劃分進(jìn)行調(diào)整。這種調(diào)整一方面是基于局部信息進(jìn)行的，對(duì)全局的劃分效果改善是有限的，另一方面需要多次迭代完成，這樣導(dǎo)致時(shí)間開(kāi)銷(xiāo)較大，因此，這些方法并未被業(yè)界主流的分布式圖數(shù)據(jù)處理系統(tǒng)采用。而現(xiàn)有算法難以對(duì)大規(guī)模圖進(jìn)行有效劃分的一個(gè)重要原因是忽略了圖結(jié)構(gòu)對(duì)其劃分效果的影響。例如圖1(a)、(b)均包括8個(gè)頂點(diǎn)和12條邊，但它們顯然具有不同的結(jié)構(gòu)特征。在均衡的二劃分時(shí)，圖1(a)的最優(yōu)劃分有0條交叉邊，而圖1(b)采用何種算法都會(huì)有4條交叉邊。由此可見(jiàn)，圖的結(jié)構(gòu)特征對(duì)劃分效果具有重要影響。

圖1 8個(gè)頂點(diǎn)12條邊不同結(jié)構(gòu)特征

本文首先定義了一種描述大圖結(jié)構(gòu)特征的方法；然后基于真實(shí)的圖數(shù)據(jù)通過(guò)不同結(jié)構(gòu)特征大圖生成算法(Generating Algorithm with Different Structure Features, GADSF)產(chǎn)生若干頂點(diǎn)數(shù)和邊數(shù)相同但結(jié)構(gòu)特征不同的仿真數(shù)據(jù)集；其次通過(guò)結(jié)構(gòu)特征相似度匹配算法找到仿真圖數(shù)據(jù)集與真實(shí)圖之間的關(guān)系，初步證明圖結(jié)構(gòu)特征對(duì)真實(shí)圖結(jié)構(gòu)表達(dá)的有效性；隨后，通過(guò)大圖劃分算法，得到仿真數(shù)據(jù)集與真實(shí)圖數(shù)據(jù)劃分結(jié)果，通過(guò)比對(duì)，進(jìn)一步證明了描述圖結(jié)構(gòu)特征方法的有效性和正確性；最后，通過(guò)對(duì)相同頂點(diǎn)和邊數(shù)但結(jié)構(gòu)特征不同的圖數(shù)據(jù)集進(jìn)行劃分，分析了大圖結(jié)構(gòu)特征與劃分效果之間的關(guān)系。

1 相關(guān)工作

圖劃分問(wèn)題是經(jīng)典的NP完全問(wèn)題[8]，其劃分效果通常綜合用交叉邊個(gè)數(shù)和負(fù)載均衡來(lái)進(jìn)行評(píng)價(jià)。負(fù)載均衡，即劃分之后的子圖規(guī)模應(yīng)大致相同，以便于提高分布式處理效率。若一對(duì)存在邊的頂點(diǎn)被劃分在了不同的子圖中，這條邊就被稱(chēng)為交叉邊。由于頻繁跨子圖訪問(wèn)數(shù)據(jù)會(huì)造成很高的通信代價(jià)，因此，在保證負(fù)載均衡的前提下，以降低網(wǎng)絡(luò)通信開(kāi)銷(xiāo)為目的，交叉邊的數(shù)量要盡可能少。

圖劃分問(wèn)題是20世紀(jì)60年代初期,人們?cè)谠O(shè)計(jì)大規(guī)模集成電路時(shí)將組合優(yōu)化技術(shù)和圖論相結(jié)合所產(chǎn)生的。就是將一個(gè)圖的頂點(diǎn)集分成k個(gè)不相交的子集，且滿(mǎn)足子集之間的某些限制[9]。最初針對(duì)圖的二分問(wèn)題，人們提出基于圖的拉普拉斯矩陣(Laplacian)特性值對(duì)圖進(jìn)行二分，這種方法被稱(chēng)為譜方法。Barnard等[10]于1993年對(duì)譜方法進(jìn)行了改進(jìn)，具體是用遞歸譜平分法(Recursive Spectral Bisection, RSB)有效地減少了算法求解特征向量的執(zhí)行時(shí)間，提高了算法的效率。

人們?yōu)榱颂幚砀笠?guī)模的圖，提出了各類(lèi)啟發(fā)式算法。其中，比較經(jīng)典的是由Kernighan等[11]提出的Kernighan-Lin(KL)算法。該算法的收斂較慢，難以處理大規(guī)模的圖。在KL算法的基礎(chǔ)上，由Fiduccia等[12]提出的Fiduccia-Mattheyses(FM)算法對(duì)KL算法進(jìn)行了改進(jìn)，一定程度上降低了時(shí)間復(fù)雜度，提高了收斂的速度。

隨著不斷的深入研究，國(guó)內(nèi)外的研究者們又將許多智能優(yōu)化算法(例如，遺傳算法[13-14]、禁忌搜索算法[15]、模擬退火算法[16]等)應(yīng)用在圖的劃分問(wèn)題上，能夠處理較大規(guī)模的圖，并且在一定程度上克服了傳統(tǒng)算法的不足；但由于這些算法忽略了圖本身多變且復(fù)雜的結(jié)構(gòu)特性，并沒(méi)有從本質(zhì)上很好地解決大規(guī)模圖的劃分問(wèn)題。

目前也有學(xué)者對(duì)圖的結(jié)構(gòu)性進(jìn)行研究，主要體現(xiàn)在圖譜理論的研究。為了研究圖的性質(zhì),人們引入了各種各樣的矩陣,諸如圖的鄰接矩陣、拉普拉斯矩陣、關(guān)聯(lián)矩陣、距離矩陣等[17]。人們?cè)噲D通過(guò)這些矩陣的特征值性質(zhì)，如譜半徑、譜唯一性、能量來(lái)反映圖的性質(zhì)。例如：Fallat等[18]利用圖的邊密度來(lái)研究圖代數(shù)連通度的上下界；Nikiforov[19]給出了關(guān)于圖鄰接譜半徑的上下界；Liu等[20]研究了具有最大(小)鄰接譜半徑的臨界圖；Kharaghani等[21]給出圖能量的上下界，但目前尚沒(méi)有分析大圖結(jié)構(gòu)對(duì)劃分效果的影響。

2 問(wèn)題描述

本文將大圖結(jié)構(gòu)特征對(duì)劃分效果的影響這一問(wèn)題分解成了三個(gè)子問(wèn)題。首先對(duì)大圖結(jié)構(gòu)特征進(jìn)行描述；其次驗(yàn)證該描述方法的有效性；最后通過(guò)劃分算法驗(yàn)證結(jié)構(gòu)特征與劃分效果之間的關(guān)系。

2.1 大圖結(jié)構(gòu)特征的描述

設(shè)有頂點(diǎn)數(shù)和邊數(shù)相同的兩個(gè)圖，它們的頂點(diǎn)度分布不同，結(jié)構(gòu)特征也不同。如圖2(a)、(b)均包括20個(gè)頂點(diǎn)和60條邊，但前者的頂點(diǎn)度分布較為均衡，而后者較為集中，二者具有不同的結(jié)構(gòu)特征。大圖結(jié)構(gòu)特征實(shí)質(zhì)是該圖頂點(diǎn)度的分布特征，如何描述頂點(diǎn)分布特征是研究的第一個(gè)問(wèn)題。

圖2 20個(gè)頂點(diǎn)60條邊不同結(jié)構(gòu)特征

2.2 結(jié)構(gòu)特征描述方法的有效性

圖2(a)、(b)是在相同頂點(diǎn)數(shù)和邊數(shù)但結(jié)構(gòu)特征不同時(shí)，通過(guò)實(shí)驗(yàn)生成的一組圖數(shù)據(jù)集。然而這樣生成的圖與真實(shí)世界的圖并無(wú)直接聯(lián)系，因此，需用結(jié)構(gòu)特征來(lái)描述現(xiàn)實(shí)世界中存在的真實(shí)的圖，以證明其合理性和有效性。

2.3 大圖結(jié)構(gòu)特征與劃分效果的關(guān)系

在證明結(jié)構(gòu)特征的正確性和有效性的基礎(chǔ)之上，研究大圖結(jié)構(gòu)特征對(duì)劃分效果的影響。在對(duì)圖劃分時(shí)將負(fù)載均衡作為大圖劃分的約束條件，交叉邊數(shù)成為評(píng)價(jià)劃分效果的主要指標(biāo)。

3 結(jié)構(gòu)特征的描述方法

現(xiàn)實(shí)中的大圖是不斷演化生成的，某點(diǎn)的頂點(diǎn)度越大，就越容易和其他頂點(diǎn)之間形成新的邊。為了模擬真實(shí)圖的產(chǎn)生過(guò)程，本章定義了描述結(jié)構(gòu)特征的方法并且設(shè)計(jì)了GADSF。

3.1 結(jié)構(gòu)特征的定義

假設(shè)初始時(shí)，所有頂點(diǎn)與其他頂點(diǎn)產(chǎn)生邊的權(quán)重均為0，即所有頂點(diǎn)之間等概率產(chǎn)生邊；當(dāng)產(chǎn)生一條邊時(shí)，這條邊所關(guān)聯(lián)的兩個(gè)頂點(diǎn)的權(quán)重不再是0，而是增大，對(duì)應(yīng)的這兩個(gè)頂點(diǎn)與其他頂點(diǎn)產(chǎn)生邊的概率不再與上次概率相等而是增大；之后再生成新的邊時(shí)，其所關(guān)聯(lián)兩個(gè)頂點(diǎn)權(quán)重也會(huì)發(fā)生變化，同時(shí)與其他點(diǎn)生成新的邊的概率也會(huì)對(duì)應(yīng)地變化。

隨著各頂點(diǎn)權(quán)重的變化，它們與其他頂點(diǎn)產(chǎn)生邊的概率也在變化。使用變量delta來(lái)控制生成圖時(shí)各個(gè)頂點(diǎn)產(chǎn)生邊的概率，從而決定了該圖的結(jié)構(gòu)特征。

3.2 GADSF

GADSF用于生成一組頂點(diǎn)和邊數(shù)相同但結(jié)構(gòu)特征不同的圖，算法的核心思想是：通過(guò)調(diào)節(jié)delta的值，當(dāng)某兩個(gè)頂點(diǎn)之間生成邊時(shí)，下一次該頂點(diǎn)與其他頂點(diǎn)生成新邊時(shí)的概率比其他新的頂點(diǎn)之間生成邊的概率增大，而delta的取值影響該概率變化的幅度。

對(duì)于圖G(V，E)而言，若delta=0，則所有邊均為等概率生成，即每個(gè)頂點(diǎn)被選中的概率pk=1/V。

當(dāng)delta=s(s為正整數(shù))時(shí)，步驟如下：

步驟1 第一條邊是等概率產(chǎn)生，假設(shè)第一次隨機(jī)生成的邊為(Vi，Vj)，則下一次頂點(diǎn)Vi和Vj被選中的概率pi=pj=(1+delta)/(V+2*delta)，而其他的頂點(diǎn)被選中的概率p=1/(V+2*delta)。

步驟2 假設(shè)第二次隨機(jī)生成的邊為(Vj,Vq)，則下一次頂點(diǎn)Vj和Vq被選中的概率分別是pj=(1+2*delta)/(V+4*delta)，pq=(1+delta)/(V+4*delta)，其余的k個(gè)頂點(diǎn)被選中的概率pk=1/(V+4*delta)；之后以此類(lèi)推。

圖3為V=10，E=15，delta=0,1,2,3時(shí)生成的圖。圖3(a)中，頂點(diǎn)度最大為3且邊分布均衡；圖3(b)中，頂點(diǎn)度最大為5切邊分布相對(duì)均衡；圖3(c)中頂點(diǎn)度最大為6且邊的分布不均衡；圖3(d)中頂點(diǎn)度最大為5但邊分布極不均衡。

圖3 10個(gè)頂點(diǎn)15條邊不同結(jié)構(gòu)特征

4 描述方法有效性驗(yàn)證

將歐氏距離的相似度計(jì)算應(yīng)用在結(jié)構(gòu)特征值相似度匹配算法中，計(jì)算真實(shí)圖與仿真圖之間的相似度，找到一個(gè)與真實(shí)圖最相似的仿真圖用以表征現(xiàn)實(shí)世界中真實(shí)的圖，從而證明結(jié)構(gòu)特征描述方法的有效性。

4.1 結(jié)構(gòu)特征相似度匹配算法

現(xiàn)實(shí)中的大圖，其頂點(diǎn)往往符合冪律分布，并且每個(gè)節(jié)點(diǎn)的劃分對(duì)其整體劃分效果的影響是非均衡的。若兩個(gè)圖頂點(diǎn)度分布具有相似性，則可說(shuō)明這兩個(gè)圖具有相似性。本節(jié)依據(jù)此設(shè)計(jì)了結(jié)構(gòu)特征相似度匹算法，具體步驟如下：

步驟1 計(jì)算真實(shí)圖各個(gè)頂點(diǎn)的頂點(diǎn)度并降序排列記為集合D；

步驟2 從D中選出top-k個(gè)頂點(diǎn)(頂點(diǎn)度最大的k個(gè)頂點(diǎn))，并將這些頂點(diǎn)的頂點(diǎn)度記為向量A(a0,a1,a2,…,ak-1)；

步驟3 將生成的仿真圖數(shù)據(jù)集的每一個(gè)圖也選出相同數(shù)量的top-k個(gè)頂點(diǎn)數(shù)記為向量B(b0,b1,b2,…,bk-1)；

步驟4 計(jì)算向量A、B之間的歐氏距離Distance并記錄；

步驟5 對(duì)仿真圖數(shù)據(jù)集中不同delta的圖重復(fù)步驟3和4。

通過(guò)以上步驟，可找到與真實(shí)圖距離最小的仿真圖，即與真實(shí)圖最相似的圖，則該仿真圖可表示真實(shí)圖。

4.2 匹配實(shí)驗(yàn)及結(jié)果分析

4.2.1 實(shí)驗(yàn)數(shù)據(jù)的選取及生成

實(shí)驗(yàn)數(shù)據(jù)選自斯坦福大學(xué)公開(kāi)的大圖數(shù)據(jù)集中一個(gè)真實(shí)圖G(6 301,20 777)，即該圖有6 301個(gè)頂點(diǎn)和20 777條邊。根據(jù)4.1節(jié)提出的不同結(jié)構(gòu)特征大圖的生成算法生成仿真數(shù)據(jù)集。令V=6 301，E=20 777，delta={0,1,2,3,4,5},Gi(0≤i≤5∩x∈R)。

4.2.2 實(shí)驗(yàn)結(jié)果及分析

計(jì)算出真實(shí)圖G中頂點(diǎn)集V的頂點(diǎn)度并降序排列記為向量A(a0,a1,a2,…,a6300)，分別將仿真圖Gi頂點(diǎn)集Vi的頂點(diǎn)度計(jì)算出，并降序排列記為向量B(b0,b1,b2,…,b6300)。從向量A、B中選取頂點(diǎn)度最大的k個(gè)頂點(diǎn)，其中k分別取63，120，180，即所取頂點(diǎn)是原圖總頂點(diǎn)數(shù)的1%、2%、3%，計(jì)算Distance，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 結(jié)構(gòu)特征相似度匹配結(jié)果

圖4中3條曲線分別代表頂點(diǎn)數(shù)取63，120，180，delta為0,1,2,3,4,5時(shí)仿真圖Gi和真實(shí)圖G之間的相似度曲線圖。明顯地看出delta=2時(shí)，距離Distance最小，向量A、B之間距離最近，說(shuō)明delta=2時(shí)生成的仿真圖與真實(shí)圖最為相似，由此證明描述大圖結(jié)構(gòu)特征的方法是有效的。

5 結(jié)構(gòu)特征與劃分效果之間關(guān)系

將真實(shí)圖G和仿真圖集Gi進(jìn)行劃分，通過(guò)比較劃分結(jié)果再次證明大圖結(jié)構(gòu)特征描述方法的有效性。在此基礎(chǔ)上，選取Hash和點(diǎn)對(duì)交換劃分算法兩種劃分算法，研究大圖結(jié)構(gòu)特征對(duì)劃分效果的影響。

5.1 大圖劃分算法

首先選取了Hash法中的直接取余法，其優(yōu)點(diǎn)是可以保證劃分子圖之間的負(fù)載相隨均衡，減少本實(shí)驗(yàn)的不確定因素，突出交叉邊與劃分效果之間的關(guān)系。其次，選擇點(diǎn)對(duì)交換算法，該算法一種貪心算法，不從整體最優(yōu)上加以考慮，每次只朝著有益的方向進(jìn)行迭代，進(jìn)而逼近最優(yōu)解。

5.1.1 Hash劃分算法

Hash劃分算法就是把任意長(zhǎng)度的輸入，通過(guò)散列算法，變換成固定長(zhǎng)度的輸出。不同的關(guān)鍵字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，這種現(xiàn)象稱(chēng)為碰撞。在此選取Hash算法中的取模法，即直接取余法：f(x)=xmodk(k為非負(fù)整數(shù))。

為給定圖G(V，E)的頂點(diǎn)賦予唯一的標(biāo)識(shí)號(hào)即變量x(x為非負(fù)整數(shù))，然后通過(guò)取模將頂點(diǎn)集V劃分為k個(gè)互不相交的子集V1，V2，…，Vk。當(dāng)xi≠xj，而f(xi)≠(xj)時(shí)，則xi、xj所對(duì)應(yīng)的頂點(diǎn)Vi、Vj將會(huì)被劃分到同一個(gè)子圖中。

5.1.2 點(diǎn)對(duì)交換算法

定義1 COE(Count of Original Edges)為原始交叉邊個(gè)數(shù)，即將給定圖G(V，E)的頂點(diǎn)集V，Hash劃分為k個(gè)互不相交的子集V1，V2，…，Vk后，k個(gè)子集之間的交叉邊數(shù)。

定義2 CEE(Count of Exchange Edges)即執(zhí)行n(n為足夠大的非負(fù)整數(shù))次點(diǎn)對(duì)交換算法后，k個(gè)子集之間的交叉邊數(shù)。

點(diǎn)對(duì)交換算法的具體步驟如下：

步驟1 將圖的頂點(diǎn)集V散列的劃分成V1，V2，…，Vk個(gè)互不相交的子集并且計(jì)算COE。

步驟2 從k個(gè)子圖中各自選取一個(gè)頂點(diǎn)Si在V1,V2,…,Vk中隨機(jī)交換Si并且計(jì)算CEE。

步驟3 若CEE

最后一次有效的CEE可近似地認(rèn)為是劃分結(jié)果的最優(yōu)解。

5.2 劃分實(shí)驗(yàn)

5.2.1 一次劃分實(shí)驗(yàn)

由于篇幅有限，這里僅舉例說(shuō)明圖G(V，E)，V=6 301，E=20 777，delta=2時(shí)的劃分方法，其他數(shù)據(jù)集劃分方法相同。步驟如下：

步驟1 將頂點(diǎn)集V中每個(gè)頂點(diǎn)賦予唯一的標(biāo)識(shí)號(hào)即變量x{0≤x≤6 301∩x∈R}，在Hash劃分算法中k值取2，即將圖劃分為兩個(gè)子圖V1、V2且保證負(fù)載均衡并且計(jì)算COE。

步驟2 每次將V1，V2中隨機(jī)各取一個(gè)點(diǎn)記為Vi，Vj，設(shè)置臨時(shí)變量temp用以交換Vi，Vj，記錄交換后的新圖并計(jì)算CEE。

步驟3 若CEECOE，則表示交換后交叉邊個(gè)數(shù)沒(méi)有減少，則為無(wú)效交換，將temp的值回滾給Vj恢復(fù)交換之前的狀態(tài)，轉(zhuǎn)至步驟2。

點(diǎn)對(duì)交換算法在交換足夠多的次數(shù)后，能夠有效地減少交叉邊數(shù)量，降低通信開(kāi)銷(xiāo)。通過(guò)多次實(shí)驗(yàn)得出，迭代5 000次后，交叉邊的個(gè)數(shù)明顯減少，若連續(xù)10 000次無(wú)變化，則近似認(rèn)為達(dá)到最優(yōu)解，停止迭代。將真實(shí)圖G和仿真圖數(shù)據(jù)集Gi(0≤i≤5∩x∈R)進(jìn)行劃分，記錄交叉邊個(gè)數(shù)結(jié)果如表1(交換次數(shù)為0即為Hash劃分的交叉邊個(gè)數(shù))。通過(guò)表1得出以下結(jié)果。

表1 圖數(shù)據(jù)集執(zhí)行兩種劃分算法交叉邊數(shù)

1)通過(guò)Hash算法劃分不同圖數(shù)據(jù)集時(shí)，無(wú)論圖的結(jié)構(gòu)如何發(fā)生變化，交叉邊數(shù)很大且無(wú)明顯變化，進(jìn)一步說(shuō)明該算法忽略了大圖結(jié)構(gòu)特征對(duì)其劃分效果的影響。

2)對(duì)真實(shí)圖G和仿真圖G2進(jìn)行劃分，當(dāng)點(diǎn)對(duì)交換算法執(zhí)行到5萬(wàn)次時(shí)，圖G交叉邊的個(gè)數(shù)由Hash劃分的10 425條減少到4 762條；圖G2交叉邊的個(gè)數(shù)由10 267條減少到4 090條，且與圖G與的交叉邊數(shù)量最接近。由此說(shuō)明了點(diǎn)對(duì)交換劃分算法能夠減少交叉邊數(shù)，且描述圖結(jié)構(gòu)特征的方法是有效的。

3)對(duì)仿真圖數(shù)據(jù)集Gi{0≤i≤5∩x∈R)執(zhí)行點(diǎn)對(duì)交換算法5萬(wàn)次時(shí)，隨著delta的增大即圖的結(jié)構(gòu)特征發(fā)生變化，交叉邊數(shù)明顯下降。由此說(shuō)明了大圖結(jié)構(gòu)特征對(duì)劃分效果有很大影響

5.2.2 二次劃分實(shí)驗(yàn)

為了證明結(jié)構(gòu)特征與劃分效果之間的普適性，進(jìn)行第二次劃分實(shí)驗(yàn)。分別生成兩組數(shù)據(jù)集A、B。

A:V=100，E=1 000，delta∈{0≤delta≤9∩x∈R}

B:V=1 000，E=100 000，delta∈{0≤delta≤9∩x∈R}

采用同樣實(shí)驗(yàn)步驟分別將兩組數(shù)據(jù)集進(jìn)行劃分,得出的結(jié)果如圖5所示。圖5(a)是數(shù)據(jù)集A執(zhí)行點(diǎn)對(duì)交換劃分算法2萬(wàn)次時(shí)劃分結(jié)果，圖5(b)圖是數(shù)據(jù)集B執(zhí)行5萬(wàn)次時(shí)劃分結(jié)果。由圖5可明顯地看出：隨著delta的增大，COE變化不大而CEE的數(shù)量明顯減少，說(shuō)明了圖的結(jié)構(gòu)特征對(duì)劃分效果有著直接的影響，也就是說(shuō)圖的頂點(diǎn)度分布差異越顯著，交換后的交叉邊個(gè)數(shù)越少，劃分效果越好。

6 結(jié)語(yǔ)

大圖劃分是實(shí)現(xiàn)大圖分布式處理的重要基礎(chǔ)。盡管當(dāng)前已經(jīng)提出大量算法來(lái)改進(jìn)大圖劃分的效果，但均忽視了大圖結(jié)構(gòu)本身對(duì)劃分效果的影響。本文首先提出一種描述大圖結(jié)構(gòu)特征的方法，并通過(guò)大量實(shí)驗(yàn)驗(yàn)證了結(jié)構(gòu)特征對(duì)真實(shí)圖結(jié)構(gòu)表征的有效性。最后，通過(guò)劃分實(shí)驗(yàn)分析了不同算法下大圖結(jié)構(gòu)特征與劃分效果之間的具體關(guān)系，這對(duì)下一步建立圖的結(jié)構(gòu)特征與劃分效果之間的關(guān)系模型奠定了基礎(chǔ)，達(dá)到利用圖結(jié)構(gòu)特征預(yù)測(cè)劃分效果的目標(biāo)。

圖5 兩組數(shù)據(jù)集劃分結(jié)果

References)

[1] JOHANNES F M. Partitioning of VLSI circuits and systems [C]// DAC ’96: Proceedings of the 33rd Annual Design Automation Conference. New York: ACM, 1996: 83-87.

[2] MEYERHENKE H, SANDERS P, SCHULZ C. Parallel graph partitioning for complex networks [C]// Proceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium. Piscataway, NJ: IEEE, 2015: 1055-1064.

[3] KARYPIS G, KUMAR V. Parallel multilevelk-way partitioning scheme for irregular graphs [J]. Journal of Parallel & Distributed Computing, 1999, 41(2): 278-300.

[4] HENDRICKSON B, LELAND R. An improved spectral graph partitioning algorithm for mapping parallel computations [J]. SIAM Journal on Scientific Computing, 1995, 16(2): 452-469.

[5] VAQUERO L, CUADRADO F, LOGOTHETIS D, et al. Adaptive partitioning for large-scale dynamic graphs [C]// ICDCS 2014: Proceedings of the 2014 IEEE 34th International Conference on Distributed Computing Systems. Piscataway, NJ: IEEE, 2014: 144-153.

[6] HUANG J, ABADI D J. Leopard: lightweight edge-oriented partitioning and replication for dynamic graphs [J]. Proceedings of the VLDB Endowment, 2016, 9(7): 540-551.

[7] MAYER C, TARIQ M A, LI C, et al. GrapH: heterogeneity-aware graph computation with adaptive partitioning [C]// ICDCS 2016: Proceedings of the 36th IEEE International Conference on Distributed Computing Systems. Piscataway, NJ: IEEE, 2016: 118-128.

[8] GAREY M R, JOHNSON D S, STOCKMEYER L. Some simplified NP-complete graph problems [J]. Theoretical Computer Science, 1976, 1(3): 237-267.

[9] 鄭麗麗.圖劃分算法綜述[J].科技信息,2014(4):145-145.(ZHEN L L. A survey of graph partitioning algorithms [J]. Science and Technology Information, 2014(4): 145-145.)

[10] BARNARD S T, SIMON H D. Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems [J]. Concurrency and Computation Practice and Experience, 2010, 6(2): 101-117.

[11] KERNIGHAN B W, LIN S. An efficient heuristic procedure for partitioning graphs [J]. Bell System Technical Journal, 1970, 49(2): 291-307.

[12] FIDUCCIA C M, MATTHEYSES R M. A linear-time heuristic for improving network partitions [C]// 25 years of DAC Papers on Twenty-Five Years of Electronic Design Automation. New York: ACM, 1988: 241-247.

[13] FARSHBAF M, FEIZI-DERAKHSHI M R. Multi-objective optimization of graph partitioning using genetic algorithms [C]// Proceedings of the 3rd International Conference on Advanced Engineering Computing and Applications in Sciences. Washington, DC: IEEE Computer Society, 2009: 1-6.

[14] BOULIF M. Genetic algorithm encoding representations for graph partitioning problems [C]// Proceedings of the 2010 International Conference on Machine and Web Intelligence. Piscataway, NJ: IEEE, 2010: 288-291.

[15] ROLLAND E, PIRKUL H, GLOVER F. Tabu search for graph partitioning [J]. Annals of Operations Research, 1996, 63(2): 209-232.

[16] AARTS E, KORST J, MICHIELS W. Simulated annealing [J]. Metaheuristic Procedures for Training Neural Networks, 2007, 36(3): 187-210.

[17] 翟明清.圖的結(jié)構(gòu)參數(shù)與特征值[D].上海:華東師范大學(xué),2010:1-5.(ZHAI M Q. Structure variables and eigenvalues of graphs [D]. Shanghai: East China Normal University, 2010: 1-5.)

[18] FALLAT S M, KIRKLAND S, PATI S. On graphs with algebraic connectivity equal to minimum edge density [J]. Linear Algebra & Its Applications, 2003, 373: 31-50.

[19] NIKIFOROV V. Note: Eigenvalue problems of Nordhaus-Gaddum type [J]. Discrete Mathematics, 2014, 307(6): 774-780.

[20] LIU H, LU M, TIAN F. On the spectral radius of unicyclic graphs with fixed diameter [J]. Linear Algebra & Its Applications, 2007, 420(2/3): 449-457.

[21] KHARAGHANI H, TAYFEH-REZAIE B. On the energy of (0,1)-matrices [J]. Linear Algebra & Its Applications, 2008, 429(8): 2046-2051.

This work is partially supported by the National Natural Science Foundation of China (41472234), the Scientific Research Program of Shaanxi Provincial Education Department (15JK1468), the Xi’an University of Science and Technology Foundation for Fostering Talents (201633).

LUOXiaoxia, born in 1964, professor. Her research interests include big data and cloud computing, software engineering, distributed computing.

SIFengwei, born in 1992, M. S. candidate. His research interests include distributed storage, graph partitioning algorithm.

LUOXiangyu, born in 1984, Ph. D., lecturer. Her research interests include distributed storage, big data.

DOI:10.11772/j.issn.1001- 9081.2017071886