计算机科学与探索 ›› 2017, Vol. 11 ›› Issue (10): 1609-1620.DOI: 10.3778/j.issn.1673-9418.1609007

• 网络与信息安全 • 上一篇    下一篇

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

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

  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

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

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

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