Large-deviation properties of largest component for random graphs

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.

8 pages, 9 figures, a concise summary (1.3 pages) of this paper is available at the Papercore database at http://www.papercore.org/Hartmann2010

References in corpus (6)

• Large deviations and ensembles of trajectories in stochastic models
• Probing the tails of the ground state energy distribution for the directed polymer in a random medium of dimension $d=1,2,3$ via a Monte-Carlo procedure in the disorder
• Multicanonical sampling of rare events in random matrices
• Freezing transition of the directed polymer in a $1+d$ random medium : location of the critical temperature and unusual critical properties
• Distribution of Lee-Yang zeros and Griffiths singularities in the $\pm J$ model of spin glasses
• Testing Error Correcting Codes by Multicanonical Sampling of Rare Events

Cited by in corpus (43)

• Long time position distribution of an active Brownian particle in two dimensions
• Current fluctuations in non-interacting run-and-tumble particles in one-dimension
• High-precision simulation of the height distribution for the KPZ equation
• Large-deviation properties of the largest biconnected component for random graphs
• Distribution of diameters for Erdös-Rényi random graphs
• Position distribution in a generalised run and tumble process
• Convex Hulls of Random Walks: Large-Deviation Properties
• Large deviation theory of percolation on multiplex networks
• Critical behavior of the Anderson model on the Bethe lattice via a large-deviation approach
• Large-deviation properties of resilience of power grids
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• Sampling motif-constrained ensembles of networks
• Edge fluctuations and third-order phase transition in harmonically confined long-range systems
• Probing the large deviations of the Kardar-Parisi-Zhang equation at short time with an importance sampling of directed polymers in random media
• Large-deviation properties of resilience of transportation networks
• Observing symmetry-broken optimal paths of stationary Kardar-Parisi-Zhang interface via a large-deviation sampling of directed polymers in random media
• Sampling fractional Brownian motion in presence of absorption: a Markov Chain method
• Large Deviations of Convex Hulls of Self-Avoiding Random Walks
• Rare-Event Properties of the Nagel-Schreckenberg Model
• Large deviations of the length of the longest increasing subsequence of random permutations and random walks
• Stable glassy configurations of the Kob-Andersen model using swap Monte Carlo
• Convex Hulls of Multiple Random Walks: A Large-Deviation Study
• Local time of a system of Brownian particles on the line with steplike initial condition
• A Monte Carlo algorithm to measure probabilities of rare events in cluster-cluster aggregation
• Occupation time of a system of Brownian particles on the line with steplike initial condition
• First-passage area distribution and optimal fluctuations of fractional Brownian motion
• Efficient large deviation estimation based on importance sampling
• How many longest increasing subsequences are there?
• Large-deviations of the SIR model around the epidemic threshold
• Large Deviations of Convex Hulls of the "True" Self-Avoiding Random Walk
• The Griffiths phase and beyond: A large deviations study of the magnetic susceptibility of the two-dimensional bond-diluted Ising model
• First-passage properties of the jump process with a drift. Two exactly solvable cases
• Numerical Aspects of Large Deviations
• Importance Sampling for counting statistics in one-dimensional systems
• Heterogeneity in Outcomes of Repeated Instances of Percolation Experiments
• Large deviations of connected components in the stochastic block model
• Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
• Large-deviation properties of the extended Moran model
• Gelation in input-driven aggregation
• Truncated linear statistics in the one dimensional one-component plasma
• Rare-event properties in a classical stochastic model describing the evolution of random unitary circuits
• Dimensionality-induced dynamical phase transition in the large deviation of local time density for Brownian motion
• Large Deviation Properties of Minimum Spanning Trees for Random Graphs