基于雙連通分量覆蓋圖的稀疏大圖最大流并行加速方法

劉揚, 魏蔚, 許賀洋

(河南工業大學 信息科學與工程學院, 河南 鄭州 450001)

作為圖數據之上一類經典的組合優化問題,最大流問題尋找通過一個流通網絡的最大流量,是網絡流理論體系中重要的研究領域[1]。最大流可輔助求解一些重要的基礎理論問題,如雙邊匹配等線性規劃問題,以及一些重要的應用問題,如網絡規劃[2],網絡和信息安全[3]和各類復雜系統中的資源調度[4]等。經典的最大流算法主要包括增廣路[5]和預流推進[6]2種方法,并在2種方法基礎上衍生出了很多變種以降低計算復雜度。已知最大流加速方法包括針對有向平面圖的快速算法[7],針對計算機視覺圖數據的快速計算方法[8],以及基于線性代數或電路流的最大流近似計算方法等[9-10]。但隨著各行業數據呈爆炸性增長,傳統加速方法已無法應對大規模圖上的最大流問題。針對大規模圖中最大流加速,已有方法主要集中在圖縮減和并行計算2個方面:

1) 圖縮減思路:通過化簡原始網絡,降低問題規模并減少后續重復計算。如針對單源單匯最大流問題,文獻[11]提出基于圖縮減機制的兩階段最大流方法,針對幾種局部特殊拓撲結構,將滿足給定代數關系的子圖縮為節點,在簡化的圖上進行快速計算。文獻[12]通過多次最大流計算,構建原始圖的最小割樹,以丟失路徑信息的代價,快速求解任意2個節點之間的最大流值。文獻[13-14]檢測滿足縮減標準的網絡社區結構,將其壓縮為一點,在簡化的圖上獲取最大流近似解。文獻[15]尋找合并后不影響外部最大流的節點對,通過多次迭代合并圖中的節點對縮小圖的規模。文獻[16]利用商空間理論建立問題求解的保真和保假原理,將圖中所有節點對之間最大流計算量從n(n-1)/2次降低為n-1次左右。

2) 并行計算思路:基于底層的多種并行架構加速求解過程。早期工作主要集中在實現多處理器環境中的并行算法[17-18]。隨著云計算技術的發展,出現了基于多種通用和專用并行計算模型的加速方法。其中,文獻[19]實現了基于Spark框架的Edmonds-Karp增廣路算法,在算法各步驟采取不同計算模型,利用框架中內置的pregel和mapreduce等多種計算接口提升算法并行度。文獻[20]針對包含上億節點和數十億條邊的社交網絡數據,在算法和mapreduce框架層進行跨層優化,將最大流計算時間縮短至10分鐘左右。

已有工作中從多個角度對最大流問題進行了探討,但仍存在一些問題:①圖縮減和并行計算2種加速思路并未充分融合,基于單個思路的加速效果受限;②未考慮常見的單個圖中多次最大流求解場景,多次計算間存在大量冗余工作;③圖縮減方法需要涉及出入度和邊容量等多個條件,計算復雜度偏高,甚至會抵消并行計算加速效果。針對上述問題,我們嘗試利用雙連通分量構建覆蓋圖, 提出了稀疏大圖中基于雙連通分量覆蓋圖(BCR:bi-connected component overlay)的并行加速方法。對原始圖中任意兩點間的最大流問題,基于覆蓋圖分解成多個子圖內最大流計算問題,并行求解這些子問題。覆蓋圖僅涉及連接關系,對局部拓撲結構沒有任何要求,計算復雜度較低。在基準網絡拓撲上的實驗結果表明,算法可顯著縮短計算時間,大幅提升求解效率。

1 模 型

1.1 試驗方法

算法主要處理無向圖中的最大流問題,首先引入連通分量和雙連通分量的定義。

定義1連通分量:在無向圖中,若頂點1和頂點2之間存在路徑,則稱頂點1和2連通。若某個子圖中任意2個頂點之間都連通,則稱該圖為連通圖,其中極大連通子圖稱為連通分量。

定義2雙連通分量:若任意圖中任意2點至少存在2條不存在重復點的路徑,則稱該圖為雙連通圖;對一個無向圖,雙連通的極大子圖稱為雙連通分量。

圖1示例中,左側虛線包含的子圖為雙連通分量中。雙連通分量和割點有緊密關系,下面引入割點和雙連通分量界點的定義。

圖1 算法模型圖

定義3割點:如在圖G中去掉一個頂點,并同時去掉與該頂點相關聯的所有邊后,該圖的連通分量數增加,則稱該頂點為圖G的割點。

定義4雙連通分量的界點:若某連通分量中節點和外部節點存在邊,稱該節點為雙連通分量的界點。

