Research On Solving Maximum Flow Problem Of Large-scale Networks Based On Granular Method

The maximum flow problem is a most important part of network flow theory, it’s a special linear programming and combinatorial optimization problem which is between continuous and discrete. In the practical application, the flow in information, traffic, electricity logistics and social networks has its weight, which makes it more meaningful.In last decades, many operational research and computer science problems has been resolved with the developing of network maximuim flow theory. In social network, it generate huge network data which all can be converted into network maximum flow problem, such as the600millon social network users,420million mobile internet users, electronic commerce and the logistic along with the electronic commerce. All these put forward higher requirements for network optimization algorithm, makes it can be better applied in different industries. The research of maximum flow problem is still particularly important and has more practical meaning in the new period, it has arelatively broad prospect on the practical application. However, the development of classical algorithm has entered a bottleneck period a few years ago, it improved in recent years, but in still can’t adapt to the speed of the large-scale network in current era. In human intelligence thinking, when faced a complex problem and diffcult to solve, we usually use stepwise refinement method while the granular computing theory can convert the complex space problem into several simple questions. In order to ensure the speediness and efficiency, this dissertation put forward the idea of using granular computing to solve the deficiency of maximum flow problem.In this dissertation, the research is focused on how we granulate a complex network into small and simple sub-networks to compute the maximum flow faster. Firstly, we granulate the original network into sub-networks based on granular computing. Then we compute the maximum flow of sub-network. At last, we take the minimum as the estimated maximum flow of the original network. In the second step, we could parallel the process of compute the sub-networks based on multi-thread method. The experimental results show the effectiveness of our algorithm, it greatly reduced the time required to solve the maximum flow and ensures the accuracy of the results at the same time.The main ideals of this dissertation is as follows:1.Firstly, we introduce the research background and significance of this dissertation, and the research status of maximum flow problem and granular computing.2.Then, we introduce some basic knowledges and algorithms about maximum flow, also the granular computing method in the second section.3.We give out the algorithm on solving maximum flow of large-scale network based on granular method and some related knowledges. And we give some experiment results which verify the effectiveness of our algorithm.4.Lastly, we give a improved method about the granular computing, we use multithreading method while computing maximum flow of each sub-networks. And we give some experiment results which verify the effectiveness of our algorithm.