Computing the Reliability of Complex Networks

摘要: We present a decomposition procedure for evaluating the reliability of network whose elements fail independently with known probabilities. A subnetwork is “solved” by computing probability classes failure patterns within which performance constant. then iterate, combining solved subnetworks until entire has been evaluated. The running time each iteration depends superexponentially on boundary size, but treelike or “thin” networks total grows only linearly size. Details our scheme are presented wide variety measures performance. For where distribution too slow we quicker method finds average Finally, show that NP-hard, so efficiency in special cases all can be achieved.