Degree-based approximations for network reliability polynomials
P.F.A. Van Mieghem (TU Delft - Network Architectures and Services)
X. Liu (TU Delft - Network Architectures and Services)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Two approximations for network reliability polynomials, only based upon the knowledge of the degree vector of the graph, are compared: the first-order approximation by Brown et al. and our stochastic approximation. Our method is an extension of the connectivity probability of Erdős–Rènyi random graphs. Both approximations are shown to upper bound the actual reliability polynomial and are increasingly accurate for dense and large graphs. Moreover, the first-order approximation is always sharper or at least as good as the stochastic approximation, whereas the stochastic approximation is computationally easier. Our stochastic approximation (2.2) can determine the critical operational probability under which the graph is disconnected almost surely for any graph and an approximation for the number Fj of sets of j links whose removal retains the graph G connected, which is helpfull because the exact computation of Fj is NP-hard.