Optimal paths and domain walls in the strong disorder limit

Unified scaling for the optimal path length in disordered lattices

In recent decades, much attention has been focused on the topic of optimal paths in weighted networks due to its broad scientific interest and technological applications. In this work we revisit the problem of the optimal path between two points and focus on the role of the geometry (size and shape) of the embedding lattice, which has received very little attention. This role becomes crucial, for example, in the strong disorder (SD) limit, where the mean length of the optimal path (ℓ[over ¯]_{opt}) for a fixed end-to-end distance r diverges as the lattice size L increases. We propose a unified scaling ansatz for ℓ[over ¯]_{opt} in D-dimensional disordered lattices. Our ansatz introduces two exponents, φ and χ, which respectively characterize the scaling of ℓ[over ¯]_{opt} with r for fixed L, and the scaling of ℓ[over ¯]_{opt} with L for fixed r, both in the SD limit. The ansatz is supported by a comprehensive numerical study of the problem on 2D lattices, yet we also present results in D=3. We show that it unifies well-known results in the strong and weak disorder regimes, including the crossover behavior, but it also reveals novel scaling scenarios not yet addressed. Moreover, it provides relevant insights into the origin of the universal exponents characterizing the scaling of the optimal path in the SD limit. For example, for the fractal dimension of the optimal path in the SD limit, d_{opt}, we find d_{opt}=φ+χ.

Green's functions for random resistor networks

We analyze random resistor networks through a study of lattice Green's functions in arbitrary dimensions. We develop a systematic disorder perturbation expansion to describe the weak disorder regime of such a system. We use this formulation to compute ensemble-averaged nodal voltages and bond currents in a hierarchical fashion. We verify the validity of this expansion with direct numerical simulations of a square lattice with resistances at each bond exponentially distributed. Additionally, we construct a formalism to recursively obtain the exact Green's functions for finitely many disordered bonds. We provide explicit expressions for lattices with up to four disordered bonds, which can be used to predict nodal voltage distributions for arbitrarily large disorder strengths. Finally, we introduce a novel order parameter that measures the overlap between the bond current and the optimal path (the path of least resistance), for a given resistance configuration, which helps to characterize the weak and strong disorder regimes of the system.

Ground-state stability and the nature of the spin glass phase

We propose an approach toward understanding the spin glass phase at zero and low temperature by studying the stability of a spin glass ground state against perturbations of a single coupling. After reviewing the concepts of flexibility, critical droplet, and related quantities for both finite- and infinite-volume ground states, we study some of their properties and review three models in which these quantities are partially or fully understood. We also review a recent result showing the connection between our approach and that of disorder chaos. We then view four proposed scenarios for the low-temperature spin glass phase-replica symmetry breaking, scaling-droplet, TNT, and chaotic pairs-through the lens of the predictions of each scenario for the lowest-energy large-lengthscale excitations above the ground state. Using a new concept called σ-criticality, which quantifies the sensitivity of ground states to single-bond coupling variations, we show that each of these four pictures can be identified with different critical droplet geometries and energies. We also investigate necessary and sufficient conditions for the existence of multiple incongruent ground states.

Universality class for loopless invasion percolation models and a percolation avalanche burst model for hydraulic fracturing

Invasion percolation is a model that was originally proposed to describe growing networks of fractures. Here we describe a loopless algorithm on random lattices, coupled with an avalanche-based model for bursts. The model reproduces the characteristic b-value seismicity and spatial distribution of bursts consistent with earthquakes resulting from hydraulic fracturing ("fracking"). We test models for both site invasion percolation and bond invasion percolation. These have differences on the scale of site and bond lengths l. But since the networks are characterized by their large-scale behavior, l≪L, we find small differences between scaling exponents. Though data may not differentiate between models, our results suggest that both models belong to different universality classes.

Sequential disruption of the shortest path in critical percolation

We investigate the effect of sequentially disrupting the shortest path of percolation clusters at criticality by comparing it with the shortest alternative path. We measure the difference in length and the enclosed area between the two paths. The sequential approach allows us to study spatial correlations. We find the lengths of the segments of successively constant differences in length to be uncorrelated. Simultaneously, we study the distance between red bonds. We find the probability distributions for the enclosed areas A, the differences in length Δl, and the lengths between the red bonds l_{r} to follow power-law distributions. Using maximum likelihood estimation and extrapolation we find the exponents β=1.38±0.03 for Δl, α=1.186±0.008 for A, and δ=1.64±0.03 for the distribution of l_{r}.

A universal approach for drainage basins

Drainage basins are essential to Geohydrology and Biodiversity. Defining those regions in a simple, robust and efficient way is a constant challenge in Earth Science. Here, we introduce a model to delineate multiple drainage basins through an extension of the Invasion Percolation-Based Algorithm (IPBA). In order to prove the potential of our approach, we apply it to real and artificial datasets. We observe that the perimeter and area distributions of basins and anti-basins display long tails extending over several orders of magnitude and following approximately power-law behaviors. Moreover, the exponents of these power laws depend on spatial correlations and are invariant under the landscape orientation, not only for terrestrial, but lunar and martian landscapes. The terrestrial and martian results are statistically identical, which suggests that a hypothetical martian river would present similarity to the terrestrial rivers. Finally, we propose a theoretical value for the Hack’s exponent based on the fractal dimension of watersheds, γ = D/2. We measure γ = 0.54 ± 0.01 for Earth, which is close to our estimation of γ ≈ 0.55. Our study suggests that Hack’s law can have its origin purely in the maximum and minimum lines of the landscapes.

