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

来源：计算机科学与探索杂志2017年第10期北京时间：

作者：魏华珍，赵姝，陈洁，张以文，张燕平

单位：1. 安徽大学 计算机科学与技术学院，合肥 2306012. 安徽大学 信息保障技术协同创新中心，合肥 230601

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

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