COMPUTING NETWORK RELIABILITY COEFFICIENTS

Elizabeth Moseman, Isabel Beichl, Francis Sullivan, and Brian Cloteaux

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 way to compute the reliability of a network is to compute the number of connected spanning subgraphs of each size in the graph. As with many of this type of problem, finding an exact value for this probability proves to be more difficult than computationally feasible. As such, we turn to approximation methods. Two methods have been developed for computing these coefficients: sequential importance sampling (SIS) and Monte Carlo Markov chain (MCMC). MCMC is based on a random walk through the sample space while SIS forms a sample directly from properties of the sample space.  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.

MCMC and SIS are both ways of sampling from a large set without knowing how many objects are in the set. In the case of reliability, the set under consideration is the set of connected spanning subgraphs of the graph. In order to properly utilize MCMC, two things must be calculated, the mixing time, a parameter which governs how long the algorithm must be run to get independent samples, and the fugacity, a parameter which governs which samples are most likely to occur by changing the acceptance rates of steps in the random walk. Despite the theory available on MCMC, both of these remain 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.