求解大規(guī)模稀疏有向圖回路的多線程并行算法

，， ，

(山東科技大學 計算機科學與工程學院，山東 青島 266590)

圖在知識圖譜、社交網(wǎng)絡等很多領域都具有廣泛應用，其中求解圖的回路是一個重要問題[1]?；贒FS(deep-first search，深度優(yōu)先遍歷)的求解算法是目前最常用的算法[2]，但隨著圖的規(guī)模日益增大，傳統(tǒng)的串行求解算法由于存儲能力的限制，無法求解該問題。

本文面向大規(guī)模稀疏有向圖，給出了一種可在普通PC(personal computer，個人計算機)上基于多線程的并行求解算法MPCF(multithreading parallel circuit finding)。該算法首先刪除圖中出度為0的所有頂點，然后找到圖中出度較大的頂點，采用多線程方法并行求解含有這些頂點的回路，接著刪除這些頂點，再采用單線程方式求解剩余圖的回路。

1 相關工作

求解圖的回路是一個被廣泛關注的問題，針對不同的回路，已提出了多種求解算法，如求解Hamilton回路的非遞歸算法[1]、求解所有頂點的最短回路的算法[3]、求解最長回路的算法[4]等。這些算法基本上都是基于DFS實現(xiàn)的，其核心過程是：從某個頂點出發(fā)，找出剛訪問頂點的第一個未被訪問的鄰接點，然后再從此鄰接點出發(fā)，繼續(xù)找它的下一個新的鄰接點進行訪問，重復此步驟，直到遇到無法繼續(xù)訪問或者遇到一個已經(jīng)被訪問的頂點。如果是后者，則表示發(fā)現(xiàn)了一個回路。由此可見，DFS算法的主要過程就是遞歸搜索，而這也正是它的不足之處：當圖數(shù)據(jù)集規(guī)模較小時，遞歸工作棧淺，內(nèi)存開銷小，單機運算足以勝任；但對于大規(guī)模圖，單個頂點的鄰接點數(shù)目眾多，頻繁的遞歸操作勢必會造成內(nèi)存不足，最終因堆棧溢出而出錯。王玉英等[5]提出的求解有向圖的全部簡單回路的算法，基于矩陣運算，避免了遞歸調(diào)用，但對于稀疏圖而言，鄰接矩陣的存儲方式占用了過多的存儲空間，也容易造成內(nèi)存溢出。

由于圖結構的特殊性，頂點與頂點之間具有很強的依賴關系，很難找到一種合適的圖劃分方式來打破這種依賴性，而且DFS算法本身難以有效地實現(xiàn)并行化[6]，因而目前尚無有效的基于DFS的回路求解并行算法。

近年來逐漸興起的云計算系統(tǒng)為基于機群的并行圖處理系統(tǒng)提供了有力支撐，從而催生了如Pregel[7]、GraphX[8]、GPS[9]等圖處理系統(tǒng)。這些系統(tǒng)都是基于BSP(bulk synchronous parallel)模型實現(xiàn)的，大致處理流程如下：

1) 將圖劃分成多個分區(qū)，每個分區(qū)分配到集群中的多個計算節(jié)點上；

2) 將每個計算節(jié)點上的頂點均標記成“活躍”狀態(tài)；

3) 開始運行一個超步，每個頂點均調(diào)用自定義的函數(shù)，函數(shù)功能包括執(zhí)行計算、消息傳遞等；

4) 同步結束后，運行下一個超步并重復此過程，直到所有頂點都不再“活躍”并且系統(tǒng)中不會有任何消息在傳輸，這時執(zhí)行過程結束。

可見，這類系統(tǒng)能夠以批處理方式來處理大規(guī)模圖數(shù)據(jù)集問題，但這些計算框架均需要搭建分布式處理系統(tǒng)，還要考慮分布式文件存儲和任務調(diào)度，大大提高了計算成本。SC-BSP[10]模型在BSP的計算框架下引入分離器和組合器，對圖劃分的邊集進行合理分配和管理，提高了水平擴展能力，但圖劃分對計算效率的影響仍然較大。此外，基于BSP模型的求解算法均是以頂點為中心的消息傳遞方式來處理圖問題的，效率較低。

