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

劉揚(yáng), 魏蔚, 許賀洋

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

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

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

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

已有工作中從多個(gè)角度對最大流問題進(jìn)行了探討,但仍存在一些問題:①圖縮減和并行計(jì)算2種加速思路并未充分融合,基于單個(gè)思路的加速效果受限;②未考慮常見的單個(gè)圖中多次最大流求解場景,多次計(jì)算間存在大量冗余工作;③圖縮減方法需要涉及出入度和邊容量等多個(gè)條件,計(jì)算復(fù)雜度偏高,甚至?xí)窒⑿杏?jì)算加速效果。針對上述問題,我們嘗試?yán)秒p連通分量構(gòu)建覆蓋圖, 提出了稀疏大圖中基于雙連通分量覆蓋圖(BCR:bi-connected component overlay)的并行加速方法。對原始圖中任意兩點(diǎn)間的最大流問題,基于覆蓋圖分解成多個(gè)子圖內(nèi)最大流計(jì)算問題,并行求解這些子問題。覆蓋圖僅涉及連接關(guān)系,對局部拓?fù)浣Y(jié)構(gòu)沒有任何要求,計(jì)算復(fù)雜度較低。在基準(zhǔn)網(wǎng)絡(luò)拓?fù)渖系膶?shí)驗(yàn)結(jié)果表明,算法可顯著縮短計(jì)算時(shí)間,大幅提升求解效率。

1 模 型

1.1 試驗(yàn)方法

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

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

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

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

圖1 算法模型圖

定義3割點(diǎn):如在圖G中去掉一個(gè)頂點(diǎn),并同時(shí)去掉與該頂點(diǎn)相關(guān)聯(lián)的所有邊后,該圖的連通分量數(shù)增加,則稱該頂點(diǎn)為圖G的割點(diǎn)。

定義4雙連通分量的界點(diǎn):若某連通分量中節(jié)點(diǎn)和外部節(jié)點(diǎn)存在邊,稱該節(jié)點(diǎn)為雙連通分量的界點(diǎn)。

割點(diǎn)的示例見圖1中左側(cè)黑色節(jié)點(diǎn),其中節(jié)點(diǎn)8和11也是界點(diǎn)。雙連通分量和割點(diǎn)存在如下關(guān)系:

引理1連通圖G的某個(gè)雙連通分量所有界點(diǎn)必然是割點(diǎn)。

證明設(shè)雙連通分量為vU,則有:

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

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

3) 因?yàn)閏和a均為vU內(nèi)節(jié)點(diǎn),存在2條無重復(fù)節(jié)點(diǎn)路徑,進(jìn)而b2和內(nèi)部任何節(jié)點(diǎn)a,都存在b2→b→c→a和b2→c→a2條無重復(fù)節(jié)點(diǎn)路徑,即包含vU和b2的分量也是雙連通分量,這和vU是雙連通極大子圖相矛盾。

4) 由于上述證明并未對界點(diǎn)b外的任何其他節(jié)點(diǎn)的性質(zhì)做出假設(shè),即證明任何一個(gè)界點(diǎn)如是割點(diǎn)都會(huì)導(dǎo)出矛盾,可得出在存在>=2個(gè)界點(diǎn)情況下,每個(gè)界點(diǎn)都必須是割點(diǎn)。

5) 根據(jù)前述證明,對于存在>=1個(gè)界點(diǎn)情況下,每個(gè)界點(diǎn)必然是割點(diǎn),證畢。

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

引理2若在原圖G的一個(gè)連通子圖中,每個(gè)界點(diǎn)在分量外的鄰居節(jié)點(diǎn)只能通過該界點(diǎn)連到連通分量內(nèi)節(jié)點(diǎn),且該連通子圖中沒有割點(diǎn),則該連通子圖為雙連通分量。

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

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

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

圖1中右側(cè)即為雙連通覆蓋圖。關(guān)于雙連通分量覆蓋圖G′的拓?fù)浣Y(jié)構(gòu),給出下述定理:

定理3雙連通分量覆蓋圖G′是樹形拓?fù)洹?/p>

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

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

2 算 法

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

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

2.1 覆蓋圖構(gòu)建算法

覆蓋圖構(gòu)建對應(yīng)圖2的步驟(1),原理如圖3所示。

圖3 雙連通分量覆蓋圖構(gòu)建示意圖

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

根據(jù)引理2,我們給出了遞歸的覆蓋圖構(gòu)建算法,如表1所示。

表1 雙連通分量覆蓋圖構(gòu)建算法

續(xù)表1

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

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

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

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

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

對應(yīng)的最大流加速算法2如表2所示。

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

3 實(shí) 驗(yàn)

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

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

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

圖5 基準(zhǔn)圖中并行度和縮減倍數(shù)的變化趨勢

圖6 基準(zhǔn)圖中所有算法平均最大流計(jì)算時(shí)間對比

圖7 基準(zhǔn)圖中所有算法平均預(yù)處理時(shí)間對比

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

Clique:文獻(xiàn)[10]基于局部子圖縮減的最大流求解方法,檢測子圖特征時(shí)使用了最大團(tuán)方法。

Community方法:文獻(xiàn)[10]中基于網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)縮減的最大流求解方法。

VertexPair:文獻(xiàn)[15]中基于節(jié)點(diǎn)對的縮減方法。

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

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

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

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

4 結(jié) 論

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