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

1.安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601

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

基于標(biāo)簽傳播的大規(guī)模網(wǎng)絡(luò)最大流求解方法*

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

1.安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601

2.安徽大學(xué) 信息保障技術(shù)協(xié)同創(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

針對(duì)大數(shù)據(jù)時(shí)代背景下，對(duì)海量數(shù)據(jù)的高效智能處理方式的需求，提出了一種簡化大規(guī)模網(wǎng)絡(luò)求解最大流的方法MFLPA（maximum flow based on label propagation algorithm）?；跇?biāo)簽傳播將初始有向網(wǎng)絡(luò)劃分成多個(gè)子網(wǎng)絡(luò)；結(jié)合商空間理論通過計(jì)算將子網(wǎng)絡(luò)壓縮成單個(gè)節(jié)點(diǎn)，形成規(guī)模較小的商網(wǎng)絡(luò)；最后，在商網(wǎng)絡(luò)中求解初始網(wǎng)絡(luò)的近似優(yōu)解，有效降低了計(jì)算復(fù)雜性。實(shí)驗(yàn)結(jié)果表明，MFLPA在不同網(wǎng)絡(luò)上運(yùn)行速度均比ISAP（improved shortest augument path）和Dinic有顯著提升，效果隨著網(wǎng)絡(luò)規(guī)模的增大而越顯著，縮小網(wǎng)絡(luò)規(guī)模達(dá)到70%以上，實(shí)驗(yàn)誤差不超過5%。

最大流；標(biāo)簽傳播；大規(guī)模網(wǎng)絡(luò)；商空間；簡化網(wǎng)絡(luò)

1 引言

最大流問題是一種組合最優(yōu)化的經(jīng)典問題，在圖論領(lǐng)域有非常重要的研究意義。現(xiàn)代社會(huì)的方方面面都可能是復(fù)雜的網(wǎng)絡(luò)系統(tǒng)，其結(jié)構(gòu)或元素間復(fù)雜的拓?fù)湫畔⒍伎梢猿橄蟪删W(wǎng)絡(luò)中的節(jié)點(diǎn)及邊，比如萬維網(wǎng)、交通網(wǎng)、電力網(wǎng)、信息網(wǎng)、社交網(wǎng)等。在實(shí)際網(wǎng)絡(luò)問題中，最大流問題的目的是求解一個(gè)有容量限制的網(wǎng)絡(luò)中源點(diǎn)可傳輸?shù)絽R點(diǎn)的最大流量，并確定其傳輸策略，使得網(wǎng)絡(luò)充分發(fā)揮其運(yùn)載能力，資源的調(diào)度達(dá)到最優(yōu)狀態(tài)。

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

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

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

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

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

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

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

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

本文組織結(jié)構(gòu)如下：第2章介紹與本文相關(guān)的基本概念和定義；第3章對(duì)MFLPA進(jìn)行詳述；第4章使用公用最大流網(wǎng)絡(luò)生成工具得出實(shí)驗(yàn)結(jié)果，并對(duì)不同結(jié)果進(jìn)行分析和討論；第5章對(duì)全文進(jìn)行總結(jié)和展望。

2 基本概念及相關(guān)定義

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

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

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

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

定義5[23]（商網(wǎng)絡(luò)）對(duì)于流網(wǎng)絡(luò)G(V,E,C)，給定V上的一個(gè)等價(jià)關(guān)系R，則[V]代表節(jié)點(diǎn)集合V對(duì)應(yīng)等價(jià)關(guān)系R的商集，定義?[v],[w]∈[V],([v],[w])∈[E]?v∈[v],w∈[w],(v,w)∈E,且這樣得到的新網(wǎng)絡(luò)G([V],[E],[C])稱為原流網(wǎng)絡(luò)對(duì)應(yīng)于等價(jià)關(guān)系R的商網(wǎng)絡(luò)。

3 MFLPA算法描述

3.1 算法框架

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

3.2 算法詳述

MFLPA算法包含三部分：基于標(biāo)簽傳播劃分子網(wǎng)絡(luò)，壓縮判定條件的確立，壓縮網(wǎng)絡(luò)并構(gòu)建商網(wǎng)絡(luò)。下面將展開進(jìn)行描述。

