A fast Monte Carlo algorithm for site or bond percolation

Abstract

We describe in detail a new and highly efficient algorithm for studying site or bond percolation on any lattice. The algorithm can measure an observable quantity in a percolation system for all values of the site or bond occupation probability from zero to one in an amount of time which scales linearly with the size of the system. We demonstrate our algorithm by using it to investigate a number of issues in percolation theory, including the position of the percolation transition for site percolation on the square lattice, the stretched exponential behavior of spanning probabilities away from the critical point, and the size of the giant component for site percolation on random graphs.

17 pages, 13 figures. Corrections and some additional material in this version. Accompanying material can be found on the web at http://www.santafe.edu/~mark/percolation/

Cited by in corpus (238)

• Evolution of networks
• The Anatomy of the Facebook Social Graph
• Percolation on complex networks: Theory and application
• Strongly correlated flat-band systems: The route from Heisenberg spins to Hubbard electrons
• Continuum Percolation Thresholds in Two Dimensions
• Explosive Phenomena in Complex Networks
• Statistical physics approaches to the complex Earth system
• Explosive Percolation: Novel critical and supercritical phenomena
• Percolation and epidemics in a two-dimensional small world
• Recent advances and open challenges in percolation
• The unreasonable effectiveness of tree-based theory for networks with clustering
• Immunization and targeted destruction of networks using explosive percolation
• Geography in a Scale-Free Network Model
• Machine learning of phase transitions in the percolation and XY models
• Scaling behavior of explosive percolation on the square lattice
• Impact of Cholesterol on Voids in Phospholipid Membranes
• Are Percolation Transitions always Sharpened by Making Networks Interdependent?
• On the critical behavior of the Susceptible-Infected-Recovered (SIR) model on a square lattice
• Square lattice site percolation at increasing ranges of neighbor interactions
• Flat-Band Ferromagnetism as a Pauli-Correlated Percolation Problem
• Robust quantum network architectures and topologies for entanglement distribution
• Convergence of threshold estimates for two-dimensional percolation
• Percolation of linear $k$-mers on square lattice: from isotropic through partially ordered to completely aligned state
• Simple cubic random-site percolation thresholds for complex neighbourhoods
• Effect of Dimensionality on the Continuum Percolation of Overlapping Hyperspheres and Hypercubes: II. Simulation Results and Analyses
• Percolation of disordered jammed sphere packings
• Entanglement generation in a quantum network at distance-independent rate
• Percolation with long-range correlated disorder
• Percolation on two- and three-dimensional lattices
• High-precision Monte Carlo study of several models in the three-dimensional U(1) universality class
• Pseudorandom Number Generators and the Square Site Percolation Threshold
• Universal dependence on disorder of 2D randomly diluted and random-bond +-J Ising models
• Topological estimation of percolation thresholds
• Percolation and the pandemic
• Percolation thresholds and fractal dimensions for square and cubic lattices with long-range correlated defects
• Cluster-resolved dynamic scaling theory and universal corrections for transport on percolating systems
• Percolation on hyperbolic lattices
• Explosive site percolation and finite size hysteresis
• Gaussian model of explosive percolation in three and higher dimensions
• Dynamics on Modular Networks with Heterogeneous Correlations
• From discrete to continuous percolation in dimensions 3 to 7
• Bohman-Frieze-Wormald model on the lattice, yielding a discontinuous percolation transition
• Estimation of Bond Percolation Thresholds on the Archimedean Lattices
• Finite-size scaling above the upper critical dimension in Ising models with long-range interactions
• Disassortativity of percolating clusters in random networks
• Optimal path cracks in correlated and uncorrelated lattices
• Simple cubic random-site percolation thresholds for neighborhoods containing fourth-nearest neighbors
• Percolation and jamming of random sequential adsorption samples of large linear $k$-mers on a square lattice
• Critical slowing down in polynomial time algorithms
• Efficient algorithm to study interconnected networks
• Measurement-induced phase transitions in sparse nonlocal scramblers
• Rigorous confidence intervals for critical probabilities
• Complementary algorithms for graphs and percolation
• Critical polynomials in the nonplanar and continuum percolation models
• On the study of force-balance percolation
• Finite-size scaling of the stochastic susceptible-infected-recovered model
• Interplay between percolation and glassiness in the random Lorentz gas
• Bond percolation on simple cubic lattices with extended neighborhoods
• Numerical evaluation of the upper critical dimension of percolation in scale-free networks
• Connected component identification and cluster update on GPU
• Continuous Percolation Phase Transitions of Two-dimensional Lattice Networks under a Generalized Achlioptas Process
• Critical fragmentation properties of random drilling: How many random holes need to be drilled to collapse a wooden cube?
• Efficient space virtualisation for Hoshen--Kopelman algorithm
• Percolation of randomly distributed growing clusters: Finite Size Scaling and Critical Exponents
• Physical-depth architectural requirements for generating universal photonic cluster states
• Different thresholds of bond percolation in scale-free networks with identical degree sequence
• Hopping transport in systems of finite thickness or length
• Universal quantum computing using $({\mathbb{Z}}_d{)}^3$ symmetry-protected topologically ordered states
• Efficient limited-time reachability estimation in temporal networks
• GPU accelerated Monte Carlo simulations of lattice spin models
• Percolation in Finite Matching Lattices
• Origin of the Pseudogap in High-Temperature Cuprate Superconductors
• New universality class in percolation on multifractal scale-free planar stochastic lattice
• Precise bond percolation thresholds on several four-dimensional lattices
• Jamming and percolation in generalized models of random sequential adsorption of linear $k$-mers on a square lattice
• Transparent electrodes with nanorings: a computational point of view
• Electrical conductance of two-dimensional composites with embedded rodlike fillers: an analytical consideration and comparison of two computational approaches
• Finite-size scaling in asymmetric systems of percolating sticks
• Mechanical Interaction Between Cells Facilitates Molecular Transport
• Critical pore radius and transport properties of disordered hard- and overlapping-sphere models
• Percolation of sticks: effect of stick alignment and length dispersity
• Monte Carlo Simulations of the Critical Properties of a Ziff-Gulari-Barshad model of Catalytic CO Oxidation with Long-range Reactivity
• Percolation in the canonical ensemble
• Quantum disorder and Griffiths singularities in bond-diluted two-dimensional Heisenberg antiferromagnets
• Percolation thresholds on planar Euclidean relative neighborhood graphs
• Crossing on hyperbolic lattices
• Restoring site percolation on a damaged square lattice
• Percolation thresholds on triangular lattice for neighbourhoods containing sites up-to the fifth coordination zone
• Quantum percolation phase transition and magneto-electric dipole glass in hexagonal ferrites
• On the numerical study of percolation and epidemic critical properties in networks
• Efficient simulation of the random-cluster model
• Distance-Independent Entanglement Generation in a Quantum Network using Space-Time Multiplexed Greenberger-Horne-Zeilinger (GHZ) Measurements
• Stacked triangular lattice: Percolation properties
• Percolation thresholds on 3-dimensional lattices with 3 nearest neighbors
• Site percolation thresholds on triangular lattice with complex neighborhoods
• Percolation transition of hydration water at hydrophilic surfaces
• Jamming and percolation of $k^3$-mers on simple cubic lattices
• Scaling of cluster heterogeneity in percolation transitions
• Winding clusters in percolation on the Torus and the Moebius strip
• Universality class of site and bond percolation on multi-multifractal scale-free planar stochastic lattice
• Cluster Monte Carlo and dynamical scaling for long-range interactions
• Site-Percolation Threshold of Carbon Nanotube Fibers: Fast Inspection of Percolation with Markov Stochastic Theory
• Newman-Ziff algorithm for the bootstrap percolation: application to the Archimedean lattices
• Conformal invariance in three dimensional percolation
• Void distributions reveal structural link between jammed packings and protein cores
• Effect of tunneling on the electrical conductivity of nanowire-based films: computer simulation within a core--shell model
• Enhancing Robustness and Immunization in geographical networks
• Percolation thresholds for discorectangles: numerical estimation for a range of aspect ratios
• Universal Properties of Cuprate Superconductors: Tc Phase Diagram, Room-Temperature Thermopower, Neutron Spin Resonance, and STM Incommensurability Explained in Terms of Chiral Plaquette Pairing
• Random sequential adsorption on Euclidean, fractal and random lattices
• Structure of percolating clusters in random clustered networks
• Continuum percolation of overlapping discs with a distribution of radii having a power-law tail
• Agglomerative Percolation on Bipartite Networks: A Novel Type of Spontaneous Symmetry Breaking
• Site-bond percolation solution to preventing the propagation of \textit{Phytophthora} zoospores on plantations
• Factorization of percolation density correlation functions for clusters touching the sides of a rectangle
• Percolation leads to finite-size effects on the transition temperature and center of mass energy required for the quark-gluon plasma formation
• Extended-range percolation in complex networks
• Highly Clustered Complex Networks in the Configuration Model: Random Regular Small-World Network
• Jamming and percolation of $k^2$-mers on simple cubic lattices
• Dulmage-Mendelsohn percolation: Geometry of maximally-packed dimer models and topologically-protected zero modes on site-diluted bipartite lattices
• Critical exponents for the homology of Fortuin-Kasteleyn clusters on a torus
• Reentrant magnetic ordering and percolation in a spin-crossover system
• Percolation phase transition by removal of $k^2$-mers from fully occupied lattices
• The influence of statistical properties of Fourier coefficients on random surfaces
• $N$-cluster correlations in four- and five-dimensional percolation
• How to share underground reservoirs
• Percolation on spatial anisotropic networks
• Dimer Covering and Percolation Frustration
• Jamming and percolation of dimers in restricted-valence random sequential adsorption
• Two-dimensional systems of elongated particles: From diluted to dense
• Chiral Plaquette Polaron Theory of Cuprate Superconductivity
• Bond percolation between $k$ separated points on a square lattice
• Universal features of cluster numbers in percolation
• Universal Critical Wrapping Probabilities in the Canonical Ensemble
• Random Sequential Renormalization and Agglomerative Percolation in Networks: Application to Erd"os-R'enyi and Scale-free Graphs
• Asymptotic scaling behavior of self-avoiding walks on critical percolation clusters
• On entropy, specific heat, susceptibility and Rushbrooke inequality in percolation
• Protected percolation: a new universality class pertaining to heavily-doped quantum critical systems
• Electrical conductivity of nanorod-based transparent electrodes: Comparison of mean-field approaches
• Random site percolation on honeycomb lattices with complex neighborhoods
• Crossing probability and number of crossing clusters in off-critical percolation
• Site percolation on lattices with low average coordination numbers
• Quantifying the Fermi paradox in the local Solar neighborhood
• Clarifying How Degree Entropies and Degree-Degree Correlations Relate to Network Robustness
• Comment on `Monte Carlo simulation study of the two-stage percolation transition in enhanced binary trees'
• Generalized-ensemble simulations and cluster algorithms
• Site and bond percolation thresholds in $K_{n,n}$-based lattices: Vulnerability of quantum annealers to random qubit and coupler failures on chimera topologies
• Are the Tails of Percolation Thresholds Gaussians ?
• Emergence of coexisting percolating clusters in networks
• Universality class of the percolation in two-dimensional lattices with distortion
• Exact Percolation Probability on the Square Lattice
• High-dimensional percolation criticality and hints of mean-field-like caging of the random Lorentz gas
• Honeycomb Lattices with Defects
• Alternative criterion for two-dimensional wrapping percolation
• Retention capacity of correlated surfaces
• Electrical conductivity of nanoring-based transparent conductive films: A mean-field approach
• Exact percolation probabilities for a square lattice: Site percolation on a plane, cylinder, and torus
• Hund's coupling-assisted ferromagnetic percolation transition in a multiorbital flat band
• A new algorithm for the ${}^K$DMDGP subclass of Distance Geometry Problems
• Percolation and jamming of linear $k$-mers on square lattice with defects: effect of anisotropy
• Jamming and percolation in the random sequential adsorption of a binary mixture on the square lattice
• Inhomogeneous percolation models for spreading phenomena in random graphs
• Asynchronous SIR model on Two-Dimensional Quasiperiodic Lattices
• Random site percolation thresholds on square lattice for complex neighborhoods containing sites up to the sixth coordination zone
• Self-dual quasiperiodic percolation
• Scaling laws for random walks in long-range correlated disordered media
• History-dependent percolation in two dimensions
• Bootstrap and diffusion percolation transitions in three-dimensional lattices
• Critical p=1/2 in percolation on semi-infinite strips
• Percolation in a simple cubic lattice with distortion
• Correlations in Quantum Spin Ladders with Site and Bond Dilution
• The Continuum Potts Model at the Disorder-Order Transition -- a Study by Cluster Dynamics
• Efficient percolation simulations for lossy photonic fusion networks
• Faster calculation of the percolation correlation length on spatial networks
• Random 2D nanowire networks: Finite-size effect and the effect of busbar/nanowire contact resistance on their electrical conductivity
• Site percolation in distorted square and simple cubic lattices with flexible number of neighbors
• Muiltiscale modeling of electrical conductivity of R-BAPB polyimide + carbon nanotubes nanocomposites
• Explosive Percolation on Directed Networks Due to Monotonic Flow of Activity
• What are the limits of universality?
• Percolation is Odd
• Geometric clusters in the overlap of the Ising model
• On the CFT describing the spin clusters in 2d Potts model
• Redefinition of site percolation in light of entropy and the second law of thermodynamics
• Percolation on a maximally disassortative network
• Correlated rigidity percolation and colloidal gels
• The elastic and directed percolation backbone
• Percolation via combined electrostatic and chemical doping in complex oxide films
• Continuum Percolation and Stochastic Epidemic Models on Poisson and Ginibre Point Processes
• Percolation of the Site Random-Cluster Model by Monte Carlo Method
• Percolation in two-species antagonistic random sequential adsorption in two dimensions
• Universality of random-site percolation thresholds for two-dimensional complex non-compact neighborhoods
• Magnetic properties of diluted hexaferrites
• Duality of critical interfaces in Potts model: numerical check
• Deterministic scale-invariant dynamics in a logistic Game-of-Life model
• Dynamic connectivity algorithms for Monte Carlo simulations of the random-cluster model
• Characterizing spatial point processes by percolation transitions
• A branching random-walk model of disease outbreaks and the percolation backbone
• Universality of the Crossing Probability for the Potts Model for q=1,2,3,4
• Random nanowire networks: Identification of a current-carrying subset of wires using a modified wall follower algorithm
• Sublattice-selective percolation on bipartite planar lattices
• The effects of disorder on Harris-criterion violating percolation
• Universality class of explosive percolation in Barabási-Albert networks
• Statistical Properties of Supercluster-Like Filaments from Cosmological Simulations
• Transparent electrodes based on mixtures of nanowires and nanorings: A mean-field approach along with computer simulation
• General Concurrence Percolation on Quantum Networks
• Bond percolation in distorted square and triangular lattices
• Cluster percolation in the three-dimensional $\pm J$ random-bond Ising model
• Percolation and electrical conduction in random systems of curved linear objects on a plane: computer simulations along with a mean-field approach
• A simple algorithm to test for linking to Wilson loops in percolation
• On the monotonicity of the critical time in the Constrained-degree percolation model
• Binary tree summation Monte Carlo simulation for Potts models
• Homology-changing percolation transitions on finite graphs
• Critical behavior of the stochastic SIR model on random bond-diluted lattices
• Electrical conductivity of randomly placed linear wires: a mean field approach
• The Tails of the Crossing Probability
• Electrical conductivity of conductive films based on random metallic nanowire networks
• Two Dimensional Connectivity for Vehicular Ad-Hoc Networks
• Electrical conductivity of random metallic nanowire networks: An analytical consideration along with computer simulation
• Phase transition in the diffusion and bootstrap percolation models on regular random and Erdős-Rényi networks
• Critical points of the random cluster model with Newman-Ziff sampling
• Exact Results for Average Cluster Numbers in Bond Percolation on Infinite-Length Lattice Strips
• Invariant percolation properties in random isotropic systems of conductive discorectangles on a plane: From disks to sticks
• A Formal Critique of the Value of the Colombian Páramo
• Percolation model for structural phase transitions in Li${}_{1-x}$H${}_x$IO${}_3$ mixed crystals
• Continuum Percolation on Disoriented Surfaces: the Problem of Permeable Disks on a Klein Bottle
• Errata and Addenda to Mathematical Constants
• Multirange Ising model on the square lattice
• Mandala Networks: ultra-robust, ultra-small-world and highly sparse graphs
• Uncovering Magnetic Phases with Synthetic Data and Physics-Informed Training
• Supplementary material: Topological estimation of percolation thresholds
• Percolation thresholds for discrete-continuous models with non-uniform probabilities of bond formation
• Geometrical effects on mobility
• Percolation in semicontinuum geometries
• Site and bond percolation in linearly distorted triangular and square lattices
• Bond percolation in distorted simple cubic and body-centered cubic lattices
• Exploring the variational method for thermodynamic models
• Disorder-free localization transition in a two-dimensional lattice gauge theory
• Upper bounds for critical probabilities in Bernoulli Percolation models