基于标签传播的大规模网络最大流求解方法*

魏华珍，赵 姝+，陈 洁，张以文，张燕平

1.安徽大学 计算机科学与技术学院，合肥 230601

2.安徽大学 信息保障技术协同创新中心，合肥 230601

基于标签传播的大规模网络最大流求解方法*

魏华珍1,2，赵 姝1,2+，陈 洁1,2，张以文1,2，张燕平1,2

1.安徽大学 计算机科学与技术学院，合肥 230601

2.安徽大学 信息保障技术协同创新中心，合肥 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

针对大数据时代背景下，对海量数据的高效智能处理方式的需求，提出了一种简化大规模网络求解最大流的方法MFLPA（maximum flow based on label propagation algorithm）。基于标签传播将初始有向网络划分成多个子网络；结合商空间理论通过计算将子网络压缩成单个节点，形成规模较小的商网络；最后，在商网络中求解初始网络的近似优解，有效降低了计算复杂性。实验结果表明，MFLPA在不同网络上运行速度均比ISAP（improved shortest augument path）和Dinic有显著提升，效果随着网络规模的增大而越显著，缩小网络规模达到70%以上，实验误差不超过5%。

最大流；标签传播；大规模网络；商空间；简化网络

1 引言

最大流问题是一种组合最优化的经典问题，在图论领域有非常重要的研究意义。现代社会的方方面面都可能是复杂的网络系统，其结构或元素间复杂的拓扑信息都可以抽象成网络中的节点及边，比如万维网、交通网、电力网、信息网、社交网等。在实际网络问题中，最大流问题的目的是求解一个有容量限制的网络中源点可传输到汇点的最大流量，并确定其传输策略，使得网络充分发挥其运载能力，资源的调度达到最优状态。

随着信息时代的发展，除了解决实际网络中的通信流量分配、交通运输路线分配之外，最大流问题在从互联网获取海量图信息的背景下也有了其他应用，如发现垃圾邮件网站[1]，社区结构发现[2-3]，P2P网络中防止Sybil攻击[4]，网络计票[5]等。最大流问题是线性规划问题之一，研究最大流可以得到网络中特定条件下的组合最优解。

对于最大流问题的研究已有60多年的发展历史，从Dantzig[6]提出了网络单纯形法开始，Fulkerson等人在最大流问题中首次使用图方法[7]，随后由Ford和Fulkerson提出了经典的增广路径算法[8]。由此学者们纷纷提出了许多出色的改进算法，Edmonds[9]和Dinitz[10]等人引入最短增广路径算法把Ford-Fulkerson算法变为强多项式，而后Karzanov得出预流推进算法[11]，Ahuja和 Orlin 提出了 ISAP（improved shortest augument path）算法，其充分地利用距离标号的作用，提高了算法效率[12]。为了满足各种网络的需求，近年来学者们提出了许多新算法，如针对平面图[13-14]以及稀疏网络[15]的算法等。

然而持续增长的数据造成网络规模呈现指数式的攀升，网络中的节点数量已经早已不是几百几千个节点，而常常是以千万计或者以亿计，所对应的图的规模也急剧扩大。在这个背景下虽然经典及其改进算法仍被广泛应用，但已无法满足规模日益增长的网络的需求，需要有新的应对策略与求解方案[16]。针对大规模网络最大流问题，Liers与Pardella[17]提出SME（shrink max edge）方法。这种方法通过压缩最大容量边达到减小网络规模的目的，但只对初始网络粗略简化，不能大规模地降低网络的规模，并且这种简化方法对于很多网络是不适用的。当前对于大规模网络数据的处理大多采用并行计算[18]的求解策略。这种方法可以很好地提高大规模网络最大流的求解速度，但需要先对问题有个合适的划分，并且分布式算法复杂且灵活。综上，目前需要一个简单易行的方法去满足大规模网络数据带来的多样性需求[16]。

面对大量复杂的信息，人类智能与计算机处理问题不同之处在于，人类既可以从宏观俯瞰全局，也能从微观进行细节分析[19]，正是这种对问题宏观层次与微观层次相结合的思考方式使得人类智能能够把复杂的问题简单化、抽象化，使其变为一个易解决与计算的问题[20]。而人工智能领域的粒计算正是研究模拟人类智能思考与解决大规模复杂问题的理论。

