基于標簽傳播的大規(guī)模網絡最大流求解方法*

魏華珍，趙 姝+，陳 潔，張以文，張燕平

1.安徽大學 計算機科學與技術學院，合肥 230601

2.安徽大學 信息保障技術協同創(chuàng)新中心，合肥 230601

基于標簽傳播的大規(guī)模網絡最大流求解方法*

魏華珍1,2，趙 姝1,2+，陳 潔1,2，張以文1,2，張燕平1,2

1.安徽大學 計算機科學與技術學院，合肥 230601

2.安徽大學 信息保障技術協同創(chuàng)新中心，合肥 230601

Abstract:This paper proposes a method,which is named MFLPA(maximum flow based on label propagation algorithm)and can simplify large-scale network to solve maximum flow problem.The original network is divided into multiple sub-networks.By combined with quotient space theory,each sub-network is contracted to a single vertex to construct a small-scale quotient network.Finally,MFLPA is applied on the quotient network to approximately get the maximum flow value of original network,which effectively reduces the computational complexity.The experimental results show that MFLPA performances well compared to the ISAP(improved shortest augument path)andDinic,and the effect becomes even more obvious with increasing of the network size.Moreover,MFLPA reduces network size more than 70%,and experimental error is less than 5%.

Key words:maximum flow;label propagation;large-scale network;quotient space theory;simplify network

針對大數據時代背景下，對海量數據的高效智能處理方式的需求，提出了一種簡化大規(guī)模網絡求解最大流的方法MFLPA（maximum flow based on label propagation algorithm）?；跇撕瀭鞑⒊跏加邢蚓W絡劃分成多個子網絡；結合商空間理論通過計算將子網絡壓縮成單個節(jié)點，形成規(guī)模較小的商網絡；最后，在商網絡中求解初始網絡的近似優(yōu)解，有效降低了計算復雜性。實驗結果表明，MFLPA在不同網絡上運行速度均比ISAP（improved shortest augument path）和Dinic有顯著提升，效果隨著網絡規(guī)模的增大而越顯著，縮小網絡規(guī)模達到70%以上，實驗誤差不超過5%。

最大流；標簽傳播；大規(guī)模網絡；商空間；簡化網絡

1 引言

最大流問題是一種組合最優(yōu)化的經典問題，在圖論領域有非常重要的研究意義。現代社會的方方面面都可能是復雜的網絡系統，其結構或元素間復雜的拓撲信息都可以抽象成網絡中的節(jié)點及邊，比如萬維網、交通網、電力網、信息網、社交網等。在實際網絡問題中，最大流問題的目的是求解一個有容量限制的網絡中源點可傳輸到匯點的最大流量，并確定其傳輸策略，使得網絡充分發(fā)揮其運載能力，資源的調度達到最優(yōu)狀態(tài)。

隨著信息時代的發(fā)展，除了解決實際網絡中的通信流量分配、交通運輸路線分配之外，最大流問題在從互聯網獲取海量圖信息的背景下也有了其他應用，如發(fā)現垃圾郵件網站[1]，社區(qū)結構發(fā)現[2-3]，P2P網絡中防止Sybil攻擊[4]，網絡計票[5]等。最大流問題是線性規(guī)劃問題之一，研究最大流可以得到網絡中特定條件下的組合最優(yōu)解。

對于最大流問題的研究已有60多年的發(fā)展歷史，從Dantzig[6]提出了網絡單純形法開始，Fulkerson等人在最大流問題中首次使用圖方法[7]，隨后由Ford和Fulkerson提出了經典的增廣路徑算法[8]。由此學者們紛紛提出了許多出色的改進算法，Edmonds[9]和Dinitz[10]等人引入最短增廣路徑算法把Ford-Fulkerson算法變?yōu)閺姸囗検?，而后Karzanov得出預流推進算法[11]，Ahuja和 Orlin 提出了 ISAP（improved shortest augument path）算法，其充分地利用距離標號的作用，提高了算法效率[12]。為了滿足各種網絡的需求，近年來學者們提出了許多新算法，如針對平面圖[13-14]以及稀疏網絡[15]的算法等。

然而持續(xù)增長的數據造成網絡規(guī)模呈現指數式的攀升，網絡中的節(jié)點數量已經早已不是幾百幾千個節(jié)點，而常常是以千萬計或者以億計，所對應的圖的規(guī)模也急劇擴大。在這個背景下雖然經典及其改進算法仍被廣泛應用，但已無法滿足規(guī)模日益增長的網絡的需求，需要有新的應對策略與求解方案[16]。針對大規(guī)模網絡最大流問題，Liers與Pardella[17]提出SME（shrink max edge）方法。這種方法通過壓縮最大容量邊達到減小網絡規(guī)模的目的，但只對初始網絡粗略簡化，不能大規(guī)模地降低網絡的規(guī)模，并且這種簡化方法對于很多網絡是不適用的。當前對于大規(guī)模網絡數據的處理大多采用并行計算[18]的求解策略。這種方法可以很好地提高大規(guī)模網絡最大流的求解速度，但需要先對問題有個合適的劃分，并且分布式算法復雜且靈活。綜上，目前需要一個簡單易行的方法去滿足大規(guī)模網絡數據帶來的多樣性需求[16]。

