A cyber-physical system consists of two interacting networks, where the cyber network overlays the physical network. Due to the interdependence, node failures in one network may lead to failures of the other network and result in cascading failures of the whole system. One of the reasons for this phenomena is attributed to the connectivity of the interdependent system, which hinges heavily on the operation probability (or equivalently reliability) of networks in the light of node reliability. In this paper, we present the model of k-reliability, define cascading failures based on k-reliability, and propose an algorithm to calculate k-reliability for estimation of potential cascading failures. The proposed k-reliability, defined as the probability that at least k surviving nodes span an operating subnetwork, explains the operation probability of the system and reflects the connectivity of nodes in networks. In particular, we find that the network with regular interlink allocation strategy is homogeneous to the network with maximum k-reliability in class of graphs with 2n nodes and 2d edges when the information of intratopology is unknown. That is, regardless of the information of each individual network, the strategy that all nodes in the system are allotted the same number of bidirectional interlinks yields better performance on k- reliability than all other possible strategies both analytically and experimentally.
Multistate two-terminal reliability is the probability that $d$ units of flow can be transmitted from the source node $s$ to the sink node $t$. It is an important index for a flow network, and its value is based on minpaths or mincuts. However, the enumeration of all minpaths is not feasible in large networks. Hence, designing an approximation algorithm is valuable for the reliability of multistate flow networks. In this paper, we model a multistate flow network as an acyclic directed graph and find that the contribution of minpaths to the reliability changes with their lengths, so we consider the approximation solution of multistate two-terminal reliability by constraining diameter of the network. Furthermore, we give a sufficient and necessary condition to detect irrelevant arcs and propose an approximation algorithm by controlling the value of diameter constraint. In the meantime, the reliability with diameter constraint is also a parameter to partially reflect the performance of network. The experiments demonstrate the effectiveness and efficiency of the algorithm.
23 October 2020 in IEEE/ACM Transactions on Networking
k-terminal network reliability is the probability that k terminal vertices are connected given that edges in the network fail independently while vertices do not fail. It depends on the distribution of these terminal vertices as well as network topology. The problem of computing k-terminal reliability is NP-hard. Previous literature mainly focus on designing efficient algorithms to compute it in different graphs, but are lacking in the analysis for optimal distribution of k terminal vertices in sparse graphs, within which those with n nodes and m edges, where m ≤ n + 1, are most basic classes. Hence, it is of great significance to investigate the optimal distribution of terminal vertices in these classes of graphs before considering general cases. In this paper, we prove that k-terminal network reliability obtains the maximum if k terminal vertices induce a connected subgraph. Further, we give equations of maximum reliability for all possible graphs in the above classes. The experiments illlustrate the variation, with several parameters and according to our theoretical results, of maximal k-terminal reliability, and provide observations for graphs with any number of edges.
1 January 2009 in Computers & Mathematics with Applications