Exploring the connectivity reliability of large-scale bridge networks based on multilevel k-way graph partition

When exploring the connectivity reliability of bridges or other infrastructure network, efficient computing methods are usually the focus of attention. But there are few efficient algorithms for the connectivity reliability of large-scale bridge network. Taking a NH bridge network (including 1772 bridges, 40 nodes and 68 edges) as an example, this paper introduces an efficient algorithm to solve the connectivity reliability of large-scale infrastructure network based on multilevel k-way graph partition. First, considering the connectivity between nodes of bridge network, the multilevel k-way graph partition algorithm is applied to obtain 2 roughly equal subnets, and the number of connected edges between them is minimized. So that the whole bridge network is divided into a 3-element series system: 2 subnets and their connected edges. Then, by transforming the probabilities of state combinations of all edges into the state combinations of two subnets and their connected edges, the complexity of connectivity reliability calculation of bridge network is simplified. Finally, the efficiency and accuracy of the aforementioned algorithm are proved by applying it to the NH bridge network. The result shows that less than 1% of the consuming time of the traditional method is needed under the same guarantee rate.