3.2.1 基于標(biāo)簽傳播劃分子網(wǎng)絡(luò)

MFLPA算法首先基于標(biāo)簽傳播理論[30]劃分子網(wǎng)絡(luò)，為網(wǎng)絡(luò)G(V,E,C)的所有節(jié)點(diǎn)指派唯一的初始標(biāo)簽（如一個(gè)整數(shù)），標(biāo)簽作為子網(wǎng)絡(luò)的唯一標(biāo)識(shí)，標(biāo)記節(jié)點(diǎn)所屬子網(wǎng)絡(luò)。

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

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

算法1基于標(biāo)簽傳播劃分子網(wǎng)絡(luò)算法

輸入：初始網(wǎng)絡(luò)G=(V,E,C)

輸出：子網(wǎng)絡(luò)節(jié)點(diǎn)集合{Vgi|i=1,2,…}

3.2.2 壓縮判定條件的確立

在找到所有子網(wǎng)絡(luò)gv之后，需要對(duì)其中合適的子網(wǎng)絡(luò)壓縮，但并不是所有子網(wǎng)絡(luò)結(jié)構(gòu)都適合壓縮，不適當(dāng)?shù)膲嚎s則會(huì)很大程度地影響最大流的求解結(jié)果。

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

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

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

算法2構(gòu)建新子網(wǎng)絡(luò)算法

輸入：子網(wǎng)絡(luò)gv

輸出：新子網(wǎng)絡(luò)g′v

由算法2得到添加了虛擬節(jié)點(diǎn)s′和t′以及與其相關(guān)聯(lián)邊的新子網(wǎng)絡(luò)g′v。

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

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

Fig.2 Process of constructing new sub-network based on labela圖2 標(biāo)簽a劃分的子網(wǎng)絡(luò)構(gòu)建新子網(wǎng)絡(luò)過程

3.2.3 壓縮網(wǎng)絡(luò)并構(gòu)建商網(wǎng)絡(luò)

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

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

圖3所示為壓縮子網(wǎng)絡(luò)構(gòu)建商網(wǎng)絡(luò)過程的例子。圖3（a）中(a,1)和(1,a)這兩條邊為平行邊，合并后為圖3（b）中(1,a)。圖3（b）為由圖2（a）中標(biāo)簽a劃分的子網(wǎng)絡(luò)進(jìn)行壓縮操作后得到的簡化網(wǎng)絡(luò)。

基于標(biāo)簽傳播的大規(guī)模網(wǎng)絡(luò)最大流求解算法MFLPA步驟如下。

Fig.3 Process of constructing quotient network by contracting sub-network圖3 壓縮子網(wǎng)絡(luò)構(gòu)建商網(wǎng)絡(luò)過程

算法3 MFLPA算法

輸入：初始網(wǎng)絡(luò)G=(V,E,C)

輸出：初始網(wǎng)絡(luò)G=(V,E,C)的最大流

3.3 時(shí)間復(fù)雜度分析

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

LPA標(biāo)簽傳播算法的時(shí)間復(fù)雜度為O(n+m),生成商網(wǎng)絡(luò)的時(shí)間為O(mn),在商網(wǎng)絡(luò)上計(jì)算最大流的時(shí)間復(fù)雜度取決于使用的最大流算法。對(duì)于MFLPA-ISAP，時(shí)間復(fù)雜度T1為：

ISAP算法計(jì)算最大流時(shí)間復(fù)雜度T2為O(n2m)。

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)設(shè)置

4.1.1 硬件環(huán)境

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

4.1.2 對(duì)比實(shí)驗(yàn)設(shè)置

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

MFLPA算法在求解最大流部分依據(jù)對(duì)比對(duì)象進(jìn)行了不同的設(shè)置。

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

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

在實(shí)驗(yàn)中使用這兩種算法分別與Dinic算法和ISAP算法進(jìn)行對(duì)比實(shí)驗(yàn)，檢測算法性能。

4.1.3 數(shù)據(jù)來源

