Мигов Д.А.  

Calculation of random graph probabilistic connectivity using two-node cuts

The problem of exact calculation of random graph probabilistic connectivity is considered. This characteristic is one of the main indices of network reliability. For the solution, an approach based on the structural decomposition of a network is proposed. Acceleration is achieved due to possibility of reliability calculation for a group of smaller networks instead reliability calculation of the initial network. A method has been developed that allows one to take into account a group of two-node cuts. As a result, the reliability calculation is much faster than the recursive bypass of two-node cuts using the appropriate formula. Also, we present the experimental study of the feasibility of decomposition for cuts which consist of more than two nodes.

Supported by the RFBR project No. 18-07-00460


To reports list