Large-deviation properties of largest component for random graphs

DOI10.1140/EPJB/E2011-10836-4zbMATH Open1515.60314arXiv1011.2996MaRDI QIDQ6135099FDOQ6135099

Alexander Hartmann

Publication date: 26 July 2023

Published in: The European Physical Journal B. Condensed Matter and Complex Systems (Search for Journal in Brave)

Abstract: Distributions of the size of the largest component, in particular the large-deviation tail, are studied numerically for two graph ensembles, for Erdoes-Renyi random graphs with finite connectivity and for two-dimensional bond percolation. Probabilities as small as 10^-180 are accessed using an artificial finite-temperature (Boltzmann) ensemble. The distributions for the Erdoes-Renyi ensemble agree well with previously obtained analytical results. The results for the percolation problem, where no analytical results are available, are qualitatively similar, but the shapes of the distributions are somehow different and the finite-size corrections are sometimes much larger. Furthermore, for both problems, a first-order phase transition at low temperatures T within the artificial ensemble is found in the percolating regime, respectively.

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

Recommendations

• On the largest component of the random graph at a nearcritical stage
• Large deviations for empirical measures of generalized random graphs
• On large deviation properties of Erdős-Rényi random graphs
• An introduction to large deviations for random graphs
• The large deviation principle for the Erdős-Rényi random graph
• The Largest Component in Subcritical Inhomogeneous Random Graphs
• A large-deviations principle for all the components in a sparse inhomogeneous random graph
• Giant components in random graphs

zbMATH Keywords

Monte Carlorandom graphfull supportlarge componentpercolate

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Large deviations (60F10) Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Cites Work

• Biological Sequence Analysis
• Title not available (Why is that?)
• Large deviations techniques and applications.
• Title not available (Why is that?)
• Large deviations
• Large Deviations and Ensembles of Trajectories in Stochastic Models
• Title not available (Why is that?)
• On large deviation properties of Erdős-Rényi random graphs
• New Optimization Algorithms in Physics
• The distribution of Lee–Yang zeros and Griffiths singularities in the ±Jmodel of spin glasses
• Searching for Rare Growth Factors Using Multicanonical Monte Carlo Methods
• Large‐deviations/thermodynamic approach to percolation on the complete graph
• Practical Guide to Computer Simulations
• The Wulff construction and asymptotics of the finite cluster distribution for two-dimensional Bernoulli percolation

Cited In (11)

• Edge fluctuations and third-order phase transition in harmonically confined long-range systems
• On large deviation properties of Erdős-Rényi random graphs
• The Largest Component in Subcritical Inhomogeneous Random Graphs
• Large-deviation properties of SIR model incorporating protective measures
• Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
• Efficient large deviation estimation based on importance sampling
• Large-deviation properties of resilience of power grids
• Truncated linear statistics in the one dimensional one-component plasma
• Large deviation theory of percolation on multiplex networks
• Percolation Analysis of Clusters in Random Graphs
• Title not available (Why is that?)

This page was built for publication: Large-deviation properties of largest component for random graphs

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