From Spin Glasses to Negative-Weight Percolation

Spin glasses are prototypical random systems modelling magnetic alloys. One important way to investigate spin glass models is to study domain walls. For two dimensions, this can be algorithmically understood as the calculation of a shortest path, which allows for negative distances or weights. This led to the creation of the negative weight percolation (NWP) model, which is presented here along with all necessary basics from spin glasses, graph theory and corresponding algorithms. The algorithmic approach involves a mapping to the classical matching problem for graphs. In addition, a summary of results is given, which were obtained during the past decade. This includes the study of percolation transitions in dimension from d=2 up to and beyond the upper critical dimension du=6, also for random graphs. It is shown that NWP is in a different universality class than standard percolation. Furthermore, the question of whether NWP exhibits properties of Stochastic–Loewner Evolution is addressed and recent results for directed NWP are presented.

A comparison of hydrological and topological watersheds

We introduce the hydrological watershed, a watershed where water can penetrate the soil, and compare it with the topological watershed for a two-dimensional landscape. For this purpose, we measure the fractal dimension of the hydrological watershed for different penetration depths and different grid sizes. Through finite size scaling, we find that the fractal dimension is 1.31 ± 0.02 which is significantly higher than the fractal dimension of the topological watershed. This indicates that the hydrological watershed belongs to a new universality class. We also find that, as opposed to the topological watershed, the hydrodynamic watershed can exhibit disconnected islands.

Fractal dimension of interfaces in Edwards-Anderson spin glasses for up to six space dimensions

The fractal dimension of domain walls produced by changing the boundary conditions from periodic to antiperiodic in one spatial direction is studied using both the strong-disorder renormalization group algorithm and the greedy algorithm for the Edwards-Anderson Ising spin-glass model for up to six space dimensions. We find that for five or fewer space dimensions, the fractal dimension is lower than the space dimension. This means that interfaces are not space filling, thus implying that replica symmetry breaking is absent in space dimensions fewer than six. However, the fractal dimension approaches the space dimension in six dimensions, indicating that replica symmetry breaking occurs above six dimensions. In two space dimensions, the strong-disorder renormalization group results for the fractal dimension are in good agreement with essentially exact numerical results, but the small difference is significant. We discuss the origin of this close agreement. For the greedy algorithm there is analytical expectation that the fractal dimension is equal to the space dimension in six dimensions and our numerical results are consistent with this expectation.

Abnormal grain growth mediated by fractal boundary migration at the nanoscale

Modern engineered materials are composed of space-filling grains or domains separated by a network of interfaces or boundaries. Such polycrystalline microstructures have the capacity to coarsen through boundary migration. Grain growth theories account for the topology of grains and the connectivity of the boundary network in terms of the familiar Euclidian dimension and Euler’s polyhedral formula, both of which are based on integer numbers. However, we recently discovered an unusual growth mode in a nanocrystalline Pd-Au alloy, in which grains develop complex, highly convoluted surface morphologies that are best described by a fractional dimension of ∼1.2 (extracted from the perimeters of grain cross sections). This fractal value is characteristic of a variety of domain growth scenarios—including explosive percolation, watersheds of random landscapes, and the migration of domain walls in a random field of pinning centers—which suggests that fractal grain boundary migration could be a manifestation of the same universal behavior.

Fractal Dimension of Interfaces in Edwards-Anderson and Long-range Ising Spin Glasses: Determining the Applicability of Different Theoretical Descriptions

The fractal dimension of excitations in glassy systems gives information on the critical dimension at which the droplet picture of spin glasses changes to a description based on replica symmetry breaking where the interfaces are space filling. Here, the fractal dimension of domain-wall interfaces is studied using the strong-disorder renormalization group method pioneered by Monthus [Fractals 23, 1550042 (2015)FRACEG0218-348X10.1142/S0218348X15500425] both for the Edwards-Anderson spin-glass model in up to 8 space dimensions, as well as for the one-dimensional long-ranged Ising spin-glass with power-law interactions. Analyzing the fractal dimension of domain walls, we find that replica symmetry is broken in high-enough space dimensions. Because our results for high-dimensional hypercubic lattices are limited by their small size, we have also studied the behavior of the one-dimensional long-range Ising spin-glass with power-law interactions. For the regime where the power of the decay of the spin-spin interactions with their separation distance corresponds to 6 and higher effective space dimensions, we find again the broken replica symmetry result of space filling excitations. This is not the case for smaller effective space dimensions. These results show that the dimensionality of the spin glass determines which theoretical description is appropriate. Our results will also be of relevance to the Gardner transition of structural glasses.

Loop-erased random walk on a percolation cluster is compatible with Schramm-Loewner evolution

We study the scaling limit of a planar loop-erased random walk (LERW) on the percolation cluster, with occupation probability p≥p(c). We numerically demonstrate that the scaling limit of planar LERW(p) curves, for all p>p(c), can be described by Schramm-Loewner evolution (SLE) with a single parameter κ that is close to the normal LERW in a Euclidean lattice. However, our results reveal that the LERW on critical incipient percolation clusters is compatible with SLE, but with another diffusivity coefficient κ. Several geometrical tests are applied to ascertain this. All calculations are consistent with SLE(κ), where κ=1.732±0.016. This value of the diffusivity coefficient is outside the well-known duality range 2≤κ≤8. We also investigate how the winding angle of the LERW(p) crosses over from Euclidean to fractal geometry by gradually decreasing the value of the parameter p from 1 to p(c). For finite systems, two crossover exponents and a scaling relation can be derived. This finding should, to some degree, help us understand and predict the existence of conformal invariance in disordered and fractal landscapes.

