大圖結(jié)構(gòu)特征對劃分效果的影響

羅曉霞，司豐瑋，羅香玉

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

0 引言

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

2 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 GADSF

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

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

當(dāng)delta=s(s為正整數(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個頂點(diǎn)被選中的概率pk=1/(V+4*delta)；之后以此類推。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

實(shí)驗(yàn)數(shù)據(jù)選自斯坦福大學(xué)公開的大圖數(shù)據(jù)集中一個真實(shí)圖G(6 301,20 777)，即該圖有6 301個頂點(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é)果及分析

計算出真實(shí)圖G中頂點(diǎn)集V的頂點(diǎn)度并降序排列記為向量A(a0,a1,a2,…,a6300)，分別將仿真圖Gi頂點(diǎn)集Vi的頂點(diǎn)度計算出，并降序排列記為向量B(b0,b1,b2,…,b6300)。從向量A、B中選取頂點(diǎn)度最大的k個頂點(diǎn)，其中k分別取63，120，180，即所取頂點(diǎn)是原圖總頂點(diǎn)數(shù)的1%、2%、3%，計算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時仿真圖Gi和真實(shí)圖G之間的相似度曲線圖。明顯地看出delta=2時，距離Distance最小，向量A、B之間距離最近，說明delta=2時生成的仿真圖與真實(shí)圖最為相似，由此證明描述大圖結(jié)構(gòu)特征的方法是有效的。

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

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

5.1 大圖劃分算法

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

5.1.1 Hash劃分算法

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

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

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

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

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

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

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

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

步驟3 若CEE

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

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

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

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

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

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

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

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

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

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

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

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

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)對交換劃分算法2萬次時劃分結(jié)果，圖5(b)圖是數(shù)據(jù)集B執(zhí)行5萬次時劃分結(jié)果。由圖5可明顯地看出：隨著delta的增大，COE變化不大而CEE的數(shù)量明顯減少，說明了圖的結(jié)構(gòu)特征對劃分效果有著直接的影響，也就是說圖的頂點(diǎn)度分布差異越顯著，交換后的交叉邊個數(shù)越少，劃分效果越好。

6 結(jié)語

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