本文的實(shí)驗(yàn)數(shù)據(jù)使用的是Rutgers大學(xué)舉辦的DIMACS會(huì)議上公布的最大流網(wǎng)絡(luò)生成工具[32]，分別是GENRMF網(wǎng)絡(luò)生成工具和AK網(wǎng)絡(luò)生成工具，它們是世界公認(rèn)并被廣泛使用的最大流生成工具，這兩個(gè)生成工具可以在文獻(xiàn)[33]中下載。

GENRMF：GENRMF網(wǎng)絡(luò)生成器由Goldfard和Grigoriadis提出，該網(wǎng)絡(luò)生成器可以生成三維格點(diǎn)網(wǎng)絡(luò)，具體描述見文獻(xiàn)[34]。

AK：AK網(wǎng)絡(luò)生成器由Cherkassky與Goldberg提出，可以用于檢測Dinic算法和預(yù)流推進(jìn)算法。該網(wǎng)絡(luò)生成器的具體描述見文獻(xiàn)[34]。

4.1.4 實(shí)驗(yàn)結(jié)果衡量指標(biāo)

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

4.2 實(shí)驗(yàn)結(jié)果與分析

4.2.1 Dinic與ISAP的實(shí)驗(yàn)對(duì)比

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

Fig.4 Running time of Dinic and ISAP to calculate maximum flow圖4 Dinic與ISAP計(jì)算最大流的運(yùn)行時(shí)間

4.2.2 最大迭代次數(shù)T對(duì)結(jié)果的影響

在運(yùn)行算法1時(shí)，需進(jìn)行多次迭代，而每一次迭代結(jié)束都會(huì)形成當(dāng)前迭代次數(shù)下不同的子網(wǎng)絡(luò)。

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

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

4.2.3 Dinic與MFLPA-Dinic的實(shí)驗(yàn)對(duì)比

為了測試MFLPA算法的性能，分別在GENRMF和AK網(wǎng)絡(luò)上與Dinic進(jìn)行對(duì)比實(shí)驗(yàn)，均不包含讀網(wǎng)絡(luò)到內(nèi)存的時(shí)間，結(jié)果見表1和表2。

Fig.5 Running time of different number of iterations in label propagation process in MFLPA-ISAP圖5 MFLPA-ISAP算法中標(biāo)簽傳播過程的不同迭代次數(shù)T下的運(yùn)行時(shí)間

Table 1 Operation results of Dinic and MFLPA-Dinic algorithms in GENRMF network表1 Dinic與MFLPA-Dinic算法在GENRMF網(wǎng)絡(luò)的運(yùn)行結(jié)果

Table 2 Operation results of Dinic and MFLPA-Dinic algorithms inAK network表2 Dinic與MFLPA-Dinic算法在AK網(wǎng)絡(luò)的運(yùn)行結(jié)果

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

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

4.2.4 ISAP和MFLPA-ISAP對(duì)比實(shí)驗(yàn)

同時(shí)在GENRMF和AK網(wǎng)絡(luò)上與ISAP算法進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果見表3、表4和圖7。

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

4.2.5 MFLPA誤差分析

根據(jù)最大流最小割原理，網(wǎng)絡(luò)的最大流等于網(wǎng)絡(luò)的最小割，如果在商網(wǎng)絡(luò)中原網(wǎng)絡(luò)的割邊未被收縮則誤差為0，否則會(huì)產(chǎn)生誤差。

Fig.6 Comparison of performance of Dinic and MFLPA-Dinic in two kinds of networks圖6 Dinic和MFLPA-Dinic在兩種網(wǎng)絡(luò)下性能的比較

Table 3 Operation results of ISAP and MFLPA-ISAP algorithms in GENRMF network表3 ISAP與MFLPA-ISAP算法在GENRMF網(wǎng)絡(luò)的運(yùn)行結(jié)果

Table 4 Operation results of ISAP and MFLPA-ISAP algorithms inAK network表4 ISAP與MFLPA-ISAP算法在AK網(wǎng)絡(luò)的運(yùn)行結(jié)果

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

5 結(jié)束語

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

Fig.7 Comparison of performance of ISAP and MFLPA-ISAP in two kinds of networks圖7 ISAP和MFLPA-ISAP在兩種網(wǎng)絡(luò)下性能的比較

