粒计算求解复杂网络最大流的研究

Research on Solving Maximum Flow Problem of the Complex Network with Granular Computing

网络最大流问题是经典的组合优化问题,随着网络规模的增加,提高算法效率成为解决问题的关键.为了降低求解大规模网络最大流的计算量,本文模拟人类思维逐步求解复杂问题的思想,提出一种基于粒计算求解网络最大流问题的简单方法.本文首先将大规模复杂网络粒化为多个规模较小的子网络,再分别求解各子网络最大流,最后将子网络最大流合成得到原网络最大流.本文方法有效地降低了计算的复杂性,为在大规模复杂网络中快速获取最大流提供了方便,并给出一个解决最大流问题的新思路.不同网络上测试的实验结果显示,最大流的近似解误差可控制在1%左右,而平均运行时间只有经典算法(Ford-Fulkerson算法)运行时间的10%,表明本文方法的有效性.

Maximum flow problem is a classical combinational optimization problem. With the growing of the network scale, it is the key issue to get the maximum flow efficiently. For a large-scale complex network, a novel method for getting its maximum flow based on granular computing is proposed in this paper. Firstly, we granulate the complex network into some sub-networks. Then we compute the maximum flow for each sub-network. Finally, we compose the maximum flow of each sub-network, and regard it as the estimated maximum flow of the original network. The experimental results on different networks show the efficiency of the proposed method. The maximum flow error is only about 1%. At the same time,the running time of our method is 10% of the classical algo- rithm（ the Ford-Fulkerson algorithm） averagely.