粒计算主要包含Zadeh[21]提出的模糊集模型、Pawlak[22]提出的粗糙集模型以及Zhang等人[23]提出的商空间模型，它通过将复杂信息进行粒化操作,用粒子代替原大规模样本作为计算单元,并将复杂问题转化到不同粒度空间上进行分析，对各个粒解进行合成得到原问题的最优近似解，适用于近似求解有层次结构的问题，以达到简化问题规模，提高求解效率的目的[24]。Qian等人曾指出[25]“任何一个复杂系统都是具有层次结构的系统”，因此对于大规模网络而言，其本身也应该具有层次结构，适于使用商空间模型进行求解。

在使用商空间模型简化大规模网络的时候，最重要的问题是把什么样的结构粒化，看作一个粒子。随着研究人员对网络性质的深入探索，发现许多网络都存在一种共同的结构——社区结构。复杂网络往往由许多个“群”组成，单个“群”的内部节点呈现较为紧密的聚集性，而群与群之间的连结则相对分散和稀疏[26]。网络中这样的结构可以天然地作为粒子，同时社区结构内部的节点可以看作具有相同等价关系的节点集合。

目前有很多种方法可以发现网络中的社区结构，其中典型方法有模块度优化方法[27]、谱分析法[28]、信息论方法[29]、标签传播方法[30]等。本文旨将社区发现应用到最大流问题中，因此需要寻找的社区结构应该是非重叠的，方便后续结合商空间理论对粒子进行合并计算，但不需要对网络进行非常精确的社区划分。而标签传播方法最大的优点在于不需要任何参数输入，比如社区的数目、大小等，算法收敛速度非常快，它不但拥有极低的线性时间复杂度，同时可以很好地保持图的社区结构，适用于大规模网络图的社区划分[31]。

因此，本文提出一种简化大规模网络求解最大流的方法MFLPA（maximum flow based on label propagation algorithm）。首先基于标签传播将初始网络划分成不同的子网络，接着结合商空间理论对大规模网络进行简化，使得最大流算法能够在简化后的商网络上快速求解。

本文组织结构如下：第2章介绍与本文相关的基本概念和定义；第3章对MFLPA进行详述；第4章使用公用最大流网络生成工具得出实验结果，并对不同结果进行分析和讨论；第5章对全文进行总结和展望。

2 基本概念及相关定义

定义1[8]（流网络）设给定一个流网络G(V,E,C),其中V表示网络中节点构成的节点集合，E是网络中的边集合，C代表容量集合。流网络中每条边都有一个非负容量，若网络中任意节点v∈V,w∈V，则(v,w)代表从节点v流向w的边，容量为c(v,w),由于流网络是有向网络，(w,v)代表从节点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]（流差）对于子网络任一节点x∈X,设定参数属性finside、foutside，xfinside代表网络中除X节点集之外的节点流入节点x的流量和，表示公式为即代表网络中除了X节点集合之外的节点流出节点v的流量和。定义γx为流差，代表流进流出x的差值。

定义5[23]（商网络）对于流网络G(V,E,C)，给定V上的一个等价关系R，则[V]代表节点集合V对应等价关系R的商集，定义∀[v],[w]∈[V],([v],[w])∈[E]⇔v∈[v],w∈[w],(v,w)∈E,且这样得到的新网络G([V],[E],[C])称为原流网络对应于等价关系R的商网络。

3 MFLPA算法描述

3.1 算法框架

本文提出的简化大规模网络求解最大流的方法MFLPA的基本思想为：基于标签传播对大规模有向流网络G(V,E,C)划分成不同子网络；随后确立压缩判定条件对子网络进行筛选，满足条件的子网络中的每个子网络内部节点具有等价关系R,将处于同一子网络中具有等价关系R的节点压缩成为一个节点，以此来构建规模较小的商网络G([V],[E],[C]),从而达到简化网络的目的；最后在商网络上使用ISAP（Dinic）算法求得初始网络最大流的近似优解。

3.2 算法详述

MFLPA算法包含三部分：基于标签传播划分子网络，压缩判定条件的确立，压缩网络并构建商网络。下面将展开进行描述。

3.2.1 基于标签传播划分子网络

MFLPA算法首先基于标签传播理论[30]划分子网络，为网络G(V,E,C)的所有节点指派唯一的初始标签（如一个整数），标签作为子网络的唯一标识，标记节点所属子网络。

设拥有n个邻居节点的节点x的标签为l(x),N(x)表示这n个邻居节点的节点集合，t代表迭代次数。在每一步迭代中，网络中的节点被随机排列后放入一个节点序列，随后按照节点序列中的顺序，对其中的每个节点x,将自身标签更新为其邻居节点集N(x)中出现频数最多的标签MaxLabel。如果存在多个标签其出现频数均为最多，则随机选取其中一个，并用这个标签更新自身原有标签。在若干次迭代后，如果每个节点具有的标签都是其邻居节点中出现频数最多的标签，则停止，否则继续迭代过程。最后，具有相同标签的节点归为同一个子网络，对流网络进行一个划分，得到子网络节点集合{Vgi|i=1,2,…}。在网络中，紧密相连的节点会快速收敛于同一标签，如图1所示。