Short-range Ising spin glasses: the metastate interpretation of replica symmetry breaking

Parisi's formal replica-symmetry-breaking (RSB) scheme for mean-field spin glasses has long been interpreted in terms of many pure states organized ultrametrically. However, the early version of this interpretation, as applied to the short-range Edwards-Anderson model, runs into problems because as shown by Newman and Stein (NS) it does not allow for chaotic size dependence, and predicts non-self-averaging that cannot occur. NS proposed the concept of the metastate (a probability distribution over infinite-size Gibbs states in a given sample that captures the effects of chaotic size dependence) and a nonstandard interpretation of the RSB results in which the metastate is nontrivial and is responsible for what was called non-self-averaging. In this picture, each state drawn from the metastate has the ultrametric properties of the old theory, but when the state is averaged using the metastate, the resulting mixed state has little structure. This picture was constructed so as to agree both with the earlier RSB results and with rigorous results. Here we use the effective field theory of RSB, in conjunction with the rigorous definitions of pure states and the metastate in infinite-size systems, to show that the nonstandard picture follows directly from the RSB mean-field theory. In addition, the metastate-averaged state possesses power-law correlations throughout the low-temperature phase; the corresponding exponent ζ takes the value 4 according to the field theory in high dimensions d, and describes the effective fractal dimension of clusters of spins. Further, the logarithm of the number of pure states in the decomposition of the metastate-averaged state that can be distinguished if only correlations in a window of size W can be observed is of order W(d-ζ). These results extend the nonstandard picture quantitatively; we show that arguments against this scenario are inconclusive. More generally, in terms of Parisi's function q(x), if q(0)≠∫(0)(1)dxq(x), then the metastate is nontrivial. In an Appendix, we also prove rigorously that the metastate-averaged state of the Sherrington-Kirkpatrick model is a uniform distribution on all spin configurations at all temperatures.

Loop-erased random walk on a percolation cluster: crossover from Euclidean to fractal geometry

We study loop-erased random walk (LERW) on the percolation cluster, with occupation probability p ≥ p_{c}, in two and three dimensions. We find that the fractal dimensions of LERW_{p} are close to normal LERW in a Euclidean lattice, for all p>p_{c}. However, our results reveal that LERW on critical incipient percolation clusters is fractal with d_{f}=1.217 ± 0.002 for d=2 and 1.43 ± 0.02 for d=3, independent of the coordination number of the lattice. These values are consistent with the known values for optimal path exponents in strongly disordered media. We investigate how the behavior of the LERW_{p} crosses over from Euclidean to fractal geometry by gradually decreasing the value of the parameter p from 1 to p_{c}. For finite systems, two crossover exponents and a scaling relation can be derived. This work opens up a theoretical window regarding the diffusion process on fractal and random landscapes.

Boolean decision problems with competing interactions on scale-free networks: equilibrium and nonequilibrium behavior in an external bias

We study the equilibrium and nonequilibrium properties of Boolean decision problems with competing interactions on scale-free networks in an external bias (magnetic field). Previous studies at zero field have shown a remarkable equilibrium stability of Boolean variables (Ising spins) with competing interactions (spin glasses) on scale-free networks. When the exponent that describes the power-law decay of the connectivity of the network is strictly larger than 3, the system undergoes a spin-glass transition. However, when the exponent is equal to or less than 3, the glass phase is stable for all temperatures. First, we perform finite-temperature Monte Carlo simulations in a field to test the robustness of the spin-glass phase and show that the system has a spin-glass phase in a field, i.e., exhibits a de Almeida-Thouless line. Furthermore, we study avalanche distributions when the system is driven by a field at zero temperature to test if the system displays self-organized criticality. Numerical results suggest that avalanches (damage) can spread across the whole system with nonzero probability when the decay exponent of the interaction degree is less than or equal to 2, i.e., that Boolean decision problems on scale-free networks with competing interactions can be fragile when not in thermal equilibrium.

Self-organized criticality in glassy spin systems requires a diverging number of neighbors

We investigate the conditions required for general spin systems with frustration and disorder to display self-organized criticality, a property which so far has been established only for the fully connected infinite-range Sherrington-Kirkpatrick Ising spin-glass model [Phys. Rev. Lett. 83, 1034 (1999)]. Here, we study both avalanche and magnetization jump distributions triggered by an external magnetic field, as well as internal field distributions in the short-range Edwards-Anderson Ising spin glass for various space dimensions between 2 and 8, as well as the fixed-connectivity mean-field Viana-Bray model. Our numerical results, obtained on systems of unprecedented size, demonstrate that self-organized criticality is recovered only in the strict limit of a diverging number of neighbors and is not a generic property of spin-glass models in finite space dimensions.

Exact evaluation of the cutting path length in a percolation model on a hierarchical network