2 問題定義

G=(V,E)是一個有向圖，其中V={v1,v2,…}是頂點集合,E={〈vi,vj〉|vi,vj∈V,i≠j}是有向邊(又稱為弧)的集合。若〈vi,vj〉∈E，則稱vj為vi的鄰接頂點。記

為頂點vi的出度。記

分別為所有頂點的最大出度和平均出度。定義

表示N個出度中，最大的前[Nα]個出度對應的頂點總數(shù)與G中所有頂點數(shù)量之比。記ρ0為出度為0的頂點數(shù)占頂點總數(shù)的比例，即

本文所要解決的問題是求解給定的一個大規(guī)模稀疏有向圖的所有簡單回路。

3 回路求解的MPCF算法

大規(guī)模稀疏圖是一類非常常見的模型，如服從冪率分布的社交網(wǎng)絡[11]。這類圖具有兩個非常重要的特點：一是圖中存在大量出度/入度為0的頂點；二是圖中僅有少部分頂點的出度/入度非常大。文獻[11]的分析表明微博數(shù)據(jù)便具有上述兩個特點。本文對斯坦福大學的SNAP[12]數(shù)據(jù)集中的7種不同規(guī)模的圖進行了分析(表1)，這些數(shù)據(jù)也滿足上述兩個特點?；诖?，可以設想：

1) 刪除出度為0的頂點，能夠大幅度縮減圖的規(guī)模；

2) 采用并行方式求解包含出度較大頂點的回路，刪除這些頂點后，再求解剩余圖的回路，可有效提高計算效率。

表1 有向稀疏圖出度的分析

MPCF算法便是基于上述思想設計的。在初始化相關變量(第1行)、對頂點出度排序(第2、3行)后，從圖中刪除出度為0的頂點(第4行)，并根據(jù)參數(shù)α將出度排序靠前的頂點放入集合Vlarge中(第5行)。第6、7行啟動n個線程，其中nmax是預先指定的最大線程數(shù)。第8～11行為并行執(zhí)行過程，每個線程求包含Vlarge中一個頂點的回路集合，同時為保證不同線程求解的是不同頂點，將算法第9行中nextVertex()方法做加鎖處理。第12行將Vlarge中的頂點刪除，接著求出剩余頂點的導出子圖G′(第13行)。第14～16行以串行方式求G′的回路集合。此處之所以使用串行，是因為圖G′頂點數(shù)目龐大，但由于沒有大出度頂點，邊數(shù)目減少，圖變得極其稀疏，在圖規(guī)模一定的情況下，使用串行算法即可在較快時間內(nèi)求解，并行算法由于線程啟動、管理等方面的時間消耗，反而需要花費更多的時間。該算法中，nextVertex()用于返回Vlarge中下一個尚未求解其回路的頂點；findCircuits(v)用于求包含頂點v的回路集合，即以頂點v作為起點和終點的回路的集合；induceSubGraph(V′)用于求頂點集合V′的導出子圖。

需要指出的是：該算法是在單機上執(zhí)行多線程的，各個線程共享內(nèi)存，而且線程在求回路時，對圖G是只讀操作，因此圖G不需要分割存儲，即各線程無需存儲G的信息。

MPCF算法Input：DirectedgraphG=(V，E)，parameterαOutput：AllcircuitssetCSofGprocedureMPCF(G，α)1．CS←Φ2．Getdoutiforeachvi∈VusingEquation(1)3．Sortdoutiinnon?descendingordera1，a2，…，aN{}4．V′←V-vi|douti=0{}5．Vlarge←vi|a[Nα]￡douti￡a1{}6．n←minVlarge，nmax{}7．Forknthreads8．foreachthreaddoinparallel9． synchronizedu←nextVertex()10． CS←CS∪findCircuits(u)11．endfor12．V′←V′-Vlarge13．G′←induceSubGraph(V′)14．forallv∈V′do15． CS←CS∪findCircuits(v)16．endfor17．returnCS18．endprocedure

