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
Pub Type: Journals
network reliability, monte carlo markov chain, importance sampling