Efficient Rare-Event Simulation for Random Geometric Graphs via Importance Sampling

Abstract: Random geometric graphs defined on Euclidean subspaces, also called Gilbert graphs, are widely used to model spatially embedded networks across various domains. In such graphs, nodes are located at random in Euclidean space, and any two nodes are connected by an edge if they lie within a certain distance threshold. Accurately estimating rare-event probabilities related to key properties of these graphs, such as the number of edges and the size of the largest connected component, is important in the assessment of risk associated with catastrophic incidents, for example. However, this task is computationally challenging, especially for large networks. Importance sampling offers a viable solution by concentrating computational efforts on significant regions of the graph. This paper explores the application of an importance sampling method to estimate rare-event probabilities, highlighting its advantages in reducing variance and enhancing accuracy. Through asymptotic analysis and experiments, we demonstrate the effectiveness of our methodology, contributing to improved analysis of Gilbert graphs and showcasing the broader applicability of importance sampling in complex network analysis.