Research On The Key Edge Of Uncertain Graph Based On Flow And Reliability

The key edge of uncertain graph can affect the network structure and function, once destroyed (or be removed), the entire system will have a great influence, and even cause the system to crash. At present, the key edge mining in the network has been concerned by many researchers because of its extensive application value and theoretical research significance. These methods stand in their respective positions, from different angles to explore the key edge of different application needs. This paper proposed an key edge evaluation model of flow network, which according to the relative loss of the flow and reliability after the edge are removed (or destroyed) to measure the key edge. We focus on how to calculation the maximum flow and reliability of dynamically network after removing edges fastly. The paper mainly includes the following aspects:(1) Construct a measurement model based on the relative loss of the flow and capacity reliability after the edge is removed. As for this model, we designed a kind of based algorithm BASE_FCP and aiming at the shortage of its performance we proposed algorithm SCA_FCP, which first classify the edge then use different method to calculation for different kind edges. Finally, the experimental results show that SCA_FCP has a certain increase in space complexity compared to BASE_FCP, but it has a great advantage in time complexity.(2) Although the flow and capacity reliability model has a good distinction, but the capacity reliability calculation is too complicated, however the calculation of distribution reliability only need to get the minimal graph of uncertain graph. Therefore, we construct a new model based on the relative loss of the flow and distribution reliability after the edge is removed. As for the model, we proposed algorithm SCA_FDP, but considering the shortcomings of the initial state space partition in the division of state, we proposed optimization algorithm SCA_FEA based on the determined edge filtering which can reduce the size of initial state section. Experimental results show that the flow and distribution reliability model has advantage of time and space performance to the flow and capacity reliability model. SCA_FEA has a certain advantage in time complexity compared to SCA_FDP(3) As for the flow and distribution reliability model, to calculate the most reliable maximum flow distribution reliability of uncertain graph is still an NP-hard problem, so it is difficult to meet the computational speed in a real-time environment. Therefore, we propose an approximation algorithms KEAA_FDP. We Gives the similarity measure of the key sequence solutions that get by approximate algorithm and exact algorithms. Then we analyze the worst situation. The experimental results show that KEAA_FDP has a significant improvement on the performance compared with SCA_FEA, and it can adapt to different size and density of the graph, and the volatility is not very large.