Research On Maximum Flow/Minimum Cut Problem Based On Quotient Space Theory

Maximum flow problem is one of the classical combination optimization problems,which has close connection of operational research and network flow theory.Maximum flow problem is usually used in the actual scene to solve complex problems,which provides the mathematical basis about scheduling resources and rational decision-making for the decision-makers,and has a wide range of applications in the field of science and engineering.Although the study of maximum flow problem has a long history,people now need an intelligent and efficient way to deal with massive data.In this background,it is difficult to use the traditional algorithm to calculate the maximum flow of large-scale networks.At the same time,with the computer network traffic increases rapidly,network congestion situation is particularly significant.The minimum cut set is an edge set,which determines the bearer and traffic capacity of the network,also is the key to the network’s maximum capacity.Minimum cut set problem is of great significance in practical application as well as maximum flow problem.When facing a large amount of complicated information,human intelligence can simplify and abstract complicated problems and transform them from different angles.The quotient space model can simulate these characteristics of human beings and transform complex problems into different granularity spaces to describe and analyze,which can efficiently simplify the scale of problem and shorten the solution time.In this dissertation,the quotient space model is combined with the maximum flow problem/minimum cut set problem to make up the deficiency of the traditional algorithm.This dissertation focuses on how the quotient space model is applied on large-scale networks to construct small-scale networks based on the original structure information,and how the maximum flow and the minimum cut set of large-scale networks are estimated based on small-scale networks with ensuring the accuracy of the solution and reducing computational complexity.This dissertation proposes an algorithm based on the quotient space model and label propagation for solving maximum flow problem,and also proposes an algorithm based on the quotient space model and augmented road mark for solving minimum cut set problem,by using quotient network information to estimate minimum cut set of initial large-scale network.Both two algorithms reduce the computational complexity and speed up the computation.The experiments are carried out on different international public test networks,which prove the effectiveness of the proposed algorithms.The main contributions of this dissertation are all as follows:1.The research background,significance of this dissertation and the problems that need to be solved when calculating the maximum flow/minimum cut set in practice are described in detail.At the same time,this dissertation introduces the current research of maximum flow/minimum cut set problem and the theory of quotient space,and then discusses them.2.This dissertation proposes an algorithm based on the quotient space model and label propagation for solving maximum flow problem,which is called MFLPA.Firstly,sub-structures with modularity characteristic in the network were quickly found based on the label propagation method.Secondly,the concept of quotient network is defined according to the quotient space theory.The maximum flow of the initial network is estimated on the quotient network.Finally,the experimental results on the public network are given,which prove that the algorithm can calculate the maximum flow of the initial network within a small error range.3.In order to calculate the maximum flow in the quotient network and estimate the initial network minimum cut set at the same time,this dissertation also proposes an algorithm based on the quotient space model and augmented road mark for solving minimum cut set problem,which is called DSM.In quotient network,the nodes are divided into different node sets,and a mapping relationship is found through a series of reasoning process between the key nodes of the initial network and different node sets in its quotient network,and this relationship is used to estimate the minimum cut set of the initial network.Finally,the experimental results on the public network data sets are given,which prove that the algorithm can exactly find the minimum cut set in the network when satisfying some specific conditions.