面對大量復雜的信息，人類智能與計算機處理問題不同之處在于，人類既可以從宏觀俯瞰全局，也能從微觀進行細節(jié)分析[19]，正是這種對問題宏觀層次與微觀層次相結合的思考方式使得人類智能能夠把復雜的問題簡單化、抽象化，使其變?yōu)橐粋€易解決與計算的問題[20]。而人工智能領域的粒計算正是研究模擬人類智能思考與解決大規(guī)模復雜問題的理論。

粒計算主要包含Zadeh[21]提出的模糊集模型、Pawlak[22]提出的粗糙集模型以及Zhang等人[23]提出的商空間模型，它通過將復雜信息進行?；僮?用粒子代替原大規(guī)模樣本作為計算單元,并將復雜問題轉化到不同粒度空間上進行分析，對各個粒解進行合成得到原問題的最優(yōu)近似解，適用于近似求解有層次結構的問題，以達到簡化問題規(guī)模，提高求解效率的目的[24]。Qian等人曾指出[25]“任何一個復雜系統都是具有層次結構的系統”，因此對于大規(guī)模網絡而言，其本身也應該具有層次結構，適于使用商空間模型進行求解。

在使用商空間模型簡化大規(guī)模網絡的時候，最重要的問題是把什么樣的結構?；?，看作一個粒子。隨著研究人員對網絡性質的深入探索，發(fā)現許多網絡都存在一種共同的結構——社區(qū)結構。復雜網絡往往由許多個“群”組成，單個“群”的內部節(jié)點呈現較為緊密的聚集性，而群與群之間的連結則相對分散和稀疏[26]。網絡中這樣的結構可以天然地作為粒子，同時社區(qū)結構內部的節(jié)點可以看作具有相同等價關系的節(jié)點集合。

目前有很多種方法可以發(fā)現網絡中的社區(qū)結構，其中典型方法有模塊度優(yōu)化方法[27]、譜分析法[28]、信息論方法[29]、標簽傳播方法[30]等。本文旨將社區(qū)發(fā)現應用到最大流問題中，因此需要尋找的社區(qū)結構應該是非重疊的，方便后續(xù)結合商空間理論對粒子進行合并計算，但不需要對網絡進行非常精確的社區(qū)劃分。而標簽傳播方法最大的優(yōu)點在于不需要任何參數輸入，比如社區(qū)的數目、大小等，算法收斂速度非?？欤坏珦碛袠O低的線性時間復雜度，同時可以很好地保持圖的社區(qū)結構，適用于大規(guī)模網絡圖的社區(qū)劃分[31]。

因此，本文提出一種簡化大規(guī)模網絡求解最大流的方法MFLPA（maximum flow based on label propagation algorithm）。首先基于標簽傳播將初始網絡劃分成不同的子網絡，接著結合商空間理論對大規(guī)模網絡進行簡化，使得最大流算法能夠在簡化后的商網絡上快速求解。

本文組織結構如下：第2章介紹與本文相關的基本概念和定義；第3章對MFLPA進行詳述；第4章使用公用最大流網絡生成工具得出實驗結果，并對不同結果進行分析和討論；第5章對全文進行總結和展望。

2 基本概念及相關定義

定義1[8]（流網絡）設給定一個流網絡G(V,E,C),其中V表示網絡中節(jié)點構成的節(jié)點集合，E是網絡中的邊集合，C代表容量集合。流網絡中每條邊都有一個非負容量，若網絡中任意節(jié)點v∈V,w∈V，則(v,w)代表從節(jié)點v流向w的邊，容量為c(v,w),由于流網絡是有向網絡，(w,v)代表從節(jié)點w流向v的邊，容量為c(w,v)。

定義2[8]（可行流）網絡中s代表源點，t代表匯點，?v,w∈V,邊(v,w)∈E的流量f(v,w)若滿足以下3個性質則稱為可行流：

定義3[24]（最大流問題）對于一個流網絡G(V,E,C),求其從給定的源點s到匯點t可行流中的最大流值為maxf(s,t)=MFG(V)。

定義4[8]（流差）對于子網絡任一節(jié)點x∈X,設定參數屬性finside、foutside，xfinside代表網絡中除X節(jié)點集之外的節(jié)點流入節(jié)點x的流量和，表示公式為即代表網絡中除了X節(jié)點集合之外的節(jié)點流出節(jié)點v的流量和。定義γx為流差，代表流進流出x的差值。