This work presents an approach to evaluate the exact value of the fractal dimension of the cutting path d(f)(CP) on hierarchical structures with finite order of ramification. Our approach is based on a renormalization group treatment of the universality class of watersheds. By making use of the self-similar property, we show that d(f)(CP) depends only on the average cutting path (CP) of the first generation of the structure. For the simplest Wheastone hierarchical lattice (WHL), we present a mathematical proof. For a larger WHL structure, the exact value of d(f)(CP) is derived based on a computer algorithm that identifies the length of all possible CP's of the first generation.

Percolation thresholds on planar Euclidean relative-neighborhood graphs

In the present article, statistical properties regarding the topology and standard percolation on relative neighborhood graphs (RNGs) for planar sets of points, considering the Euclidean metric, are put under scrutiny. RNGs belong to the family of "proximity graphs"; i.e., their edgeset encodes proximity information regarding the close neighbors for the terminal nodes of a given edge. Therefore they are, e.g., discussed in the context of the construction of backbones for wireless ad hoc networks that guarantee connectedness of all underlying nodes. Here, by means of numerical simulations, we determine the asymptotic degree and diameter of RNGs and we estimate their bond and site percolation thresholds, which were previously conjectured to be nontrivial. We compare the results to regular 2D graphs for which the degree is close to that of the RNG. Finally, we deduce the common percolation critical exponents from the RNG data to verify that the associated universality class is that of standard 2D percolation.

Universality class of the two-dimensional randomly distributed growing-cluster percolation model

We consider the "Touch and Stop" cluster growth percolation (CGP) model on the two-dimensional square lattice. A key parameter in the model is the fraction p of occupied "seed" sites that act as nucleation centers from which a particular cluster growth procedure is started. Here, we consider two growth styles: rhombic and disk-shaped cluster growth. For intermediate values of p the final state, attained by the growth procedure, exhibits a cluster of occupied sites that span the entire lattice. Using numerical simulations we investigate the percolation probability and the order parameter and perform a finite-size scaling analysis for lattices of side length up to L=1024 in order to carefully determine the critical exponents that govern the respective transition. In contrast to previous studies, reported in Tsakiris et al. [Phys. Rev. E 82, 041108 (2010)], we find strong numerical evidence that the CGP model is in the standard percolation universality class.

Fracturing highly disordered materials

We investigate the role of disorder on the fracturing process of heterogeneous materials by means of a two-dimensional fuse network model. Our results in the extreme disorder limit reveal that the backbone of the fracture at collapse, namely, the subset of the largest fracture that effectively halts the global current, has a fractal dimension of 1.22 ± 0.01. This exponent value is compatible with the universality class of several other physical models, including optimal paths under strong disorder, disordered polymers, watersheds and optimal path cracks on uncorrelated substrates, hulls of explosive percolation clusters, and strands of invasion percolation fronts. Moreover, we find that the fractal dimension of the largest fracture under extreme disorder, d(f) = 1.86 ± 0.01, is outside the statistical error bar of standard percolation. This discrepancy is due to the appearance of trapped regions or cavities of all sizes that remain intact till the entire collapse of the fuse network, but are always accessible in the case of standard percolation. Finally, we quantify the role of disorder on the structure of the largest cluster, as well as on the backbone of the fracture, in terms of a distinctive transition from weak to strong disorder characterized by a new crossover exponent.

Watersheds are Schramm-Loewner evolution curves

We show that in the continuum limit watersheds dividing drainage basins are Schramm-Loewner evolution (SLE) curves, being described by one single parameter κ. Several numerical evaluations are applied to ascertain this. All calculations are consistent with SLE(κ), with κ = 1.734 ± 0.005, being the only known physical example of an SLE with κ<2. This lies outside the well-known duality conjecture, bringing up new questions regarding the existence and reversibility of dual models. Furthermore, it constitutes a strong indication for conformal invariance in random landscapes and suggests that watersheds likely correspond to a logarithmic conformal field theory with a central charge c ≈ -7/2.

Analysis of the loop length distribution for the negative-weight percolation problem in dimensions d=2 through d=6

We consider the negative weight percolation (NWP) problem on hypercubic lattice graphs with fully periodic boundary conditions in all relevant dimensions from d=2 to the upper critical dimension d=6. The problem exhibits edge weights drawn from disorder distributions that allow for weights of either sign. We are interested in the full ensemble of loops with negative weight, i.e., nontrivial (system spanning) loops as well as topologically trivial ("small") loops. The NWP phenomenon refers to the disorder driven proliferation of system spanning loops of total negative weight. While previous studies where focused on the latter loops, we here put under scrutiny the ensemble of small loops. Our aim is to characterize-using this extensive and exhaustive numerical study-the loop length distribution of the small loops right at and below the critical point of the hypercubic setups by means of two independent critical exponents. These can further be related to the results of previous finite-size scaling analyses carried out for the system spanning loops. For the numerical simulations, we employed a mapping of the NWP model to a combinatorial optimization problem that can be solved exactly by using sophisticated matching algorithms. This allowed us to study here numerically exact very large systems with high statistics.

How to share underground reservoirs

Many resources, such as oil, gas, or water, are extracted from porous soils and their exploration is often shared among different companies or nations. We show that the effective shares can be obtained by invading the porous medium simultaneously with various fluids. Partitioning a volume in two parts requires one division surface while the simultaneous boundary between three parts consists of lines. We identify and characterize these lines, showing that they form a fractal set consisting of a single thread spanning the medium and a surrounding cloud of loops. While the spanning thread has fractal dimension 1.55 ± 0.03, the set of all lines has dimension 1.69 ± 0.02. The size distribution of the loops follows a power law and the evolution of the set of lines exhibits a tricritical point described by a crossover with a negative dimension at criticality.