Fig.1 Because of high density of edges,5 nodes acquire same labela图1 紧密相连的节点1～5收敛于同一标签a

算法1基于标签传播划分子网络算法

输入：初始网络G=(V,E,C)

输出：子网络节点集合{Vgi|i=1,2,…}

3.2.2 压缩判定条件的确立

在找到所有子网络gv之后，需要对其中合适的子网络压缩，但并不是所有子网络结构都适合压缩，不适当的压缩则会很大程度地影响最大流的求解结果。

首先需要确立判断子网络能否被压缩的条件，满足压缩判定条件的每个子网络的内部节点看作具有等价关系R的集合。由网络流理论[8]可知，流网络中的中间节点既不产生多余流量也不滞留经流的流量。经过对网络流性质的研究和实验发现，划分得到的某一子网络，若外部流入到该子网络中每个节点的流量能从它本身或者子网络任一节点流出，则满足这样条件的子网络就可以被压缩。

由于网络中除去源点s和汇点t之外的所有节点都属于中间节点，这一条件相当于微观流网络中间节点的中转理论延伸到宏观的子网络整体上的应用，这里的整个子网络相当于初始网络中既不产生多余流量也不滞留过境的流量的中间节点。同时经过大量实验验证，该条件的确立虽然无法完全避免压缩掉含有最小割边的子网络，但是可以尽量减少这种情况的发生。

判断子网络能否被压缩首先需要由子网络gv构建新子网络g′v，便于压缩条件的判断。设子网络gv={Vgi,Egi},Egi={(e1,e2)∈Egi|e1,e2∈Vgi},构建的算法如下。

算法2构建新子网络算法

输入：子网络gv

输出：新子网络g′v

由算法2得到添加了虚拟节点s′和t′以及与其相关联边的新子网络g′v。

假设X是Vgi中的某个节点集合，x是X中的任一节点，计算X集合的新子网络最大流MFG(X),若代表由s′流出的边都是饱和边，且这些流量都能从t′流出，满足压缩判定条件。

图2（a）到（c）所示的是标签a划分的子网络构建新子网络过程的例子。其中图2（a）代表网络的初始状态，节点a1～a5代表由算法1基于标签传播划分得到的一个子网络所包含的节点，节点1～9代表与该子网络有边连接的子网络外部节点。图2（b）建立新的节点s′、t′,并分别计算节点集A={a1,a2,a3,a4,a5}中每个节点的流入流出差值γ，由算法2构建与节点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求解最大流并进行压缩条件判定，满足条件的子网络中的每个子网络内部节点看作具有等价关系R。根据商空间理论[23]，具有等价关系R的节点集合可被压缩成为一个节点，把满足条件的每个子网络节点集合分别进行压缩处理。

具体操作是：假设X为满足压缩条件的某个子网络节点集合，首先将X替换为单个节点x，并将X集合内部节点之间相互连接的边E(X)全部删除，E(X)={x1∈X,x2∈X|(x1,x2)∈E}，而子网络节点集合X与外部节点v∈(V-X)连接的边，替换为单个节点x与外部节点v∈(V-X)连接的边；随后对所有平行边进行合并操作，合并之后使得x与任一外部节点v∈(V-X)连接的同一方向的边至多只有一条。完成所有压缩操作之后，形成了商网络G([V],[E],[C]),网络规模和结构复杂度都大大减小，最后在商网络上使用最大流算法对网络求得最大流的近似解。

图3所示为压缩子网络构建商网络过程的例子。图3（a）中(a,1)和(1,a)这两条边为平行边，合并后为图3（b）中(1,a)。图3（b）为由图2（a）中标签a划分的子网络进行压缩操作后得到的简化网络。

基于标签传播的大规模网络最大流求解算法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是否具有优势：

（1）如果O(mn)＞O(n′2m′)，则T1＜2O(mn),而在大规模网络中情形下，n的数值非常大，因此O(mn)＜＜O(n2m),从而T1＜T2。

（2）如果O(mn)≤O(n′2m′),则因此只要即可保证T1＜T2。其中，和分别为节点和边的压缩率。在AK和GENRMF网络中，远远小于1，所以T1＜T2。

4 实验结果与分析

4.1 实验设置

4.1.1 硬件环境

