Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Computing Network Reliability Coefficients

Published

Author(s)

Elizabeth R. Moseman, Isabel M. Beichl, Francis Sullivan

Abstract

When a network is modeled by a graph and edges of the graph remain reliable with a given probability p, the probability of the graph remaining connected is called the reliability of the network. One form of the reliability polynomial has as coefficients the number of connected spanning subgraphs of each size in the graph. Since the problem of exact computation is P-hard, we turn to approximation methods. We have developed two methods for computing these coefficients: one based on sequential importance sampling (SIS) and the other based on Monte Carlo Markov chain (MCMC). MCMC uses a random walk through the sample space while SIS draws a sample directly. There is not much theory available on the SIS method; however, this method is fast. In contrast, MCMC has a great deal of theory associated with it and is thus a more widely used and trusted method. In order to properly use MCMC, two quantities are need, the mixing time, the parameter which governs how long the algorithm must be run to get independent samples, and the fugacity, the parameter which governs the acceptance rates of proposed steps in the random walk. Despite the theory available on MCMC, both of these quantities are very difficult to calculate. As such, it is common practice to simply guess at values for these parameters. This work focuses on the effectiveness of SIS in calculating these MCMC parameters in a given instance of the problem. Thus, we use SIS to speed up MCMC.
Citation
Congressus Numerantium
Volume
207

Keywords

network reliability, monte carlo markov chain, importance sampling

Citation

Moseman, E. , Beichl, I. and Sullivan, F. (2011), Computing Network Reliability Coefficients, Congressus Numerantium, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=908418 (Accessed March 29, 2024)
Created December 1, 2011, Updated February 19, 2017