定義5[23]（商網絡）對于流網絡G(V,E,C)，給定V上的一個等價關系R，則[V]代表節(jié)點集合V對應等價關系R的商集，定義?[v],[w]∈[V],([v],[w])∈[E]?v∈[v],w∈[w],(v,w)∈E,且這樣得到的新網絡G([V],[E],[C])稱為原流網絡對應于等價關系R的商網絡。

3 MFLPA算法描述

3.1 算法框架

本文提出的簡化大規(guī)模網絡求解最大流的方法MFLPA的基本思想為：基于標簽傳播對大規(guī)模有向流網絡G(V,E,C)劃分成不同子網絡；隨后確立壓縮判定條件對子網絡進行篩選，滿足條件的子網絡中的每個子網絡內部節(jié)點具有等價關系R,將處于同一子網絡中具有等價關系R的節(jié)點壓縮成為一個節(jié)點，以此來構建規(guī)模較小的商網絡G([V],[E],[C]),從而達到簡化網絡的目的；最后在商網絡上使用ISAP（Dinic）算法求得初始網絡最大流的近似優(yōu)解。

3.2 算法詳述

MFLPA算法包含三部分：基于標簽傳播劃分子網絡，壓縮判定條件的確立，壓縮網絡并構建商網絡。下面將展開進行描述。

3.2.1 基于標簽傳播劃分子網絡

MFLPA算法首先基于標簽傳播理論[30]劃分子網絡，為網絡G(V,E,C)的所有節(jié)點指派唯一的初始標簽（如一個整數），標簽作為子網絡的唯一標識，標記節(jié)點所屬子網絡。

設擁有n個鄰居節(jié)點的節(jié)點x的標簽為l(x),N(x)表示這n個鄰居節(jié)點的節(jié)點集合，t代表迭代次數。在每一步迭代中，網絡中的節(jié)點被隨機排列后放入一個節(jié)點序列，隨后按照節(jié)點序列中的順序，對其中的每個節(jié)點x,將自身標簽更新為其鄰居節(jié)點集N(x)中出現頻數最多的標簽MaxLabel。如果存在多個標簽其出現頻數均為最多，則隨機選取其中一個，并用這個標簽更新自身原有標簽。在若干次迭代后，如果每個節(jié)點具有的標簽都是其鄰居節(jié)點中出現頻數最多的標簽，則停止，否則繼續(xù)迭代過程。最后，具有相同標簽的節(jié)點歸為同一個子網絡，對流網絡進行一個劃分，得到子網絡節(jié)點集合{Vgi|i=1,2,…}。在網絡中，緊密相連的節(jié)點會快速收斂于同一標簽，如圖1所示。

Fig.1 Because of high density of edges,5 nodes acquire same labela圖1 緊密相連的節(jié)點1～5收斂于同一標簽a

算法1基于標簽傳播劃分子網絡算法

輸入：初始網絡G=(V,E,C)

輸出：子網絡節(jié)點集合{Vgi|i=1,2,…}

3.2.2 壓縮判定條件的確立

在找到所有子網絡gv之后，需要對其中合適的子網絡壓縮，但并不是所有子網絡結構都適合壓縮，不適當的壓縮則會很大程度地影響最大流的求解結果。

首先需要確立判斷子網絡能否被壓縮的條件，滿足壓縮判定條件的每個子網絡的內部節(jié)點看作具有等價關系R的集合。由網絡流理論[8]可知，流網絡中的中間節(jié)點既不產生多余流量也不滯留經流的流量。經過對網絡流性質的研究和實驗發(fā)現，劃分得到的某一子網絡，若外部流入到該子網絡中每個節(jié)點的流量能從它本身或者子網絡任一節(jié)點流出，則滿足這樣條件的子網絡就可以被壓縮。

由于網絡中除去源點s和匯點t之外的所有節(jié)點都屬于中間節(jié)點，這一條件相當于微觀流網絡中間節(jié)點的中轉理論延伸到宏觀的子網絡整體上的應用，這里的整個子網絡相當于初始網絡中既不產生多余流量也不滯留過境的流量的中間節(jié)點。同時經過大量實驗驗證，該條件的確立雖然無法完全避免壓縮掉含有最小割邊的子網絡，但是可以盡量減少這種情況的發(fā)生。

判斷子網絡能否被壓縮首先需要由子網絡gv構建新子網絡g′v，便于壓縮條件的判斷。設子網絡gv={Vgi,Egi},Egi={(e1,e2)∈Egi|e1,e2∈Vgi},構建的算法如下。

算法2構建新子網絡算法

輸入：子網絡gv

輸出：新子網絡g′v

由算法2得到添加了虛擬節(jié)點s′和t′以及與其相關聯邊的新子網絡g′v。

