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.