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

• 作者: 张以文 张燕平 赵姝 陈洁 魏华珍
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 最大流 标签传播 大规模网络 商空间 简化网络
• 年，卷（期）: 2017,（10）
• 所属期刊栏目: 网络与信息安全
• 页码范围: 1609-1620
• 页数: 12页
• 分类号: TP301.6
• 字数: 8312字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1609007

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵姝	安徽大学计算机科学与技术学院	82	555	13.0	19.0
5	张以文	安徽大学计算机科学与技术学院	45	260	9.0	14.0
9	陈洁	安徽大学计算机科学与技术学院	48	232	8.0	13.0
13	魏华珍	安徽大学计算机科学与技术学院	3	5	1.0	2.0