割點的示例見圖1中左側黑色節點,其中節點8和11也是界點。雙連通分量和割點存在如下關系:

引理1連通圖G的某個雙連通分量所有界點必然是割點。

證明設雙連通分量為vU,則有:

1) 若只有一個界點a,則去除a后,vU和外部不相連,a即為割點。

2) 假設有>=2個界點,且界點b不是割點。設界點b和外部節點b2相連,則對于vU中任何一個節點a,存在路徑b2→b→a;因b不是割點,則去除b后,b2和節點a間仍存在路徑,設該路徑上最早訪問到的vU內節點是界點c且有c≠b,則節點b2到c存在b2→b→c和b2→c2條路徑;因路徑b→c存在只通過vU內節點的路徑,而b2→c不通過任何vU內節點,即b2到c存在2條路徑無重復節點的路徑。

3) 因為c和a均為vU內節點,存在2條無重復節點路徑,進而b2和內部任何節點a,都存在b2→b→c→a和b2→c→a2條無重復節點路徑,即包含vU和b2的分量也是雙連通分量,這和vU是雙連通極大子圖相矛盾。

4) 由于上述證明并未對界點b外的任何其他節點的性質做出假設,即證明任何一個界點如是割點都會導出矛盾,可得出在存在>=2個界點情況下,每個界點都必須是割點。

5) 根據前述證明,對于存在>=1個界點情況下,每個界點必然是割點,證畢。

由引理1可知,在一個連通圖中,所有雙連通分量必然通過割點與外部相連。

引理2若在原圖G的一個連通子圖中,每個界點在分量外的鄰居節點只能通過該界點連到連通分量內節點,且該連通子圖中沒有割點,則該連通子圖為雙連通分量。

證明取原始圖G中任意2個節點及之間的邊構成一個小的特殊的雙連通圖vU,對vU中節點a在分量外的鄰居b,只要b不通過a也能連到vU內節點,即b能通過第二個界點a2連到vU內,則b至少能連到2個不同的界點,可知對vU內任意節點c,節點b都有2條無重復節點路徑b→a→c和b→a2→c,因此b也能加入到vU中并組成更大的雙連通圖。因此,直到每一個界點在雙連通圖外鄰居只能通過該界點連到連通圖內,這種擴張過程才能停住,此時獲得的是極大雙連通圖,即雙連通分量。證畢。

基于引理2,可先找到所有割點,識別被割點分隔的并以割點為界點的連通分量,保證分量外鄰居節點只能通過界點連到分量內,即得到雙連通分量,在獲取所有雙連通分量過程中,可構建雙連通分量覆蓋圖,定義如下:

定義5雙連通分量覆蓋圖:設原始圖G對應的雙連通分量覆蓋圖為G′,對原始圖G中每個雙連通分量,在G'中對應一個類型為U的節點;其每個割點,在G′中對應一個類型為W的節點vW,若割點v屬于某個雙連通分量,則在該雙連通分量在圖G′中的U類節點和vW間建立一條邊;對原圖中與割點v不屬于同一個雙連通分量的所有鄰居節點,用他們對應的G′中節點分別和v建立一條邊。

圖1中右側即為雙連通覆蓋圖。關于雙連通分量覆蓋圖G′的拓撲結構,給出下述定理:

定理3雙連通分量覆蓋圖G′是樹形拓撲。

證明反證。因不存在環路的圖即為樹,假設雙連通分量覆蓋圖G′中存在環路,依據環路定義,環路中任意2個節點在G′中存在無重復點的>=2條路徑,即G′中環路上的類型為W的節點對應的原圖G中任意兩個節點也存在無重復點的>=2條路徑,即G′中環路上的點所對應的點在原圖G中屬于同一個雙連通分量,而根據生成規則,同一個雙連通分量中所有非割點對應一個U類節點,每個割點對應的W節點和該U類節點間存在一條邊,同屬于一個U類節點的這些W節點之間不會存在邊,即G′中這些節點只會組成局部星形結構,這和組成環路相矛盾。證畢。

基于定理3,我們也把雙連通分量覆蓋圖G′寫為雙連通分量覆蓋樹T′。

2 算 法

算法的基本思想如圖2所示:①首先,識別原始圖中的雙連通分量并縮成點以構建覆蓋圖,建立原始圖到覆蓋圖中節點的單射關系。②對原始圖中節點對s和t,尋找覆蓋圖中的對應點S和T。③覆蓋圖中S和T之間路徑上每個U類節點對應原圖中的一個雙連通分量,U類節點在路徑上前后兩個節點是雙連通分量的界點,則可并行求解每個雙連通分量的2個界點之間的最大流。④合并子問題結果得到原始圖中節點對s和t最大流的解。

圖2 最大流加速方法整體流程

