Strongly-connected percolation on directed lattices
summary
The gist
Strongly-connected percolation on directed lattices studies percolation on lattices with directed bonds…
In short
The study investigates percolation on lattices with directed bonds, focusing on strongly-connected clusters where every site is mutually reachable along forward paths. Findings show this system belongs to a different universality class than traditional undirected percolation, yet all bond arrangements share the same class. Critical exponents and fractal dimensions are distinct from ordinary percolation, and wrapping probabilities are substantially higher.
Key concepts
- Strongly-Connected Clusters
- These are groups of sites connected by directed bonds such that you can travel between any two sites within the group by only following bonds in their forward direction. They model systems like traffic flow or social networks where movement is restricted to a specific direction.
- Universality Class
- This refers to a set of critical exponents and scaling behaviors that describe how a system behaves near its critical point. The paper finds that strongly-connected percolation has its own unique universality class, separate from standard undirected percolation, despite different bond arrangements.
- Critical Exponents (β and γ)
- These are specific mathematical numbers that describe the scaling behavior of cluster sizes near the critical point. The estimated values for this directed system ($eta eq 5/36$ and $ ilde{eta} eq 43/18$) are significantly different from those found in ordinary percolation, indicating a fundamentally different physical process.
- Wrapping Probability (RL(pc))
- This is the likelihood that a cluster spans across periodic boundaries of the lattice. The study finds this probability to be substantially higher than in ordinary percolation, suggesting that directed connectivity influences how clusters interact with boundary conditions.
Terminology used across episodes
This episode discusses
- Strongly-connected percolation on directed lattices · Paper Radio
- Percolation transition of strongly connected clusters in finite dimensions and on complete graphs · Paper Radio
- The Planar Lattice Two-Neighbor Graph Percolates
- Janus Percolation in Anisotropic Limited-Degree Networks
The paper
Strongly-connected percolation on directed lattices · Read on arXiv
M. E. J. Newman, P. Grassberger, R. M. Ziff
University of Michigan · Jülich Supercomputing Centre
Transcript
Introduction to the show: ident: Condensed Matter. The day in condensed matter: materials, phases and the measurements under them.
Kai: We're looking at the paper: "Strongly-connected percolation on directed lattices".
Mira: Here's the gist of the paper. Strongly-connected percolation on directed lattices studies percolation on lattices with directed bonds, focusing on strongly-connected clusters—clusters in which every site is reachable from every other along a directed path—and finds that the critical behavior is in a distinctly different universality class from that of traditional undirected percolation, but that all bond arrangements appear to fall in the same universality class Definition and Context of Strongly-Connected Clusters Strongly-connected clusters are defined as groups of sites connected by directed bonds such that every site in a cluster is reachable from every other along a directed path that follows bonds only in their forward direction These clusters have applications in transportation and traffic flow, social network analysis, the world wide web, and bioinformatics They are distinct from weakly-connected clusters which are groups of sites connected by occupied bonds running in any direction Lattice Configurations Investigated The study focuses on square lattices in two dimensions with directed bonds and examines four different arrangements of the bond directions These configurations include the Manhattan lattice, the L-lattice, the random diode model, and the square ice model The Manhattan lattice is named for street patterns that alternate directions for both east-west and north-south running streets The L-lattice involves every site having two ingoing and two outgoing bonds where the ingoing ones are opposite one another, resulting in a 90 degree turn at every site Algorithmic Approaches for Measurement The authors employ several algorithmic approaches to probe the percolation properties of directed lattices These include breadth-first and depth-first search algorithms to find the outcomponent, incomponent, and their intersection which gives the strongly-connected cluster Tarjan’s algorithm is noted as a fast method for finding strongly-connected clusters by employing some additional bookkeeping strategies Incremental algorithms are also developed to maintain strongly-connected structures as bonds are added one by one, though they are less efficient than those for the undirected case Critical Properties and Universality Class The paper investigates critical properties such as scaling behavior, the position of the percolation threshold, critical exponents, and fractal dimensions The results show that while the critical behavior is in a different universality class from ordinary percolation, all bond arrangements appear to fall in the same universality class For instance, for the Manhattan lattice, the estimated percolation threshold is pc = 0.6971571(5) Key Findings on Critical Exponents and Dimensions The study estimates critical exponents with values such as β = 0.2618(3) and γ = 2.1423(4), which are distinctly different from the known value for ordinary undirected percolation The fractal dimension of the percolating strongly-connected cluster is estimated to be df = 1.8035(1) These exponents suggest a combined estimate of df = 1.8035(1), which is slightly lower than the value given recently by Wang and Li The wrapping probability at the percolation threshold RL(pc) is found to be substantially higher than the corresponding probability for ordinary percolation In conclusion, the paper finds convincing evidence that strongly-connected percolation falls in a different universality class from ordinary percolation in two dimensions, with distinctly different critical exponents This universality class also appears to be different from other known classes The wrapping probability we find to be substantially higher than the corresponding probability for ordinary percolation is a perhaps surprising result The work described here could be extended in a number of directions Appendix Details The appendix provides computer code for the calculations in this paper, which is written in the C programming language for speed The code is divided across a number of programs as follows: binary.c generates either a Manhattan lattice or an L-lattice on an L×L system and then repeatedly simulates percolation on that lattice to measure the size of the largest strongly-connected cluster clusters.c generates either a Manhattan lattice or an L-lattice on an L × L system and then repeatedly simulates percolation on that lattice to measure the size of the largest strongly-connected cluster, the average cluster, and whether wrapping has occurred in the horizontal and vertical directions binary ice.c generates random configurations of the ice model by translation from Markov chain Monte Carlo simulations of the three-state Potts antiferromagnet then finds thresholds for wrapping in the horizontal and vertical directions by binary search clusters rl.c generates configurations of the random diode model then measures the size of the largest strongly-connected cluster, the average cluster, and whether wrapping has occurred at the percolation threshold p = 1 incremental.c generates an L × L Manhattan or L-lattice system for given L and then repeatedly simulates percolation on it, finding the stronglyconnected components using the incremental algorithm of Section III B and calculating the size of the largest component Numerical Calculations Details In appendix B, numerical calculations provide further details of the numerical methods and calculations underlying the results in this paper Estimates of pav and its uncertainty were made directly from Eq.
Kai: (6) Estimates of pc-c were made by computing RL(p) and R2L(p) from Eq.
Mira: (5) and then solving for the root p of RL(p)−R2L(p) = 0 by binary search The error on pc-c was estimated by bootstrapping with 100 bootstrap repetitions for each value of L Final estimates of pc are error-weighted straight-line extrapolations to the intercept at L = ∞ and quoted errors are standard errors on the intercept Hull Dimension Measurement The fractal dimension dh of the hull is calculated from the variation of the average length of the hull walk l as a function of system size The slope of the fit gives a value of dh = 1.3331(2), which is consistent with the hypothesis that dh = 4/3 exactly Table I provides scaling estimates of pc for the Manhattan, L-lattice, and ice models using average and cell-to-cell estimates derived from three different definitions of wrapping around the boundaries on an L × L periodic system Table II presents scaling estimates of the wrapping probability at the percolation threshold RL(pc) for the Manhattan lattice, L-lattice, ice model, and random diode model for each of the three definitions of wrapping used here Table III shows estimates of the critical exponents β and γ from the slopes of the lines in Fig.
Kai: 10 The overall best estimates for pc are pc = 0.697160(2) for the Manhattan lattice, 0.740193(4) for the L-lattice, and 0.708838(4) for the ice model The overall best estimates of the three wrapping probabilities are 0.86117(6) for wrapping in any direction, 0.75001(7) for one specified direction, and 0.63867(11) for both directions The values differ considerably from the values for ordinary undirected percolation Final Conclusion on Critical Exponents The best overall estimate of the exponent is β = 0.2618(3), distinctly different from the value 5/36 = 0.1389 for ordinary undirected percolation The exponent γ is estimated as γ = 2.1423(4), again distinctly different from the known value for undirected percolation, which is γ = 43/18 = 2.389 The correlation length exponent ν satisfies the hyperscaling relation dν = 2β + γ where d is the system dimension, giving ν = β + 1/2γ = 1.3330(3) The fractal dimension of the percolating strongly-connected cluster can be calculated from either β or γ as df = d - β/ν = 1.8036(2) or df = 1/2 + gamma/nu = 1.8033(2) The scaling relation for the complete distribution of cluster sizes is p(s) = s(1-τ)/L df f(s/L df) where τ is in general different from the exponent for ordinary percolation Final Summary of Findings In this paper we have studied the percolation properties of strongly-connected clusters for bond percolation on directed lattices We find convincing evidence that strongly-connected percolation falls in a different universality class from ordinary percolation in two dimensions, with distinctly different critical exponents All arrangements of bond directions are in the same universality class The wrapping probability we find to be substantially higher than the corresponding probability for ordinary percolation is a perhaps surprising result Each of these quantities is expected to take a universal value Future Directions The work described here could be extended in a number of directions One could look at other arrangements of the directed bonds on the square lattice, such as the two-neighbor model
38: , the biased directed percolation model
39: , or the randomly-oriented Manhattan lattice
40: Several researchers have looked previously at resistor-diode lattices in which occupied bonds can run either in one direction, as here, or in both directions
30, 35–37: One could also look at strongly-connected clusters under site (rather than bond) percolation on square lattices, or at either bond or site percolation on non-square lattices such as triangular or hexagonal lattices, or on cubic or hypercubic lattices in higher dimensions Some such cases have been investigated for the random resistordiode model
30: but many other possibilities remain to be examined The code for the calculations in this paper is available for download from https://umich.edu/ mejn/scc.zip and is written in the C programming language for speed Acknowledgments This work was funded in part by the US National Science Foundation under grant DMS–2404617 The code is divided across a number of programs as follows: binary.c generates either a Manhattan lattice or an L-lattice on an L×L system and then repeatedly simulates percolation on that system to measure the size of the largest strongly-connected cluster clusters.c generates either a Manhattan lattice or an L-lattice on an L × L system and then repeatedly simulates percolation on that lattice to measure the size of the largest strongly-connected cluster, the average cluster, and whether wrapping has occurred in the horizontal and vertical directions binary ice.c generates random configurations of the ice model by translation from Markov chain Monte Carlo simulations of the three-state Potts antiferromagnet then finds thresholds for wrapping in the horizontal and vertical directions by binary search clusters rl.c generates configurations of the random diode model then measures the size of the largest strongly-connected cluster, the average cluster, and whether wrapping has occurred at the percolation threshold p = 1 incremental.c generates an L × L Manhattan or L-lattice system for given L and then repeatedly simulates percolation on it, finding the stronglyconnected components using the incremental algorithm of Section III B and calculating the size of the largest component The error on pc-c was estimated by bootstrapping with 100 bootstrap repetitions for each value of L Final estimates of pc are error-weighted straight-line extrapolations to the intercept at L = ∞ and quoted errors are standard errors on the intercept The calculations of crossing probabilities in Section IV B for Manhattan, L-lattice, and ice models are based on the same numerical results as the calculations of pc in Section IV A using Eq.
Title and authors: Kai: So, what does the actual summary of "Strongly-connected percolation on directed lattices" say about what they found? It talks about defining these clusters as groups where every site is reachable from every other by following only forward bonds.
Mira: Yeah, they spend a lot of time distinguishing these from weakly connected clusters, which are just groups connected by any bond direction. The core finding is that the critical behavior—how the system behaves right at the percolation threshold—is in a different universality class than traditional undirected percolation.
Lev: That’s a big statement because it means standard tools for analyzing random networks might not apply directly to directed systems without some specific corrections.
Kai: They examined several lattice configurations, including the Manhattan lattice, the L-lattice where every site has two ingoing and two outgoing bonds with opposite orientations, and randomized models like the random diode model and square ice model.
Mira: The summary emphasizes that despite these wildly different bond arrangements, they all seem to share the same universality class for their critical properties. That’s a pretty strong claim when you introduce so much structural variation.
Lev: If we were to try and simulate this on a real system, we would have to account for the specific bond arrangement, but if they are all in the same class, that suggests there might be a more fundamental underlying principle governing these directed systems.
Kai: They use things like breadth-first search and Tarjan’s algorithm to find the strongly-connected cluster intersection, which is their primary way of measuring these properties in simulations.
Mira: The paper stresses that their simulation results show a distinct difference in critical exponents, giving us those values we talked about earlier, like beta being zero point two six one eight(three).
Lev: Those exponents are what matter most for predicting the macroscopic behavior of the system as it gets bigger, so getting these estimates right is essential for any practical application.
Kai: They also look at scaling behavior and fractal dimensions, finding that the cluster dimension is estimated around one point eight zero three five(one) for certain lattices.
Mira: So, to sum up their summary: they found a new class of critical behavior for directed percolation, and that this class seems robust across different bond configurations on a square lattice.
The paper's summary: Lev: Now, let’s talk about what the authors suggest improving or extending in this work. They aren't just stopping at measuring these four specific lattices and four specific models.
Kai: One of the suggested improvements is building a better way to understand cluster topology when bonds are added, using something they call a condensation graph that is necessarily acyclic.
Mira: That sounds like it could help us predict if adding a new bond will join many small clusters into one big one, which would be really useful for modeling traffic flow or network growth.
Lev: If we can track that acyclic graph incrementally, it moves us beyond just knowing the final cluster size and gives us dynamic information about how the system evolves during construction.
Kai: Another suggestion is using incremental algorithms to maintain these strongly-connected structures as bonds are added one by one, though they admit those are less efficient than what you’d see in an undirected case.
Mira: That makes sense, because with directed bonds, maintaining that structure dynamically is inherently harder than just counting connections in a static undirected graph.
Lev: And they also mention extending the study to other types of lattices and bond percolation on non-square lattices like triangular or hexagonal ones, or even higher dimensions like cubic ones.
Kai: They’ve also looked at other models, like the biased directed percolation model or the random diode model, which gives us insights into more complex scenarios.
Mira: It sounds like they are trying to broaden the scope beyond just square lattices and specific bond patterns to see if this universality class holds up in more general settings.
The paper's improvements: Kai: So, bringing it all together on "Strongly-connected percolation on directed lattices," the paper provides convincing evidence that strongly-connected percolation has its own distinct universality class in two dimensions.
Mira: They conclude that this class is different from ordinary percolation because of the distinctly different critical exponents they found.
Lev: But they also stress that all bond arrangements fall into this same universality class, which is a key piece of information for us when we're trying to predict how these systems will behave in practice.
Kai: The wrapping probability finding is surprising—RL at pc is substantially higher than for ordinary percolation, and they suggest this might be a universal value across different systems.
Mira: It’s certainly an interesting result, especially since the wrapping probability for ordinary percolation is much lower.
Lev: For real hardware simulations, knowing that the scaling relation p of s equals s to minus tau over L to power df f of s over L to power df where tau is in general different from the exponent for ordinary percolation means we need a new way to estimate those exponents for directed systems.
Kai: So, the overall picture is that we have established this new class and its key features through high-precision numerical calculations across four different lattice types.
Mira: It’s a solid foundation for future research into how directed constraints influence connectivity in physical systems.
Lev: If we were to take these findings to build something, the immediate need is a concrete set of parameters for those critical exponents so we can start designing systems that respect this new scaling law.
Conclusion: Kai: So we just finished looking at the paper "Strongly-connected percolation on directed lattices," and what they found is that directed percolation has its own set of critical exponents, distinct from traditional undirected percolation.
Mira: Exactly, and this is important because it means the critical behavior isn't universal across all types of networks anymore; it depends on the directionality of the bonds.
Lev: From an engineering standpoint, if we were trying to model a directed traffic flow network or a specific type of circuit where connections only go one way, we need these specific exponents to get our scaling right.
Kai: They looked at several lattice arrangements—the Manhattan lattice, the L-lattice with those ninety degree turns—and found that even though the geometry is different, they all fall into this same universality class.
Mira: And the results are quite specific; they estimated a beta exponent of zero point two six one eight and a gamma exponent of two point one four two three.
Lev: Those numbers are what you’d have to feed into an error correction scheme if you wanted to build a real system based on these directed bonds, and they suggest the fractal dimension is about one point eight zero three five.
Kai: They also looked at the wrapping probability, RL at the percolation threshold, and it’s substantially higher than what we see in ordinary percolation.
Mira: That's a bit surprising because we expected universal values to be more consistent, but they found that this wrapping probability is significantly different from the known value for undirected systems.
Lev: For running these simulations on real hardware, knowing that the error on the critical point pc minus c is estimated by bootstrapping with one hundred repetitions for each lattice size L gives us a solid way to gauge how reliable those threshold estimates are.
Kai: So, to wrap up this paper "Strongly-connected percolation on directed lattices," they’ve convinced us that we need a new set of scaling relations when dealing with directed networks.
Mira: It opens up the door for building models that account for directional constraints in areas like transportation or social networks where flow has a specific sense.
Lev: Next time, we'll look at how this might translate into error correction overhead when you try to implement these directed structures on actual quantum hardware.
More episodes
- 2610.32678-Probing the limits of materials design via a comprehensive crystal database of 14.6 million structures with 140 properties
- 2610.33595-Native-oxide-driven layer asymmetry, two-step switching and exchange bias in Co/Ir/Co trilayers
- 2503.19572-Spin models from nonlinear cellular automata
- 2606.23350-Irreversibility Enhances Quantum-Enhanced Markov-Chain Monte Carlo
- 2608.02744-Two-Parameter Ansatz for the Violation of Eigenstate Thermalization
- 2210.00806-Low- and high-energy localization landscapes for tight-binding Hamiltonians in two-dimensional lattices
- 2409.09625-Selective switch for band-edge alignments in pentagonal CdSeTe monolayer: Atom-valley locking
- 2606.20168-Norms, overlaps and Yangian descendants for the Haldane-Shastry spin chain
- 2512.19503-Strain-induced splitting of the CCDW-NCCDW phase transition in 1T-TaS 2
- 2307.12638-Strong localization of microwaves beyond two dimensions in aperiodic Vogel spirals