Research On The Maxflow Of The Uncertain Graph

Recently,in many various scientific fields, large amounts of data can beconverted into uncertain graph, eg: social networks, protein interaction networks.We can see the structural relationship of the information, get information from theuncertain graph. How to mine the structure features, the trends, patterns from thegraph is the practical and academic problem. Some studies have been done,including frequent subgraph mining, maximum clique problem, neighbors mining,shortest path, accessibility in uncertain graph. There are many issues of theuncertain graph to study such as the maximum flow problem in this paper.This paper proposes two new issues of the uncertain graph: maximummaximum flow probability and the maximum probability maximum flow.1)For the maximum maximum flow probability，this paper proposes MMFPbased on space decomposition of subgraph, and gives the optimization algorithm. Italso shows that the problem is#P-Hard.Then it proposes the approximationalgorithm based on Chernoff Bound. The approximation algorithm is provedunbiased estimate. Finally, the experiments show the time comparison of MMFP anderror analysis of approximation algorithms.2) For the maximum probability maximum flow，this paper proposes MPMFbased on space decomposition of maximum flow, and uses subgraph isomorphismand cutting point to optimize it. It notes that the problem is NP-C.Then it proposesthree approximation algorithms based on two factors(Structure and Probability):STR_GREEDY, PROB_GREEDY, COM_GREEDY. Finally, the experiments showthe time comparison of MPMF and the error analysis and time comparison ofapproximation algorithms.