Fig.8 Flow network sample圖8 流網(wǎng)絡(luò)示例圖

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

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

（1）本文從實(shí)驗(yàn)數(shù)據(jù)中總結(jié)出MFLPA的性能指標(biāo)（網(wǎng)絡(luò)壓縮率、商網(wǎng)絡(luò)最大流的誤差率），下一步的工作是如何從理論上證明或者探索上述性能指標(biāo)的上界。

（2）本文方法只對(duì)網(wǎng)絡(luò)總體進(jìn)行了一次壓縮，未來的工作將嘗試對(duì)初始網(wǎng)絡(luò)遞歸地調(diào)用本文方法，以多次壓縮后生成的商網(wǎng)絡(luò)的最大流估計(jì)原始網(wǎng)絡(luò)的最大流。從實(shí)驗(yàn)和理論的角度研究網(wǎng)絡(luò)的多次壓縮對(duì)算法性能指標(biāo)造成的影響。

[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.

附中文參考文獻(xiàn)：

[16]徐計(jì),王國胤,于洪.基于粒計(jì)算的大數(shù)據(jù)處理[J].計(jì)算機(jī)學(xué)報(bào),2015,38(8):1497-1517.

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

[24]鄭誠,張鈴.網(wǎng)絡(luò)分析中求最大流的商空間方法[J].計(jì)算機(jī)學(xué)報(bào),2015,38(8):1705-1712.

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

[31]駱志剛,丁凡,蔣曉舟,等.復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法研究新進(jìn)展[J].國防科技大學(xué)學(xué)報(bào),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(國家自然科學(xué)基金);the National High Technology Research and Development Program of China under Grant No.2015AA124102(國家高技術(shù)研究發(fā)展計(jì)劃(863計(jì)劃));the Natural Science Foundation of Anhui Higher Education Institutions under Grant No.KJ2013A016(安徽省高等學(xué)校省級(jí)自然科學(xué)研究項(xiàng)目);the Natural Science Foundation ofAnhui Province under Grant No.1508085MF113(安徽省自然科學(xué)基金);the Scientific Research Foundation for the Returned Overseas Chinese Scholars,State Education Ministry(教育部留學(xué)回國人員科研啟動(dòng)基金);the High Level Talent Demand Project ofAnhui University(安徽大學(xué)高層次人才需求計(jì)劃項(xiàng)目).

Received 2016-08,Accepted 2016-10.

CNKI網(wǎng)絡(luò)優(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—），女，浙江余姚人，安徽大學(xué)計(jì)算機(jī)應(yīng)用專業(yè)碩士研究生，主要研究領(lǐng)域?yàn)橹悄苡?jì)算，機(jī)器學(xué)習(xí)等。

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年于安徽大學(xué)獲得博士學(xué)位，現(xiàn)為安徽大學(xué)教授，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，社交網(wǎng)絡(luò)，智能計(jì)算等。已授權(quán)專利1項(xiàng)，獲軟件著作權(quán)3項(xiàng)，發(fā)表學(xué)術(shù)論文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年于安徽大學(xué)獲得博士學(xué)位，現(xiàn)為安徽大學(xué)講師，主要研究領(lǐng)域?yàn)橹悄苡?jì)算，機(jī)器學(xué)習(xí)等。發(fā)表學(xué)術(shù)論文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è)大學(xué)獲得博士學(xué)位，現(xiàn)為安徽大學(xué)副教授，主要研究領(lǐng)域?yàn)榉?wù)計(jì)算，云計(jì)算，商務(wù)智能等。發(fā)表學(xué)術(shù)論文30余篇，主持參與國家級(jí)、省部級(jí)項(xiàng)目10余項(xiàng)。

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年于安徽大學(xué)獲得博士學(xué)位，現(xiàn)為安徽大學(xué)教授，主要研究領(lǐng)域?yàn)榱Ｓ?jì)算，智能計(jì)算，商空間理論，機(jī)器學(xué)習(xí)等。獲發(fā)明專利2項(xiàng)，發(fā)表學(xué)術(shù)論文80多篇，主持參與國家級(jí)、省部級(jí)項(xiàng)目10余項(xiàng)。