The importance sampling technique for understanding rare events in Erdős-Rényi random graphs

DOI10.1214/EJP.V20-2696zbMATH Open1327.05300arXiv1302.6551MaRDI QIDQ894166FDOQ894166

Authors: N. E. Zubov 

Publication date: 27 November 2015

Published in: Electronic Journal of Probability (Search for Journal in Brave)

Abstract: In dense ErdH{o}s-R'enyi random graphs, we are interested in the events where large numbers of a given subgraph occur. The mean behavior of subgraph counts is known, and only recently were the related large deviations results discovered. Consequently, it is natural to ask, can one develop efficient numerical schemes to estimate the probability of an ErdH{o}s-R'enyi graph containing an excessively large number of a fixed given subgraph? Using the large deviation principle we study an importance sampling scheme as a method to numerically compute the small probabilities of large triangle counts occurring within ErdH{o}s-R'enyi graphs. We show that the exponential tilt suggested directly by the large deviation principle does not always yield an optimal scheme. The exponential tilt used in the importance sampling scheme comes from a generalized class of exponential random graphs. Asymptotic optimality, a measure of the efficiency of the importance sampling scheme, is achieved by a special choice of the parameters in the exponential random graph that makes it indistinguishable from an ErdH{o}s-R'enyi graph conditioned to have many triangles in the large network limit. We show how this choice can be made for the conditioned ErdH{o}s-R'enyi graphs both in the replica symmetric phase as well as in parts of the replica breaking phase to yield asymptotically optimal numerical schemes to estimate this rare event probability.

Full work available at URL: https://arxiv.org/abs/1302.6551

Recommendations

• The large deviation principle for the Erdős-Rényi random graph
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• Counterexamples in importance sampling for large deviations probabilities
• Large deviations for random graphs. École d'Été de Probabilités de Saint-Flour XLV -- 2015
• Importance Sampling, Large Deviations, and Differential Games

zbMATH Keywords

large deviationsrare event simulationgraph limitsexponential random graphsErdős-Rényi random graphs

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Large deviations (60F10) Random graphs (graph-theoretic aspects) (05C80)

Cited In (3)

• Rare Event Simulation Using Reversible Shaking Transformations
• Approximating the cumulant generating function of triangles in the Erdös-Rényi random graph
• Rare events in random geometric graphs

This page was built for publication: The importance sampling technique for understanding rare events in Erdős-Rényi random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q894166)