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

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