Corrections to scaling for watersheds, optimal path cracks, and bridge lines

We study the corrections to scaling for the mass of the watershed, the bridge line, and the optimal path crack in two and three dimensions (2D and 3D). We disclose that these models have numerically equivalent fractal dimensions and leading correction-to-scaling exponents. We conjecture all three models to possess the same fractal dimension, namely, d(f) =1.2168 ± 0.0005 in 2D and d(f) = 2.487 ± 0.003 in 3D, and the same exponent of the leading correction, Ω = 0.9 ± 0.1 and Ω=1.0 ± 0.1, respectively. The close relations between watersheds, optimal path cracks in the strong disorder limit, and bridge lines are further supported by either heuristic or exact arguments.

Fracturing ranked surfaces

Discretized landscapes can be mapped onto ranked surfaces, where every element (site or bond) has a unique rank associated with its corresponding relative height. By sequentially allocating these elements according to their ranks and systematically preventing the occupation of bridges, namely elements that, if occupied, would provide global connectivity, we disclose that bridges hide a new tricritical point at an occupation fraction p = p_c, where p_c is the percolation threshold of random percolation. For any value of p in the interval p_c < p ≤ 1, our results show that the set of bridges has a fractal dimension d_BB ≈ 1.22 in two dimensions. In the limit p → 1, a self-similar fracture is revealed as a singly connected line that divides the system in two domains. We then unveil how several seemingly unrelated physical models tumble into the same universality class and also present results for higher dimensions.

Bohman-Frieze-Wormald model on the lattice, yielding a discontinuous percolation transition

The BFW model introduced by Bohman, Frieze, and Wormald [Random Struct. Algorithms, 25, 432 (2004)], and recently investigated in the framework of discontinuous percolation by Chen and D'Souza [Phys. Rev. Lett. 106, 115701 (2011)], is studied on the square and simple-cubic lattices. In two and three dimensions, we find numerical evidence for a strongly discontinuous transition. In two dimensions, the clusters at the threshold are compact with a fractal surface of fractal dimension d(f)=1.49±0.02. On the simple-cubic lattice, distinct jumps in the size of the largest cluster are observed. We proceed to analyze the tree-like version of the model, where only merging bonds are sampled, for dimension two to seven. The transition is again discontinuous in any considered dimension. Finally, the dependence of the cluster-size distribution at the threshold on the spatial dimension is also investigated.

Mean-field behavior of the negative-weight percolation model on random regular graphs

We investigate both analytically and numerically the ensemble of minimum-weight loops in the negative-weight percolation model on random graphs with fixed connectivity and bimodal weight distribution. This allows us to study the mean-field behavior of this model. The analytical study is based on a conjectured equivalence with the problem of self-avoiding walks in a random medium. The numerical study is based on a mapping to a standard minimum-weight matching problem for which fast algorithms exist. Both approaches yield results that are in agreement on the location of the phase transition, on the value of critical exponents, and on the absence of any sizable indications of a glass phase. By these results, the previously conjectured upper critical dimension of d(u)=6 is confirmed.

Gaussian model of explosive percolation in three and higher dimensions

The Gaussian model of discontinuous percolation, recently introduced by Araújo and Herrmann [Phys. Rev. Lett. 105, 035701 (2010)], is numerically investigated in three dimensions, disclosing a discontinuous transition. For the simple cubic lattice, in the thermodynamic limit we report a finite jump of the order parameter J=0.415±0.005. The largest cluster at the threshold is compact, but its external perimeter is fractal with fractal dimension d(A)=2.5±0.2. The study is extended to hypercubic lattices up to six dimensions and to the mean-field limit (infinite dimension). We find that, in all considered dimensions, the percolation transition is discontinuous. The value of the jump in the order parameter, the maximum of the second moment, and the percolation threshold are analyzed, revealing interesting features of the transition and corroborating its discontinuous nature in all considered dimensions. We also show that the fractal dimension of the external perimeter, for any dimension, is consistent with the one from bridge percolation and establish a lower bound for the percolation threshold of discontinuous models with a finite number of clusters at the threshold.

Scaling relations for watersheds

We study the morphology of watersheds in two and three dimensional systems subjected to different degrees of spatial correlations. The response of these objects to small, local perturbations is also investigated with extensive numerical simulations. We find the fractal dimension of the watersheds to generally decrease with the Hurst exponent, which quantifies the degree of spatial correlations. Moreover, in two dimensions, our results match the range of fractal dimensions 1.10≤d(f)≤1.15 observed for natural landscapes. We report that the watershed is strongly affected by local perturbations. For perturbed two and three dimensional systems, we observe a power-law scaling behavior for the distribution of areas (volumes) enclosed by the original and the displaced watershed and for the distribution of distances between outlets. Finite-size effects are analyzed and the resulting scaling exponents are shown to depend significantly on the Hurst exponent. The intrinsic relation between watershed and invasion percolation, as well as relations between exponents conjectured in previous studies with two dimensional systems, are now confirmed by our results in three dimensions.

Optimal-path cracks in correlated and uncorrelated lattices