本文实验的硬件配置如下：CPU为AMD FX-8300 Eight-Core@3.32 GHz，内存为12 GB，编程环境为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、压缩率（节点压缩率cv，边压缩率ce）作为主要性能衡量指标。f为初始网络最大流；f′为MFLPA算法求解的最大流；n为初始网络节点总数；n′为商网络节点总数；m为初始网络边总数；m′为商网络边总数；tI为ISAP算法求解最大流的时间；tD为Dinic算法求解最大流的时间；t′为MFLPA求解最大流的时间；t*为在商网络上求解最大流时间；误差率，MFLPA求得的最大流与初始网络最大流的误差率；节点压缩率；边压缩率。

4.2 实验结果与分析

4.2.1 Dinic与ISAP的实验对比

在GENRMF网络与AK网络分别使用Dinic算法和ISAP算法计算最大流，网络节点数为212至218，图4所示的运行时间为10次运行取平均值。可以看到在AK网络中随着节点数增加Dinic算法取得了更快的结果，而在GENRMF网络中，ISAP算法表现出更优的性能。

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在不同的规模网络下，当T=5时，实验结果最优。图5给出了MFLPA-ISAP在节点数为217的GENRMF网络下的实验结果，MFLPA-ISAP求解最大流的时间在T值从1取到4中，呈现陡减趋势，并在T值为5时达到最低值，而后呈现稳步递增趋势，因此本文实验中选取的标签传播的最大迭代次数T值为5。

Raghavan[30]经过大量实验发现标签传播过程只需要经过5次迭代就能完成95%以上节点的划分，上述实验结果印证了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网络中节点压缩率和边压缩率平均为77.38%和75.77%，误差率低于5%。MFLPA-Dinic算法的总时间均低于Dinic算法，如图6所示，数据集的规模越大效果越显著。例如在GENRMF网络中节点规模达到218时，MFLPADinic算法时间是Dinic求解时间的1/15。

表2中结果表明，AK网络节点压缩率和边压缩率平均为82.25%和81.08%，并精确计算出最大流值。在AK网络上MFLPA-Dinic算法时间远低于Dinic算法，如在节点数为262 150的AK网络中，MFLPA-Dinic算法时间是Dinic求解时间的1/74。

4.2.4 ISAP和MFLPA-ISAP对比实验

同时在GENRMF和AK网络上与ISAP算法进行对比实验，结果见表3、表4和图7。

表3中网络节点数大于8 192后MFLPA-ISAP算法的时间复杂度低于ISAP。从表3、表4和图7中可以看出，在GENRMF和AK网络中MFLPA-ISAP算法的运行总时间也明显优于ISAP算法。如图7所示，在网络规模急剧增大的情况下其运行时间相较ISAP有明显优势。

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），在标签传播过程结束后，节点1、4和5可能具有相同标签值，划分到同一个子网络。令A={1,4,5},新建节点s′、t′构建新子网络，达到压缩条件，但是当把A压缩成一点后，（1,4）这条割边被压缩，因此产生了实验误差。

5 结束语

最大流问题是一种组合最优化的经典问题，在众多领域中有着十分广泛的应用，随着持续增长的数据造成网络规模呈现指数式的攀升，如何降低求解最大流的时间复杂度是一个亟待解决的问题。针对这种现状，本文提出了一种基于标签传播的大规模网络最大流计算方法MFLPA。首先，基于标签传播将初始网络划分成多个子网络；然后，结合商空间理论将子网络压缩成单个节点并形成规模较小的商网络；最后，在商网络中求解初始网络的最大流近似解。因为商网络的规模很小，所以在误差允许范围内极大降低了求解最大流的时间复杂度。

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 流网络示例图

本文方法具有普适性，可作为一个简化大规模网络的方法，将原始网络压缩为商网络后，其他任一最大流算法均可通过商网络估计原始网络的最大流。

未来的工作将从以下方面展开：

（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]骆志刚,丁凡,蒋晓舟,等.复杂网络社区发现算法研究新进展[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(国家高技术研究发展计划(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网络优先出版: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—），女，浙江余姚人，安徽大学计算机应用专业硕士研究生，主要研究领域为智能计算，机器学习等。

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项，发表学术论文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年于安徽大学获得博士学位，现为安徽大学讲师，主要研究领域为智能计算，机器学习等。发表学术论文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年于合肥工业大学获得博士学位，现为安徽大学副教授，主要研究领域为服务计算，云计算，商务智能等。发表学术论文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年于安徽大学获得博士学位，现为安徽大学教授，主要研究领域为粒计算，智能计算，商空间理论，机器学习等。获发明专利2项，发表学术论文80多篇，主持参与国家级、省部级项目10余项。