假設X是Vgi中的某個節(jié)點集合，x是X中的任一節(jié)點，計算X集合的新子網絡最大流MFG(X),若代表由s′流出的邊都是飽和邊，且這些流量都能從t′流出，滿足壓縮判定條件。

圖2（a）到（c）所示的是標簽a劃分的子網絡構建新子網絡過程的例子。其中圖2（a）代表網絡的初始狀態(tài)，節(jié)點a1～a5代表由算法1基于標簽傳播劃分得到的一個子網絡所包含的節(jié)點，節(jié)點1～9代表與該子網絡有邊連接的子網絡外部節(jié)點。圖2（b）建立新的節(jié)點s′、t′,并分別計算節(jié)點集A={a1,a2,a3,a4,a5}中每個節(jié)點的流入流出差值γ，由算法2構建與節(jié)點s′、t′相連的邊，生成了新子網絡（見圖2（c））。最后根據ISAP(Dinic)計算得，滿足壓縮條件。

Fig.2 Process of constructing new sub-network based on labela圖2 標簽a劃分的子網絡構建新子網絡過程

3.2.3 壓縮網絡并構建商網絡

對所有由子網絡gv構建的新子網絡g′v求解最大流并進行壓縮條件判定，滿足條件的子網絡中的每個子網絡內部節(jié)點看作具有等價關系R。根據商空間理論[23]，具有等價關系R的節(jié)點集合可被壓縮成為一個節(jié)點，把滿足條件的每個子網絡節(jié)點集合分別進行壓縮處理。

具體操作是：假設X為滿足壓縮條件的某個子網絡節(jié)點集合，首先將X替換為單個節(jié)點x，并將X集合內部節(jié)點之間相互連接的邊E(X)全部刪除，E(X)={x1∈X,x2∈X|(x1,x2)∈E}，而子網絡節(jié)點集合X與外部節(jié)點v∈(V-X)連接的邊，替換為單個節(jié)點x與外部節(jié)點v∈(V-X)連接的邊；隨后對所有平行邊進行合并操作，合并之后使得x與任一外部節(jié)點v∈(V-X)連接的同一方向的邊至多只有一條。完成所有壓縮操作之后，形成了商網絡G([V],[E],[C]),網絡規(guī)模和結構復雜度都大大減小，最后在商網絡上使用最大流算法對網絡求得最大流的近似解。

圖3所示為壓縮子網絡構建商網絡過程的例子。圖3（a）中(a,1)和(1,a)這兩條邊為平行邊，合并后為圖3（b）中(1,a)。圖3（b）為由圖2（a）中標簽a劃分的子網絡進行壓縮操作后得到的簡化網絡。

基于標簽傳播的大規(guī)模網絡最大流求解算法MFLPA步驟如下。

Fig.3 Process of constructing quotient network by contracting sub-network圖3 壓縮子網絡構建商網絡過程

算法3 MFLPA算法

輸入：初始網絡G=(V,E,C)

輸出：初始網絡G=(V,E,C)的最大流

3.3 時間復雜度分析

本文提出的MFLPA算法共分為三部分：標簽傳播劃分子網，構建商網絡（包括判斷子網絡是否滿足壓縮條件和壓縮網絡構建商網絡）以及在商網絡上近似求最大流。

LPA標簽傳播算法的時間復雜度為O(n+m),生成商網絡的時間為O(mn),在商網絡上計算最大流的時間復雜度取決于使用的最大流算法。對于MFLPA-ISAP，時間復雜度T1為：

ISAP算法計算最大流時間復雜度T2為O(n2m)。

下面將討論MFLPA-ISAP相較于ISAP是否具有優(yōu)勢：

（1）如果O(mn)＞O(n′2m′)，則T1＜2O(mn),而在大規(guī)模網絡中情形下，n的數值非常大，因此O(mn)＜＜O(n2m),從而T1＜T2。

（2）如果O(mn)≤O(n′2m′),則因此只要即可保證T1＜T2。其中，和分別為節(jié)點和邊的壓縮率。在AK和GENRMF網絡中，遠遠小于1，所以T1＜T2。

4 實驗結果與分析

4.1 實驗設置

4.1.1 硬件環(huán)境

本文實驗的硬件配置如下：CPU為AMD FX-8300 Eight-Core@3.32 GHz，內存為12 GB，編程環(huán)境為Microsoft Visual Studio。

4.1.2 對比實驗設置

本文選取的對比算法為目前求解最大流高效算法中的ISAP算法和Dinic算法。

MFLPA算法在求解最大流部分依據對比對象進行了不同的設置。

（1）MFLPA-Dinic：MFLPA算法中求解最大流部分使用的最大流算法是Dinic算法。

（2）MFLPA-ISAP：MFLPA算法中求解最大流部分使用的最大流算法是ISAP算法。