The optimal path crack model on uncorrelated surfaces, recently introduced by Andrade et al. [Phys. Rev. Lett. 103, 225503 (2009).], is studied in detail and its main percolation exponents computed. In addition to β/ν=0.46±0.03, we report γ/ν=1.3±0.2 and τ=2.3±0.2. The analysis is extended to surfaces with spatial long-range power-law correlations, where nonuniversal fractal dimensions are obtained when the degree of correlation is varied. The model is also considered on a three-dimensional lattice, where the main crack is found to be a surface with a fractal dimension of 2.46±0.05.

Upper critical dimension of the negative-weight percolation problem

By means of numerical simulations, we investigate the geometric properties of loops on hypercubic lattice graphs in dimensions d=2 through 7, where edge weights are drawn from a distribution that allows for positive and negative weights. We are interested in the appearance of system-spanning loops of total negative weight. The resulting negative-weight percolation (NWP) problem is fundamentally different from conventional percolation, as we have seen in previous studies of this model for the two-dimensional case. Here, we characterize the transition for hypercubic systems, where the aim of the present study is to get a grip on the upper critical dimension d u of the NWP problem. For the numerical simulations, we employ a mapping of the NWP model to a combinatorial optimization problem that can be solved exactly by using sophisticated matching algorithms. We characterize the loops via observables similar to those in percolation theory and perform finite-size scaling analyses, e.g., three-dimensional hypercubic systems with side length up to L=56 sites, in order to estimate the critical properties of the NWP phenomenon. We find our numerical results consistent with an upper critical dimension d u=6 for the NWP problem.

Optimization of transport protocols with path-length constraints in complex networks

We propose a protocol optimization technique that is applicable to both weighted and unweighted graphs. Our aim is to explore by how much a small variation around the shortest-path or optimal-path protocols can enhance protocol performance. Such an optimization strategy can be necessary because even though some protocols can achieve very high traffic tolerance levels, this is commonly done by enlarging the path lengths, which may jeopardize scalability. We use ideas borrowed from extremal optimization to guide our algorithm, which proves to be an effective technique. Our method exploits the degeneracy of the paths or their close-weight alternatives, which significantly improves the scalability of the protocols in comparison to shortest-path or optimal-path protocols, keeping at the same time almost intact the length or weight of the paths. This characteristic ensures that the optimized routing protocols are composed of paths that are quick to traverse, avoiding negative effects in data communication due to path-length increases that can become specially relevant when information losses are present.

Thermodynamics of the Lévy spin glass

We investigate the Lévy glass, a mean-field spin-glass model with power-law distributed couplings characterized by a divergent second moment. By combining extensively many small couplings with a spare random backbone of strong bonds the model is intermediate between the Sherrington-Kirkpatrick and the Viana-Bray models. A truncated version where couplings smaller than some threshold ε are neglected can be studied within the cavity method developed for spin glasses on locally treelike random graphs. By performing the limit ε→0 in a well-defined way we calculate the thermodynamic functions within replica symmetry and determine the de Almeida-Thouless line in the presence of an external magnetic field. Contrary to previous findings we show that there is no replica-symmetric spin-glass phase. Moreover we determine the leading corrections to the ground-state energy within one-step replica symmetry breaking. The effects due to the breaking of replica symmetry appear to be small in accordance with the intuitive picture that a few strong bonds per spin reduce the degree of frustration in the system.

Modeling collective charge transport in nanoparticle assemblies

Mapping the assembled patterns of nanoparticles onto networks (mathematical graphs) provides a way for quantitative analysis of the structure effects on the physical properties of the assembly. Here we review the network modeling of the conduction with single-electron tunneling mechanisms in the assembled nanoparticle films. Simulations of the conduction predict the nonlinear current-voltage curves in different classes of the nanoparticle networks. Furthermore, the numerical analysis reveals how the I(V) nonlinearity is related to the collective charge fluctuations along the conducting paths through the sample, and stresses the role of the topology and quenched charge disorder.

Theory of minimum spanning trees. I. Mean-field theory and strongly disordered spin-glass model

The minimum spanning tree (MST) is a combinatorial optimization problem: given a connected graph with a real weight ("cost") on each edge, find the spanning tree that minimizes the sum of the total cost of the occupied edges. We consider the random MST, in which the edge costs are (quenched) independent random variables. There is a strongly disordered spin-glass model due to Newman and Stein [Phys. Rev. Lett. 72, 2286 (1994)], which maps precisely onto the random MST. We study scaling properties of random MSTs using a relation between Kruskal's greedy algorithm for finding the MST, and bond percolation. We solve the random MST problem on the Bethe lattice (BL) with appropriate wired boundary conditions and calculate the fractal dimension D=6 of the connected components. Viewed as a mean-field theory, the result implies that on a lattice in Euclidean space of dimension d , there are of order W(d-D) large connected components of the random MST inside a window of size W , and that d=d(c)=D=6 is a critical dimension. This differs from the value 8 suggested by Newman and Stein. We also critique the original argument for 8, and provide an improved scaling argument that again yields d(c)=6 . The result implies that the strongly disordered spin-glass model has many ground states for d>6 , and only of order one below six. The results for MSTs also apply on the Poisson-weighted infinite tree, which is a mean-field approach to the continuum model of MSTs in Euclidean space, and is a limit of the BL. In a companion paper we develop an epsilon=6-d expansion for the random MST on critical percolation clusters.

Theory of minimum spanning trees. II. Exact graphical methods and perturbation expansion at the percolation threshold

