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) and Dinic, 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%。

关键词: 最大流, 标签传播, 大规模网络, 商空间, 简化网络