假定使用鄰接表來存儲圖數(shù)據(jù)，那么算法的時間復雜性分析如下。第2行需O(|V|+|E|)來求各個頂點的出度。第3行排序需用O(NlogN)來排序N個不同的出度值。第4行需要O(ρ0|V|)來刪除出度為0的頂點。第8～11行并行過程的時間取決于求解包含出度最大頂點u的回路的時間。在最壞情況下，若以u為根的生成樹包含了V′的所有頂點，使用DFS思想求回路的方法需要時間為O((1-ρ0)|V|+|E|)?？紤]到圖的稀疏性，第12～13行所求出的導出子圖僅包含非常少的邊，所以第14～16行的時間不會超過O((1-ρ0)|V|)。因此，該算法的時間復雜性為O(2|V|+2|E|+NlogN)。對于稀疏圖，N<|E|?|V|2，所以MPCF算法的時間復雜度要低于文獻[5]所提出算法的時間復雜度O(|V|2)。

4 實驗與結果分析

本文進行實驗的圖數(shù)據(jù)即表1所示的7個有向圖。實驗用計算機的CPU為Intel? CoreTMi5-3210M CPU @ 2.50 GHz，運行內(nèi)存為6 GB，操作系統(tǒng)為Windows10(64位)。算法采用JAVA語言實現(xiàn)，設置JVM(JAVA虛擬機)最大堆內(nèi)存參數(shù)“-Xmx”為4 GB。每個單獨實驗均做10次，每次實驗完成后，重啟主機以保證每次實驗環(huán)境一致，并且互不影響。運行時間取10次平均值。

4.1 α的取值

α是MPCF算法的關鍵參數(shù)，決定了進入并行環(huán)節(jié)的頂點數(shù)量，因此首先需要根據(jù)圖的規(guī)模來選取α值。此處分別對α取0.1、0.2和0.3進行實驗，結果如表2所示，表中tpara和tseq分別表示算法1中第8～11步并行求解的時間、第14～16步串行求解的時間，ttotal=tpara+tseq?！啊北硎敬胁糠謨?nèi)存溢出，無法求出所有的回路。

表2 不同α值實驗結果

根據(jù)實驗結果，可以得出：

1) 當頂點數(shù)在10萬以下時，α=0.1所需計算時間最少。

2) 當頂點數(shù)在10萬到100萬之間時，α=0.1已無法串行求解G′的回路。α=0.2時所需時間最少。

3) 當頂點數(shù)超過100萬時，只有α=0.3方可求解回路。

4.2 MPCF算法性能分析

由于文獻[5]的算法是基于矩陣乘法運算的，對于表1中的大規(guī)模圖，僅圖的鄰接矩陣便需要占用大量的內(nèi)存空間。如對于10萬個頂點的圖，即使每個矩陣元素僅需1 B內(nèi)存，整個鄰接矩陣就需要占用超過9 GB內(nèi)存，在計算過程中，則至少需要20 GB內(nèi)存。因此該算法無法在普通PC上實現(xiàn)。

本文將MPCF算法與基于DFS的串行回路求解算法進行對比分析，執(zhí)行時間如表3所示，占用內(nèi)存情況如圖1所示。表3中tdfs為串行求解算法所需的時間。tpara和tseq是在4.1節(jié)中確定的α值基礎上求解算法的時間。

表3 算法性能分析

可以看出，p2p-Gnutella04和p2p-Gnutella25兩個圖的數(shù)據(jù)規(guī)模較小，串行算法占用內(nèi)存在4 GB以下，且能在數(shù)百毫秒內(nèi)求出所有的有向回路(少于10萬個)。MPCF算法的執(zhí)行時間僅略少于串行算法，約為串行算法時間的96%～97%，tpara占全部執(zhí)行時間的12%～13%。從內(nèi)存情況看，這兩個圖的串行求解算法沒有因為遞歸而導致內(nèi)存溢出，MPCF算法的并行部分和串行部分占用內(nèi)存為串行算法的30%～65%。