Continuing the program begun by the authors in a previous paper, we develop an exact low-density expansion for the random minimum spanning tree (MST) on a finite graph and use it to develop a continuum perturbation expansion for the MST on critical percolation clusters in space dimension d . The perturbation expansion is proved to be renormalizable in d=6 dimensions. We consider the fractal dimension D(p) of paths on the latter MST; our previous results lead us to predict that D(p)=2 for d>d(c)=6 . Using a renormalization-group approach, we confirm the result for d>6 and calculate D(p) to first order in epsilon=6-d for d<6 using the connection with critical percolation, with the result D(p)=2-epsilon/7+O(epsilon(2)) .

Fracturing the optimal paths

Optimal paths play a fundamental role in numerous physical applications ranging from random polymers to brittle fracture, from the flow through porous media to information propagation. Here for the first time we explore the path that is activated once this optimal path fails and what happens when this new path also fails and so on, until the system is completely disconnected. In fact many applications can also be found for this novel fracture problem. In the limit of strong disorder, our results show that all the cracks are located on a single self-similar connected line of fractal dimension D(b) approximately = 1.22. For weak disorder, the number of cracks spreads all over the entire network before global connectivity is lost. Strikingly, the disconnecting path (backbone) is, however, completely independent on the disorder.

Structural crossover of polymers in disordered media

We present a unified scaling theory for the structural behavior of polymers embedded in a disordered energy substrate. An optimal polymer configuration is defined as the polymer configuration that minimizes the sum of interacting energies between the monomers and the substrate. The fractal dimension of the optimal polymer in the limit of strong disorder (SD) was found earlier to be larger than the fractal dimension in weak disorder (WD). We introduce a scaling theory for the crossover between the WD and SD limits. For polymers of various sizes in the same disordered substrate we show that polymers with a small number of monomers N<<N* will behave as in SD, while large polymers with length N>>N* will behave as in WD. This implies that small polymers will be relatively more compact compared to large polymers even in the same substrate. The crossover length N* is a function of nu and a , where nu is the percolation correlation length exponent and a is the parameter which controls the broadness of the disorder. Furthermore, our results show that the crossover between the strong and weak disorder limits can be seen even within the same polymer configuration. If one focuses on a segment of size n<<N* within a long polymer (N>>N*) that segment will have a higher fractal dimension compared to a segment of size n>>N*.

Percolation clusters above criticality form Kardar-Parisi-Zhang surfaces

This study is concerned with the characteristics of regular (isotropic) percolation clusters above the critical threshold p{c}. Analytic arguments for the general dimension case, and numerical results for the two-dimensional case, lead to the conclusion that the characteristics of the shortest paths (defined as the chemical distance l) between given two sites on a percolation cluster are similar to the characteristics of optimal paths in the directed polymer model. A corollary which should be valid for the general dimension case, and verified by numerical results for the two-dimensional case, is that a cluster whose sites are at chemical distance l from a given site forms a Kardar-Parisi-Zhang surface.

Invasion percolation through minimum-weight spanning trees

Invasion percolation is often used to simulate capillary-dominated drainage and imbibition in pore networks. More than a decade ago it was observed that the part of a pore network that is involved in an invasion bond percolation is a minimum-weight spanning tree of the network, where the weights indicate resistances associated with the bonds. Thus, one can determine a minimum-weight spanning tree first and then run the invasion bond percolation on the minimum-weight spanning tree. The time complexities of the two steps are O(malpha(m,n)) and O(n) , respectively, where m is the number of edges, n is the number of vertices, and alpha(,) denotes the inverse Ackermann function. In this paper we (1) formulate the property of minimum-weight spanning trees that justifies the two-step approach to invasion bond percolation, (2) extend the two-step approach to invasion site percolation, and (3) further extend it to simulations of drainage (imbibition) that include trapping of the wetting (nonwetting) phase. In case of imbibition we also take snap-off into account. As a consequence, all these simulations can now be done in O(malpha(m,n)) .

Transport and percolation theory in weighted networks

We study the distribution P(sigma) of the equivalent conductance sigma for Erdös-Rényi (ER) and scale-free (SF) weighted resistor networks with N nodes. Each link has conductance g triple bond e-ax, where x is a random number taken from a uniform distribution between 0 and 1 and the parameter a represents the strength of the disorder. We provide an iterative fast algorithm to obtain P(sigma) and compare it with the traditional algorithm of solving Kirchhoff equations. We find, both analytically and numerically, that P(sigma) for ER networks exhibits two regimes: (i) A low conductance regime for sigma<e-apc, where pc=1/(k) is the critical percolation threshold of the network and k is the average degree of the network. In this regime P(sigma) is independent of N and follows the power law P(sigma) approximately sigma-alpha, where alpha=1-(ka)/a. (ii) A high conductance regime for sigma>e-apc in which we find that P(sigma) has strong N dependence and scales as P(sigma) approximately f(sigma,apc/N1/3) . For SF networks with degree distribution P(k) approximately k-lambda, kmin<or=k<or=kmax, we find numerically also two regimes, similar to those found for ER networks.

Screened nonbonded interactions in native proteins manipulate optimal paths for robust residue communication

