• 网络与信息安全 •

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

1. 1. 安徽大学 计算机科学与技术学院，合肥 230601
2. 安徽大学 信息保障技术协同创新中心，合肥 230601
• 出版日期:2017-10-01 发布日期:2017-10-20

### 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. 1. School of Computer Science & Technology, Anhui University, Hefei 230601, China
2. Center of Information Support & Assurance Technology, Anhui University, Hefei 230601, China
• Online:2017-10-01 Published:2017-10-20

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