English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In dense Erd\H{o}s-R\'enyi random graphs, we are interested in the eventswhere large numbers of a given subgraph occur. The mean behavior of subgraphcounts is known, and only recently were the related large deviations resultsdiscovered. Consequently, it is natural to ask, can one develop efficientnumerical schemes to estimate the probability of an Erd\H{o}s-R\'enyi graphcontaining an excessively large number of a fixed given subgraph? Using thelarge deviation principle we study an importance sampling scheme as a method tonumerically compute the small probabilities of large triangle counts occurringwithin Erd\H{o}s-R\'enyi graphs. We show that the exponential tilt suggesteddirectly by the large deviation principle does not always yield an optimalscheme. The exponential tilt used in the importance sampling scheme comes froma generalized class of exponential random graphs. Asymptotic optimality, ameasure of the efficiency of the importance sampling scheme, is achieved by aspecial choice of the parameters in the exponential random graph that makes itindistinguishable from an Erd\H{o}s-R\'enyi graph conditioned to have manytriangles in the large network limit. We show how this choice can be made forthe conditioned Erd\H{o}s-R\'enyi graphs both in the replica symmetric phase aswell as in parts of the replica breaking phase to yield asymptotically optimalnumerical schemes to estimate this rare event probability.

The importance sampling technique for understanding rare events in Erd\H{o}s-R\'enyi random graphs