2.1 覆蓋圖構建算法

覆蓋圖構建對應圖2的步驟(1),原理如圖3所示。

圖3 雙連通分量覆蓋圖構建示意圖

左側原始圖可轉換為右側覆蓋圖,覆蓋圖中的實線節點對應原圖中相同編號的割點,覆蓋圖中虛線節點對應左側原圖中的雙連通分量;其中,原始圖到覆蓋圖的映射關系在圖中下方的表格中。對于原圖中節點1和10的最大流,由于對應的N1和N4之間的唯一路徑包含界點2/4/6/8,則原圖中節點1和節點10最大流可分解為(1,2),(2,4)(4,8)(8,10)4個并行的最大流計算,從而大幅降低求解時間。注意此時各個界點間的計算僅涉及對應的雙連通分量內的節點,即此時原圖中節點1和10之間的所有最大流路徑,不可能包含覆蓋圖中路徑上之外的節點,例如此時N2的另外一個界點為11,且根據定義必為割點,則最大流路徑不可能涉及節點12所在的雙連通分量除11之外的節點,否則節點11必然在路徑中出現2次,違反了最大流路徑為簡單路徑的定義。這也意味著,基于覆蓋圖可排除部分節點,這也可降低計算量。

根據引理2,我們給出了遞歸的覆蓋圖構建算法,如表1所示。

表1 雙連通分量覆蓋圖構建算法

續表1

整個構建過程首先確定一個根節點,按照深度優先的順序在每個節點上遞歸調用固定的算法,在單個節點上調用的遞歸算法。算法識別各個雙連通分量,同時更新對應的雙連通分量覆蓋樹T′,并建立雙連通分量覆蓋樹中節點到原圖節點的映射關系。算法1在運行時,表1中遞歸調用結束時step1會被調用N次,step2會被調用2M次,而step2中包含循環的步驟為step2.6.3和step2.6.4,由于對每條邊只會調用1次,全局共被調用M次,則算法1的復雜度為O(N+M),在稀疏大圖中遠小于最大流算法復雜度下限O(NM)[1]。這說明構建算法復雜度較低,和圖的規模呈線性關系。

2.2 基于覆蓋圖的最大流加速方法

基于覆蓋圖的加速方法包含圖2流程圖的所有步驟,其示例如圖4所示。

圖4 基于雙連通分量覆蓋圖的最大流加速示意圖

針對圖3中原始圖中節點1到節點10的最大流問題,基于映射表查詢得到圖4的覆蓋圖中節點N1和N4。在雙連通分量縮點樹T′中搜索并發現如圖4中N1至N4的唯一路徑;路徑上每個雙連通分量節點對應一個子問題(如圖4中左右兩側的虛線圓圈),通過并行求解子問題可進一步提高計算速度。

對應的最大流加速算法2如表2所示。

表2 基于雙連通分量覆蓋圖的最大流加速算法

3 實 驗

我們在基準評測圖中分析和比較算法的加速效果,每個圖的參數主要包括節點數量N和無向邊的數量M。對每個(N,M)組合,采用權威評測工具GENRMF[24]生成50個基準圖,每個圖選取50個節點對分別計算最大流。GENRMF工具接收a,b,c1和c2(>c1)4個參數,首先會產生b個擁有a個節點的子圖, 隨機分配順序號給每個子圖中節點,并將其與前后2個相鄰編號的節點相連;每個子圖也隨機獲得一個順序號,與前后2個相鄰編號的子圖做節點一對一的映射并建立連接。每個圖中,邊的容量在c1和c2之間隨機分布,節點數量N=ab,無向邊數量M=a(2b-1),在此基礎上隨機增加邊以得到對應的邊數量M。因M≥6N后并行度變化不大,實驗主要考察M≤5N的稀疏圖中的變化情況。

首先考察多個圖中多次計算時并行度的均值及最大和最小值變化趨勢,如圖5a)所示,其中稀疏度(density)定義為M/N。圖5a)表明并行度(及最大/最小值)均隨節點數量N的增加或稀疏度的降低有緩慢增加,不同稀疏度下的并行度均值隨著N的增加逐漸趨向接近,說明算法在稀疏大圖中始終能保持合適的并行度。隨著節點數量的增大,并行度的區間有增大趨勢,稀疏度較高時區間范圍隨節點數量增大增加趨勢更快,例如在N=107時所有稀疏度下的最小值也能達到接近10左右,保證最差情況下的加速效果。