對于其余的4個圖，它們包含的有向回路數(shù)在18萬條以上，此時串行求解算法的遞歸部分占用內(nèi)存急劇增加，超過了3.9 GB，Java程序出現(xiàn)內(nèi)存溢出(Out of Memory)異常，從而無法求出所有的有向回路。MPCF算法的并行階段僅求解極少量頂點的回路，串行階段因處理的圖G′已非常稀疏而遞歸層次淺，所以MPCF算法的內(nèi)存開銷未溢出。但隨著圖中所包含回路數(shù)量的增加，MPCF算法所需的時間和內(nèi)存也在增長。從時間上來看，MPCF算法的并行部分約為串行部分時間的20%～37%；從內(nèi)存上來看，MPCF算法的并行部分約為串行部分時間的78%～94%。

因此，MPCF算法在內(nèi)存方面能夠保證大規(guī)模圖有向回路的正常求解。

圖1 算法內(nèi)存分析

5 總結

針對傳統(tǒng)基于DFS思想的算法無法在普通PC上求解大規(guī)模稀疏圖所有有向回路的問題，通過對圖數(shù)據(jù)集的分析，提出了一種基于多線程的并行求解算法。同時，為了測試此種求解方式的可行性，本文使用真實社交網(wǎng)絡數(shù)據(jù)進行實驗，結果表明此算法可在普通PC上求得大規(guī)模有向稀疏圖的所有回路。本文所提出的算法同樣適用于無向圖。下一步，我們將進一步研究在多核、眾核處理器上處理更大規(guī)模圖的算法。

[1]SILVA J L C,ROCHA L,SILVA B C H.A new algorithm for finding all tours and Hamiltonian circuits in graphs[J].IEEE Latin America Transactions,2016,14(2):831-836.

[2]LI B,XIONG L,YIN J.Large degree vertices in longest cycles of graphs,I[J].Discussiones Mathematicae Graph Theory,2016,36(2):363-382.

[3]YUSTER R.A shortest cycle for each vertex of a graph[J].Information Processing Letters,2011,111(21-22):1057-1061.

[4]PAULUSMA D,YOSHIMOTO K.Cycles through specified vertices in triangle-free graphs[J].Discussiones Mathematicae Graph Theory,2007,27(1):179-191.

[5]王玉英,陳平,蘇旸.生成有向圖中全部簡單回路的一種新算法[J].山西師范大學學報(自然科學版),2008,36(4):12-15.

WANG Yuying,CHEN Ping,SU Yang.A new algorithm to find all elementary circuits of a directed graph[J].Journal of Shaanxi Normal University(Natural Science),2008,36(4):12-15.

[6]REIF J H.Depth-first search is inherently sequential[J].Information Processing Letters,1985,20(5):229-234.

[7]MALEWICZ G,AUSTERN M H,BIK A J C,et al.Pregel:A system for large-scale graph processing[C]//ACM SIGMOD International Conference on Management of Data,2010:135-146.

[8]GONZALEZ J E,XIN R S,DAVE A,et al.GraphX:Graph processing in a distributed dataflow framework[C]//Proceedings of 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14),2014:599-613.

[9]SALIHOGLU S,WIDOM J.GPS:A graph processing system[C]//Proceedings of 25th International Conference on Scientific and Statistical Database Management.Baltimore,Maryland,USA,July 2013:Article No.22.

[10]趙翔,李博,商海川,等.一種改進的基于BSP的大圖計算模型[J].計算機學報,2017,40(1):223-235.

ZHAO Xiang,LI Bo,SHANG Haichuan,et al.A revised BSP-based massive graph computation model[J].Chinese Journal of Computers,2017,40(1):223-235.

[11]羅由平,周召敏,李麗娟,等.基于冪率分布的社交網(wǎng)絡規(guī)律分析[J].計算機工程,2015,41(7):299-304.

LUO Youping,ZHOU Zhaomin,LI Lijuan,et al.Social network discipline analysis based on power-law distribution[J].Computer Engineering,2015,41(7):299-304.

[12]LESKOVEC J,KREVL A.SNAP datasets:Stanford large network dataset collection[DB/OL].(2017-07-24)http://snap.stanford.edu/data,2014.