Estimating Residual Connectivity for Random Graphs

Abstract

Computation of the probability that a random graph is connected is a challenging problem, so it is natural to turn to approximations such as Monte Carlo methods. We describe sequential importance resampling and splitting algorithms for the estimation of these probabilities. The importance sampling steps of these algorithms involve identifying vertices that must be present in order for the random graph to be connected, and conditioning on the corresponding events. We provide numerical results demonstrating the effectiveness of the proposed algorithm.

arXiv comment29 pages, 13 figures

References in corpus (4)

• Modeling the Multi-layer Nature of the European Air Transport Network: Resilience and Passengers Re-scheduling under random failures
• Modelling the Air Transport with Complex Networks: a short review
• Evaluating North American Electric Grid Reliability Using the Barabasi-Albert Network Model
• A new transfer-matrix algorithm for exact enumerations: Self-avoiding polygons on the square lattice