我們也考察縮減倍數均值及最大最小值的變化趨勢,如圖5b)所示,其中Y軸為指數坐標系。可發現,縮減倍數均值和節點數量大致呈指數關系,且均值(及最大/最小值)隨節點數量N的增加或稀疏度的降低有緩慢的增加。隨著節點數量的增加, 各種稀疏度下的縮減倍數均有指數級的增加,并不隨著稀疏度變化有明顯降低。且隨著節點數量的增大,區間也有明顯的變大趨勢(注:Y軸為指數坐標系)。另外縮減倍數最小值始終都有增大的趨勢,但是在稀疏度較高和節點數量較低時可能會很小,如N=105且稀疏度為5時為1左右,此時整個原圖即為一個雙連通分量,從而使得最大流計算需涉及原圖中所有節點。

圖5 基準圖中并行度和縮減倍數的變化趨勢

圖6 基準圖中所有算法平均最大流計算時間對比

圖7 基準圖中所有算法平均預處理時間對比

基于前述理論分析, 我們在上述基準網絡上比較我們的算法和經典算法的效果。硬件環境為ThinkStation P310工作站,擁有2顆4核CPU和32GB內存,CPU主頻2.6GHz,操作系統采用CentOS7.0.并行計算時開啟8個線程,每線程對應一個CPU核;計算時將所有子問題組織成先進先出隊列,依次將問題調度給空閑的線程。已知面向通用最大流求解的串行算法是基于highest push/relable的方法[22],因此在各類圖縮減算法計算時均默認采用highest push/relable計算縮減圖中的最大流,比對的各類算法標記如下:

Clique:文獻[10]基于局部子圖縮減的最大流求解方法,檢測子圖特征時使用了最大團方法。

Community方法:文獻[10]中基于網絡社區結構縮減的最大流求解方法。

VertexPair:文獻[15]中基于節點對的縮減方法。

實驗中針對3個不同的節點數量N,從基準圖中隨機選擇各種稠密度的50幅圖,每幅基準圖中選取50個不同節點對分別進行最大流計算,并記錄各種不同方法中除去數據載入和輸出的計算時間,如圖6所示,其中X軸分別對應節點數量N=105,106,107,Y軸為按對數坐標顯示的計算時間。此時我們算法BCR對應X軸3個坐標點的計算時間均值分別為0.3 s,2.3 s,13.2 s。可見僅N=105時VertexPair方法平均要稍快一些(約為我們方法的0.9倍左右時間),其他方法以及在更大的圖中,我們方法都是最快的,而且隨著圖規模的增加,其他方法的計算時間呈指數級上升。檢查數據發現,由于Clique和Community方法尋找最大團和社團等無尺寸限制的子圖結構,而實際上由于算法限制,稀疏圖中能找到的子圖結構并不多,從而影響了加速效果;隨著圖規模的增加,相應的子圖結構并沒有同步變大,使得縮減效果進一步降低,導致加速效果變差,而VertexPair基于局部的2個子節點進行縮減,無論在何種圖中都能充分找到可利用的子圖結構,從而保證一定的加速效果。

我們也比較了所有方法的預處理時間,如圖7所示。我們算法中對應X軸3個坐標點的預處理時間均值分別為0.9 s,8.7 s,61.3 s。我們算法始終保持較低的預處理時間;且隨著圖規模的增大,在N=107時相對其他方法的優勢更加明顯;檢查對應的預處理算法發現,Clique和Community方法尋找無尺寸限制子圖方法,在原圖增大時計算復雜度呈指數級增加;而VertexPair方法優化后可維持線性的復雜度,但整體上我們的預處理時間仍然最低。前述實驗可得到如下結論:

1) 相對其他方法,我們算法加速效果部分來自于排除作用,即排除計算不會涉及的節點,將計算相關節點縮減到一個很小的范圍,在大圖中甚至可縮減到原圖節點的萬分之一左右,大大加速計算速度;加速效果的另外一個來源是并行計算的引入,通過將原始的最大流問題分隔成多個獨立的可并行求解的子問題,可充分利用底層設施的并行性加速計算;且由于獨立子問題數量不會太多,對基礎設施要求也較低。

2) 相比基于大范圍子圖方法Clique和Community,我們的算法加速效果更明顯,且前期處理時間也大幅領先;我們的算法對于VertexPair這種針對局部小型子圖的方法也有優勢。上述優勢隨著圖尺寸的增加而增加,也說明了我們方法更加適用于大規模稀疏圖。

4 結 論

本文提出基于雙連通分量覆蓋圖的稀疏大圖最大流并行加速方法,算法采用雙連通分量建立覆蓋圖,將原始圖中最大流問題分解為多個子圖中的局部問題,基于并行計算加速求解。在大量基準圖上的分析和實驗表明,算法具極低的覆蓋圖構建代價,相比已知算法可達到2個數量級的加速效果。將來的工作可從多個角度展開,包括尋找稠密大圖中的最大流并行加速方法,及如何在分布式計算框架上實現基于覆蓋圖的加速計算。