A protein structure is represented as a network of residues whereby edges are determined by intramolecular contacts. We introduce inhomogeneity into these networks by assigning each edge a weight that is determined by amino acid pair potentials. Two methodologies are utilized to calculate the average path lengths (APLs) between pairs: to minimize i), the maximum weight in the strong APL, and ii), the total weight in the weak APL. We systematically screen edges that have higher than a cutoff potential and calculate the shortest APLs in these reduced networks, while keeping chain connectivity. Therefore, perturbations introduced at a selected region of the residue network propagate to remote regions only along the nonscreened edges that retain their ability to disseminate the perturbation. The shortest APLs computed from the reduced homogeneous networks with only the strongest few nonbonded pairs closely reproduce the strong APLs from the weighted networks. The rate of change in the APL in the reduced residue network as compared to its randomly connected counterpart remains constant until a lower bound. Upon further link removal, this property shows an abrupt increase toward a random coil behavior. Under different perturbation scenarios, diverse optimal paths emerge for robust residue communication.

Flows on graphs with random capacities

We investigate flows on graphs whose links have random capacities. For binary trees we derive the probability distribution for the maximal flow from the root to a leaf, and show that for infinite trees it vanishes beyond a certain threshold that depends on the distribution of capacities. We then examine the maximal total flux from the root to the leaves. Our methods generalize to simple graphs with loops, e.g., to hierarchical lattices and to complete graphs.

Optimal paths in complex networks with correlated weights: the worldwide airport network

We study complex networks with weights w(ij) associated with each link connecting node i and j. The weights are chosen to be correlated with the network topology in the form found in two real world examples: (a) the worldwide airport network and (b) the E. Coli metabolic network. Here w(ij) approximately equals x(ij)(k(i)k(j))alpha, where k(i) and k(j) are the degrees of nodes i and j , x(ij) is a random number, and alpha represents the strength of the correlations. The case alpha >0 represents correlation between weights and degree, while alpha< 0 represents anticorrelation and the case alpha=0 reduces to the case of no correlations. We study the scaling of the lengths of the optimal paths, l(opt), with the system size N in strong disorder for scale-free networks for different alpha. We find two different universality classes for l(opt), in strong disorder depending on alpha: (i) if alpha >0 , then for lambda >2 the scaling law l(opt) approximately equals N(1/3), where lambda is the power-law exponent of the degree distribution of scale-free networks, and (ii) if alpha< or =0 , then l(opt) approximately equals N((nu)(opt)) with nu(opt) identical to its value for the uncorrelated case alpha=0. We calculate the robustness of correlated scale-free networks with different alpha and find the networks with alpha< 0 to be the most robust networks when compared to the other values of alpha. We propose an analytical method to study percolation phenomena on networks with this kind of correlation, and our numerical results suggest that for scale-free networks with alpha< 0 , the percolation threshold p(c) is finite for lambda >3, which belongs to the same universality class as alpha=0 . We compare our simulation results with the real worldwide airport network, and we find good agreement.

Optimal response function in networks of excitatory elements

In this paper the problem of signal propagation in networks of excitatory elements is studied. It is found that the geometry of signal transmission paths depends crucially on how an excitatory element responds to a stimulus. Two types of responses are defined: fast and slow. In the slow response case the signal transmission paths are in the same universality class as optimal paths in the limit of strong disorder. The signal transmission paths formed in the fast response case constitute possibly a new universality class.

Transport in weighted networks: partition into superhighways and roads

Transport in weighted networks is dominated by the minimum spanning tree (MST), the tree connecting all nodes with the minimum total weight. We find that the MST can be partitioned into two distinct components, having significantly different transport properties, characterized by centrality--the number of times a node (or link) is used by transport paths. One component, superhighways, is the infinite incipient percolation cluster, for which we find that nodes (or links) with high centrality dominate. For the other component, roads, which includes the remaining nodes, low centrality nodes dominate. We find also that the distribution of the centrality for the infinite incipient percolation cluster satisfies a power law, with an exponent smaller than that for the entire MST. The significance of this finding is that one can improve significantly the global transport by improving a tiny fraction of the network, the superhighways.

Optimal paths in strong and weak disorder: a unified approach

We present a unified scaling theory for the optimal path connecting opposite edges of a disordered lattice of size L. Each bond of the lattice is assigned a cost exp(ar), where r is a uniformly distributed random variable and a is disorder strength. The optimal path minimizes the sum of the costs of the bonds along the path. We argue that for L>>a(nu) , where nu is the correlation exponent of percolation, the path becomes equivalent to a directed polymer on an effective lattice consisting of blobs of size xi=a(nu). It is self-affined and characterized by the roughness exponent of directed polymers chi. For L<<a(nu), or on the length scales below the blob size xi, the path behaves as an optimal path in the strong disorder limit. It has a self-similar fractal shape with fractal dimension d(opt). We derived the scaling relations for the length of the path, its transversal displacement, the average cost and its fluctuation. We test our scaling theoretical predictions by numerical simulations on a square lattice.

Universal behavior of optimal paths in weighted networks with general disorder

We study the statistics of the optimal path in both random and scale-free networks, where weights are taken from a general distribution P(w). We find that different types of disorder lead to the same universal behavior. Specifically, we find that a single parameter (S defined as AL(-1/v) for d-dimensional lattices, and S defined as AN(-1/3) for random networks) determines the distributions of the optimal path length, including both strong and weak disorder regimes. Here v is the percolation connectivity exponent, and A depends on the percolation threshold and P(w). We show that for a uniform P(w), Poisson or Gaussian, the crossover from weak to strong does not occur, and only weak disorder exists.