羅曉霞，司豐瑋，羅香玉

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

0 引言

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

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

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

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

1 相關工作

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

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

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

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

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

2 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 GADSF

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

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

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

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

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

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

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

4 描述方法有效性驗證

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

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

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

步驟1 計算真實圖各個頂點的頂點度并降序排列記為集合D；

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

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

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

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

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

4.2 匹配實驗及結(jié)果分析

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

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

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

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

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

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

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

5.1 大圖劃分算法

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

5.1.1 Hash劃分算法

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

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

5.1.2 點對交換算法

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

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

點對交換算法的具體步驟如下：

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

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

步驟3 若CEE

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

5.2 劃分實驗

5.2.1 一次劃分實驗

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

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

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

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

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

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

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

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

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

5.2.2 二次劃分實驗

為了證明結(jié)構(gòu)特征與劃分效果之間的普適性，進行第二次劃分實驗。分別生成兩組數(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ù)據(jù)集進行劃分,得出的結(jié)果如圖5所示。圖5(a)是數(shù)據(jù)集A執(zhí)行點對交換劃分算法2萬次時劃分結(jié)果，圖5(b)圖是數(shù)據(jù)集B執(zhí)行5萬次時劃分結(jié)果。由圖5可明顯地看出：隨著delta的增大，COE變化不大而CEE的數(shù)量明顯減少，說明了圖的結(jié)構(gòu)特征對劃分效果有著直接的影響，也就是說圖的頂點度分布差異越顯著，交換后的交叉邊個數(shù)越少，劃分效果越好。

6 結(jié)語

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

圖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].上海:華東師范大學,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