在實驗中使用這兩種算法分別與Dinic算法和ISAP算法進行對比實驗，檢測算法性能。

4.1.3 數據來源

本文的實驗數據使用的是Rutgers大學舉辦的DIMACS會議上公布的最大流網絡生成工具[32]，分別是GENRMF網絡生成工具和AK網絡生成工具，它們是世界公認并被廣泛使用的最大流生成工具，這兩個生成工具可以在文獻[33]中下載。

GENRMF：GENRMF網絡生成器由Goldfard和Grigoriadis提出，該網絡生成器可以生成三維格點網絡，具體描述見文獻[34]。

AK：AK網絡生成器由Cherkassky與Goldberg提出，可以用于檢測Dinic算法和預流推進算法。該網絡生成器的具體描述見文獻[34]。

4.1.4 實驗結果衡量指標

本文主要以時間、誤差率er、壓縮率（節(jié)點壓縮率cv，邊壓縮率ce）作為主要性能衡量指標。f為初始網絡最大流；f′為MFLPA算法求解的最大流；n為初始網絡節(jié)點總數；n′為商網絡節(jié)點總數；m為初始網絡邊總數；m′為商網絡邊總數；tI為ISAP算法求解最大流的時間；tD為Dinic算法求解最大流的時間；t′為MFLPA求解最大流的時間；t*為在商網絡上求解最大流時間；誤差率，MFLPA求得的最大流與初始網絡最大流的誤差率；節(jié)點壓縮率；邊壓縮率。

4.2 實驗結果與分析

4.2.1 Dinic與ISAP的實驗對比

在GENRMF網絡與AK網絡分別使用Dinic算法和ISAP算法計算最大流，網絡節(jié)點數為212至218，圖4所示的運行時間為10次運行取平均值。可以看到在AK網絡中隨著節(jié)點數增加Dinic算法取得了更快的結果，而在GENRMF網絡中，ISAP算法表現出更優(yōu)的性能。

Fig.4 Running time of Dinic and ISAP to calculate maximum flow圖4 Dinic與ISAP計算最大流的運行時間

4.2.2 最大迭代次數T對結果的影響

在運行算法1時，需進行多次迭代，而每一次迭代結束都會形成當前迭代次數下不同的子網絡。

本文設置不同的最大迭代次數T進行實驗，研究T對實驗結果的影響。實驗結果表明，MFLPA-Dinic與MFLPA-ISAP在不同的規(guī)模網絡下，當T=5時，實驗結果最優(yōu)。圖5給出了MFLPA-ISAP在節(jié)點數為217的GENRMF網絡下的實驗結果，MFLPA-ISAP求解最大流的時間在T值從1取到4中，呈現陡減趨勢，并在T值為5時達到最低值，而后呈現穩(wěn)步遞增趨勢，因此本文實驗中選取的標簽傳播的最大迭代次數T值為5。

Raghavan[30]經過大量實驗發(fā)現標簽傳播過程只需要經過5次迭代就能完成95%以上節(jié)點的劃分，上述實驗結果印證了Raghavan的結論。

4.2.3 Dinic與MFLPA-Dinic的實驗對比

為了測試MFLPA算法的性能，分別在GENRMF和AK網絡上與Dinic進行對比實驗，均不包含讀網絡到內存的時間，結果見表1和表2。

Fig.5 Running time of different number of iterations in label propagation process in MFLPA-ISAP圖5 MFLPA-ISAP算法中標簽傳播過程的不同迭代次數T下的運行時間

Table 1 Operation results of Dinic and MFLPA-Dinic algorithms in GENRMF network表1 Dinic與MFLPA-Dinic算法在GENRMF網絡的運行結果

Table 2 Operation results of Dinic and MFLPA-Dinic algorithms inAK network表2 Dinic與MFLPA-Dinic算法在AK網絡的運行結果

表1中實驗結果表明，在GENRMF網絡中節(jié)點壓縮率和邊壓縮率平均為77.38%和75.77%，誤差率低于5%。MFLPA-Dinic算法的總時間均低于Dinic算法，如圖6所示，數據集的規(guī)模越大效果越顯著。例如在GENRMF網絡中節(jié)點規(guī)模達到218時，MFLPADinic算法時間是Dinic求解時間的1/15。

表2中結果表明，AK網絡節(jié)點壓縮率和邊壓縮率平均為82.25%和81.08%，并精確計算出最大流值。在AK網絡上MFLPA-Dinic算法時間遠低于Dinic算法，如在節(jié)點數為262 150的AK網絡中，MFLPA-Dinic算法時間是Dinic求解時間的1/74。

4.2.4 ISAP和MFLPA-ISAP對比實驗

同時在GENRMF和AK網絡上與ISAP算法進行對比實驗，結果見表3、表4和圖7。

