Strongly-connected percolation on directed lattices
Listen
Radio episode about this paper
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.
M. E. J. Newman, P. Grassberger, R. M. Ziff
University of Michigan · Jülich Supercomputing Centre
cond-mat.stat-mech
Submitted: 2026-07-27
Updated: 2026-11-02
Comments: 16 pages, 14 figures, 3 tables
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 82/100
The gist: Strongly-connected percolation on directed lattices studies percolation on lattices with directed bonds…
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
Summary
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. p. 91423(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. p. 98035(1) These exponents suggest a combined estimate of df = 1. p. 58035(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
Conclusion on Universality
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. p. 9c 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. p. 3 p. 3c 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. p. 5 p. 5c 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. p. 3 p. 3c 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. (6) Estimates of pc-c were made by computing RL(p) and R2L(p) from Eq. p. 7 (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
Summary of Results Table
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. 10 The overall best estimates for pc are pc = 0. p. 8697160(2) for the Manhattan lattice, 0. p. 8 p. 8740193(4) for the L-lattice, and 0. p. 8 p. 8708838(4) for the ice model The overall best estimates of the three wrapping probabilities are 0. p. 986117(6) for wrapping in any direction, 0. p. 975001(7) for one specified direction, and 0. p. 963867(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. p. 91389 for ordinary undirected percolation The exponent γ is estimated as γ = 2. p. 91423(4), again distinctly different from the known value for undirected percolation, which is γ = 43/18 = 2. p. 9389 The correlation length exponent ν satisfies the hyperscaling relation dν = 2β + γ where d is the system dimension, giving ν = β + 1/2γ = 1. p. 73330(3) The fractal dimension of the percolating strongly-connected cluster can be calculated from either β or γ as df = d - β/ν = 1. p. 98036(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. p. 1 p. 1 p. 1zip 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. p. 9c 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. p. 9 (5) to estimate the value of RL(pc) with best estimates of pc for each lattice from Section IV A The error on RL is estimated by combining the direct statistical uncertainty to estimate the total error on RL For the calculations of critical exponents in Section IV C we perform direct measurements of the largest and average sizes of the strongly-connected clusters for each of our four lattices for system sizes up to L = 1024 The scaling collapses in Fig. p. 9 9 use the incremental algorithm of Section III B, which allows us to calculate complete curves of cluster size against p In appendix B, we give further details of the numerical methods and calculations underlying the results in this paper 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. (5) to estimate the value of RL(pc) with best estimates of pc for each lattice from Section IV A The error on RL is estimated by combining the direct statistical uncertainty to estimate the total error on RL For the random diode model no such calculations are needed since we know the percolation threshold pc = 1 exactly (see Section IV A) 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
Final Exponent Estimates
Combining values across all four lattices, our best overall estimates of pc = 0.697160(2) for the Manhattan lattice, 0.740193(4) for the L-lattice, and 0.708838(4) for the ice model The values differ considerably from the values for ordinary undirected percolation We note that the probability for crossing in one direction across the square system is suspiciously close to 0. p. 975 The data are compatible—to within parts in 10 5—with the hypothesis that RL(pc) = 3/4 exactly for this definition
Final Exponent Comparison
The values of β and γ suggest a combined estimate of df = 1.8035(1), which is slightly lower than the value given recently by Wang and Li 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 The fractal dimension dh of the hull is estimated to be dh = 1. p. 13331(2), which is consistent with the hypothesis that dh = 4/3 exactly The work described here could be extended in a number of directions The code for the calculations in this paper is available for download from https://umich. p. 1edu/ mejn/scc.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved understanding of cluster topology in directed networks: The system can now accurately predict whether a bond addition will join
many smaller clusters into a single large one
by maintaining an additionalcondensation graph,
which is described asnecessarily acyclic.
-
Enhanced critical parameter estimation: The AI can estimate the percolation threshold pc for various directed lattices, such as the Manhattan lattice (0.6971571(5)) and the L-lattice (0.7401931(10)), using efficient methods like binary search combined with Tarjan's algorithm, rather than less satisfactory measures based on strongly-connected cluster sizes alone.
-
Accurate determination of fractal dimensions: The system can calculate the fractal dimension of the percolating strongly-connected cluster as a function of lattice type, yielding estimates such as df = 1.8035(1) for Manhattan lattices, which rules out conjectures that
beta takes exactly twice the value of the corresponding exponent for ordinary percolation.
-
Predictive modeling of wrapping phenomena: The AI can estimate the probability RL(pc) that a system has a
wrapping cluster
around periodic boundaries, yielding best overall estimates like 0.86117(6) for any direction, which issubstantially higher than the corresponding probability for ordinary percolation.
-
Optimized simulation and measurement algorithms: The AI can utilize incremental algorithms with an improved running time of O(M4/3) to calculate a complete curve of properties Q(p) over the entire range of p from zero to one in a single run, which is useful for calculating
a complete curve of Q(p) from p = 0 to 1.
Sources
- Percolation transition of strongly connected clusters in finite dimensions and on complete graphs
- The Planar Lattice Two-Neighbor Graph Percolates
- Janus Percolation in Anisotropic Limited-Degree Networks
Related papers
- Emergent long-tail dynamics in driven magnets with dynamical frustration
- Statistical Mechanics of Dynamical System Identification
- Second law of thermodynamics in closed quantum many-body systems
- Chemical potentials from structure factors: II. Charged multi-component mixtures
- Genuine quantum scars in Floquet chaotic many-body systems
- Stochastic Thermodynamics for Autoregressive Generative Models: A Non-Markovian Perspective