表3中網絡節(jié)點數大于8 192后MFLPA-ISAP算法的時間復雜度低于ISAP。從表3、表4和圖7中可以看出，在GENRMF和AK網絡中MFLPA-ISAP算法的運行總時間也明顯優(yōu)于ISAP算法。如圖7所示，在網絡規(guī)模急劇增大的情況下其運行時間相較ISAP有明顯優(yōu)勢。

4.2.5 MFLPA誤差分析

根據最大流最小割原理，網絡的最大流等于網絡的最小割，如果在商網絡中原網絡的割邊未被收縮則誤差為0，否則會產生誤差。

Fig.6 Comparison of performance of Dinic and MFLPA-Dinic in two kinds of networks圖6 Dinic和MFLPA-Dinic在兩種網絡下性能的比較

Table 3 Operation results of ISAP and MFLPA-ISAP algorithms in GENRMF network表3 ISAP與MFLPA-ISAP算法在GENRMF網絡的運行結果

Table 4 Operation results of ISAP and MFLPA-ISAP algorithms inAK network表4 ISAP與MFLPA-ISAP算法在AK網絡的運行結果

圖8是一個流網絡示例圖。該網絡的最小割邊為（3,6）、（2,5）和（1,4），在標簽傳播過程結束后，節(jié)點1、4和5可能具有相同標簽值，劃分到同一個子網絡。令A={1,4,5},新建節(jié)點s′、t′構建新子網絡，達到壓縮條件，但是當把A壓縮成一點后，（1,4）這條割邊被壓縮，因此產生了實驗誤差。

5 結束語

最大流問題是一種組合最優(yōu)化的經典問題，在眾多領域中有著十分廣泛的應用，隨著持續(xù)增長的數據造成網絡規(guī)模呈現指數式的攀升，如何降低求解最大流的時間復雜度是一個亟待解決的問題。針對這種現狀，本文提出了一種基于標簽傳播的大規(guī)模網絡最大流計算方法MFLPA。首先，基于標簽傳播將初始網絡劃分成多個子網絡；然后，結合商空間理論將子網絡壓縮成單個節(jié)點并形成規(guī)模較小的商網絡；最后，在商網絡中求解初始網絡的最大流近似解。因為商網絡的規(guī)模很小，所以在誤差允許范圍內極大降低了求解最大流的時間復雜度。

Fig.7 Comparison of performance of ISAP and MFLPA-ISAP in two kinds of networks圖7 ISAP和MFLPA-ISAP在兩種網絡下性能的比較

Fig.8 Flow network sample圖8 流網絡示例圖

本文方法具有普適性，可作為一個簡化大規(guī)模網絡的方法，將原始網絡壓縮為商網絡后，其他任一最大流算法均可通過商網絡估計原始網絡的最大流。

未來的工作將從以下方面展開：

（1）本文從實驗數據中總結出MFLPA的性能指標（網絡壓縮率、商網絡最大流的誤差率），下一步的工作是如何從理論上證明或者探索上述性能指標的上界。

（2）本文方法只對網絡總體進行了一次壓縮，未來的工作將嘗試對初始網絡遞歸地調用本文方法，以多次壓縮后生成的商網絡的最大流估計原始網絡的最大流。從實驗和理論的角度研究網絡的多次壓縮對算法性能指標造成的影響。

[1]Song J,Lee S,Kim J.Spam filtering in Twitter using senderreceiver relationship[C]//LNCS 6961:Proceedings of the 14th International Conference on Recent Advances in Intrusion Detection,Menlo Park,USA,Sep 20-21,2011.Berlin,Heidelberg:Springer,2011:301-317.

[2]Qi Xingqin,Tang Wenliang,Wu Yezhou,et al.Optimal local community detection in social networks based on density drop of subgraphs[J].Pattern Recognition Letters,2014,36(1):46-53.

[3]Fortunato S,Castellano C.Community structure in graphs[M].New York:Springer-Verlag,Inc,2012:490-512.

[4]Saoud Z,Faci N,Maamar Z,et al.Sybil tolerance and probabilistic databases to compute Web services trust[C]//LNCS 9282:Proceedings of the 2015 East European Conference on Advances in Databases and Information Systems,Poitiers,France,Sep 8-11,2015.Berlin,Heidelberg:Springer,2015:458-471.

[5]Tran D N,Min Bonan,Li Jinyang,et al.Sybil-resilient online content voting[C]//Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation,Boston,USA,Apr 22-24,2009.Berkeley,USA:USENIX Association,2009:15-28.

[6]Dantzig G B.Application of the simplex method to a transportation problem[J].Activity Analysis of Production and Allocation,1951:359-373.

[7]Fulkerson D R,Dantzig G B.Computation of maximal flows in networks[J].Naval Research Logistics Quarterly,1955,2(4):277-283.

[8]Ford L R,Fulkerson D R.Maximum flow through a network[J].Canadian Journal of Mathematics,1956,8(5):399-404.

[9]Edmonds J,Karp R M.Theoretical improvements in algorithmic efficiency for network flow problems[J].Journal of theACM,1972,19(2):248-264.

[10]Dinitz E A.Algorithm for solution of a problem of maximum flow in networks with power estimation[J].Soviet Mathematics Doklady,1970,11(5):1277-1280.

[11]Karzanov A V.Determining the maximal flow in a network by the method of preflows[J].Doklady Mathematics,1974,215(1):49-52.

[12]Orlin J B,Ahuja R K.Distance-directed algorithms for maximum flow and parametric maximum flow problems[J].Naval Research Logistics,1991,38(3):413-430.

[13]Eisenstat D,Klein P N.Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs[C]//Proceedings of the 45th Annual ACM Symposium on Theory of Computing,Palo Alto,USA,Jun 1-4,2013.New York:ACM,2013:735-744.

[14]Italiano G F,Nussbaum Y,Sankowski P,et al.Improved algorithms for min cut and max flow in undirected planar graphs[C]//Proceedings of the 43rd ACM Symposium on Theory of Computing,San Jose,USA,Jun 6-8,2011.New York:ACM,2011:313-322.

[15]Orlin J B.Max flows inO(nm)time,or better[C]//Proceedings of the Symposium on Theory of Computing,Palo Alto,USA,Jun 1-4,2013.New York:ACM,2013:765-774.

[16]Xu Ji,Wang Guoyin,Yu Hong.Review of big data processing based on granular computing[J].Chinese Journal of Computers,2015,38(8):1497-1517.

[17]Liers F,Pardella G.Simplifying maximum flow computations:the effect of shrinking and good initial flows[J].DiscreteApplied Mathematics,2011,159(17):2187-2203.

[18]Halim F,Yap R H C,Wu Yongzheng.A MapReduce-based maximum-flow algorithm for large small-world network graphs[C]//Proceedings of the 31st International Conference on Distributed Computing Systems,Minneapolis,USA,Jun 20-24,2011.Washington:IEEE Computer Society,2011:192-202.

[19]Hobbs J R.Granularity[J].Readings in qualitative reasoning About Physical Systems,1990,26(11):542-545.

[20]Zadeh L A.Outline of a new approach to the analysis of complex systems and decision processes[J].IEEE Transactions on Systems,Man&Cybernetics,1973,3(1):28-44.

[21]Zadeh L A.Fuzzy sets[J].Information&Control,1965,8(3):338-353.

[22]Pawlak Z.Rough sets[J].International Journal of Computer&Information Sciences,1982,11(5):41-356.

[23]Zhang Ling,Zhang Bo.Quotient space based problem solving:a theoretical foundation of granular computing[M].Beijing:Tsinghua University Press,2014:1-114.

[24]Zheng Cheng,Zhang Ling.The computation of maximum flow in network analysis based on quotient space theory[J].Chinese Journal of Computers,2015,38(8):1705-1712.

[25]Qian Xuesen,Yu Jingyuan,Dai Ruwei.Anew field of scienceopen complex giant system and its methodology[J].Chinese Journal of Nature,1990(1):3-10.

[26]Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.

[27]Li Zhenping,Zhang Shihua,Wang Ruisheng,et al.Erratum:quantitative function for community detection[J].Physical Review E,2015,91(1):2278-2309.

[28]Sun Yueheng,Zhang Shuo,Ruan Xingmao.Community detection of complex networks based on the spectrum optimization algorithm[C]//Proceedings of the 2nd International Conference on Software Engineering,Knowledge Engineering and Information Engineering,Singapore,Aug 5-6,2014.Washington:IEEE Computer Society,2014:1127-1146.

[29]Rosvall M,Bergstrom C T.Maps of random walks on complex networks reveal community structure[J].Proceedings of the National Academy of Sciences of the United States ofAmerica,2007,105(4):1118-1123.

[30]Raghavan U N,Albert R,Kumara S.Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2007,76(3):036106.

[31]Luo Zhigang,Ding Fan,Jiang Xiaozhou,et al.New progress community detection in complex networks[J].Journal of National University of Defense Technology,2011,33(1):47-52.

[32]Kovács P.Minimum-cost flow algorithms:an experimentalevaluation[J].Optimization Methods&Software,2015,30(1):94-127.

[33]The first DIMACS international algorithm implementation challenge:the core experiments[EB/OL].(1990)[2016-07-21].ftp://dimacs.rutgers.edu/pub/net fl ow/general-info/core.tex.

[34]Buzdalov M,Shalyto A.Hard test generation for augmenting path maximum flow algorithms using genetic algorithms:revisited[C]//Proceedings of the Congress on Evolutionary Computation,Sendai,Japan,May 25-28,2015.Washington:IEEE Computer Society,2015:2124-2128.

附中文參考文獻：

[16]徐計,王國胤,于洪.基于粒計算的大數據處理[J].計算機學報,2015,38(8):1497-1517.

[23]張鈴,張鈸.基于商空間的問題求解:粒度計算的理論基礎[M].北京:清華大學出版社,2014:1-114.

[24]鄭誠,張鈴.網絡分析中求最大流的商空間方法[J].計算機學報,2015,38(8):1705-1712.

[25]錢學森,于景元,戴汝為.一個科學新領域——開放的復雜巨系統及其方法論[J].自然雜志,1990(1):3-10.

[31]駱志剛,丁凡,蔣曉舟,等.復雜網絡社區(qū)發(fā)現算法研究新進展[J].國防科技大學學報,2011,33(1):47-52.

Method of Solving Maximum Flow Problem in Large-Scale Network Based on Label Propagation*

WEI Huazhen1,2,ZHAO Shu1,2+,CHEN Jie1,2,ZHANG Yiwen1,2,ZHANG Yanping1,2
1.School of Computer Science&Technology,Anhui University,Hefei 230601,China
2.Center of Information Support&Assurance Technology,Anhui University,Hefei 230601,China

A

TP301.6

+Corresponding author:E-mail:zhaoshuzs2002@hotmail.com

WEI Huazhen,ZHAO Shu,CHEN Jie,et al.Method of solving maximum flow problem in large-scale network based on label propagation.Journal of Frontiers of Computer Science and Technology,2017,11(10)：1609-1620.

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2017/11(10)-1609-12

10.3778/j.issn.1673-9418.1609007

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

*The National Natural Science Foundation of China under Grant Nos.61402006,61175046(國家自然科學基金);the National High Technology Research and Development Program of China under Grant No.2015AA124102(國家高技術研究發(fā)展計劃(863計劃));the Natural Science Foundation of Anhui Higher Education Institutions under Grant No.KJ2013A016(安徽省高等學校省級自然科學研究項目);the Natural Science Foundation ofAnhui Province under Grant No.1508085MF113(安徽省自然科學基金);the Scientific Research Foundation for the Returned Overseas Chinese Scholars,State Education Ministry(教育部留學回國人員科研啟動基金);the High Level Talent Demand Project ofAnhui University(安徽大學高層次人才需求計劃項目).

Received 2016-08,Accepted 2016-10.

CNKI網絡優(yōu)先出版:2016-10-31,http://www.cnki.net/kcms/detail/11.5602.TP.20161031.1650.018.html

WEI Huazhen was born in 1992.She is an M.S.candidate at Department of Computer Science,Anhui University.Her research interests include intelligent computing and machine learning,etc.

魏華珍（1992—），女，浙江余姚人，安徽大學計算機應用專業(yè)碩士研究生，主要研究領域為智能計算，機器學習等。

ZHAO Shu was born in 1979.She received the Ph.D.degree in intelligent computing from Anhui University in 2007.Now she is a professor at Anhui University.Her research interests include machine learning,social networks and intelligent computing,etc.

趙姝（1979—），女，安徽巢湖人，2007年于安徽大學獲得博士學位，現為安徽大學教授，主要研究領域為機器學習，社交網絡，智能計算等。已授權專利1項，獲軟件著作權3項，發(fā)表學術論文20余篇。

CHEN Jie was born in 1982.She received the Ph.D.degree in intelligent computing from Anhui University in 2014.Now she is a lecturer at Anhui University.Her research interests include intelligent computing and machine learning,etc.

陳潔（1982—），女，安徽巢湖人，2014年于安徽大學獲得博士學位，現為安徽大學講師，主要研究領域為智能計算，機器學習等。發(fā)表學術論文10余篇。

ZHANG Yiwen was born in 1976.He received the Ph.D.degree in management science and engineering from Hefei University of Technology in 2013.Now he is an associate professor at School of Computer Science and Technology,Anhui University.His research interests include service computing,cloud computing and e-commerce intelligence,etc.

張以文（1976—），男，安徽馬鞍山人，2013年于合肥工業(yè)大學獲得博士學位，現為安徽大學副教授，主要研究領域為服務計算，云計算，商務智能等。發(fā)表學術論文30余篇，主持參與國家級、省部級項目10余項。

ZHANG Yanping was born in 1962.She received the Ph.D.degree from Anhui University in 2003.Now she is a professor at Anhui University.Her research interests granular computing,intelligent computing,quotient space theory and machine learning,etc.

張燕平（1962—），女，安徽巢湖人，2003年于安徽大學獲得博士學位，現為安徽大學教授，主要研究領域為粒計算，智能計算，商空間理論，機器學習等。獲發(fā)明專利2項，發(fā)表學術論文80多篇，主持參與國家級、省部級項目10余項。