Optimal paths in disordered media: scaling of the crossover from self-similar to self-affine behavior

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.

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.

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.

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.

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.

Impact of perturbations on watersheds

We find that watersheds in real and artificial landscapes can be strongly affected by small, local perturbations like landslides or tectonic motions. We observe power-law scaling behavior for both the distribution of areas enclosed by the original and the displaced watershed as well as the probability density to induce, after perturbation, a change at a given distance. Scaling exponents for real and artificial landscapes are determined, where in the latter case the exponents depend linearly on the Hurst exponent of the applied fractional Brownian noise. The obtained power laws are shown to be independent on the strength of perturbation. Theoretical arguments relate our scaling laws for uncorrelated landscapes to properties of invasion percolation.

Explosive percolation via control of the largest cluster

We show that considering only the largest cluster suffices to obtain a first-order percolation transition. As opposed to previous realizations of explosive percolation, our models obtain Gaussian cluster distributions and compact clusters as one would expect at first-order transitions. We also discover that the cluster perimeters are fractal at the transition point, yielding a fractal dimension of 1.23 ± 0.03, close to that of watersheds.

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.

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.

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.

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.

Phase transition in the link weight structure of networks

When transport in networks follows the shortest paths, the link weights are shown to play a crucial role. If the underlying topology with nodes N is not changed and if the link weights are independent from each other, then we show that, by tuning the link weights, a phase transition occurs around a critical extreme value index alphac of the link weight distribution alpha<alphac. If the extreme value index of the link weight distribution , transport in the network traverses many links whereas for , all transport flows over a critical backbone consisting of N-1 links. For connected Erdös-Rényi random graphs Gp(N) and square lattices, we have characterised the phase transition and found that alphac approximately =bN(-beta) with betaGp(N) and betalattice approximately = 0.62.

Scaling of optimal-path-lengths distribution in complex networks

We study the distribution of optimal path lengths in random graphs with random weights associated with each link ("disorder"). With each link i we associate a weight tau(i) = exp (a r(i)), where r(i) is a random number taken from a uniform distribution between 0 and 1, and the parameter a controls the strength of the disorder. We suggest, in an analogy with the average length of the optimal path, that the distribution of optimal path lengths has a universal form that is controlled by the expression (1/p(c)) (l(infinity)/a), where l(infinity) is the optimal path length in strong disorder (a --> infinity) and p(c) is the percolation threshold. This relation is supported by numerical simulations for Erdos-Rényi and scale-free graphs. We explain this phenomenon by showing explicitly the transition between strong disorder and weak disorder at different length scales in a single network.

Resistance distribution in the hopping percolation model

We study the distribution function P (rho) of the effective resistance rho in two- and three-dimensional random resistor networks of linear size L in the hopping percolation model. In this model each bond has a conductivity taken from an exponential form sigma proportional to exp (-kappar) , where kappa is a measure of disorder and r is a random number, 0< or = r < or =1 . We find that in both the usual strong-disorder regime L/ kappa(nu) >1 (not sensitive to removal of any single bond) and the extreme-disorder regime L/ kappa(nu) <1 (very sensitive to such a removal) the distribution depends only on L/kappa(nu) and can be well approximated by a log-normal function with dispersion b kappa(nu) /L , where b is a coefficient which depends on the type of lattice, and nu is the correlation critical exponent.

Current flow in random resistor networks: the role of percolation in weak and strong disorder

We study the current flow paths between two edges in a random resistor network on a L X L square lattice. Each resistor has resistance e(ax) , where x is a uniformly distributed random variable and a controls the broadness of the distribution. We find that: (a) The scaled variable u identical with u congruent to L/a(nu) , where nu is the percolation connectedness exponent, fully determines the distribution of the current path length l for all values of u . For u >> 1, the behavior corresponds to the weak disorder limit and l scales as l approximately L, while for u << 1 , the behavior corresponds to the strong disorder limit with l approximately L(d(opt) ), where d(opt) =1.22+/-0.01 is the optimal path exponent. (b) In the weak disorder regime, there is a length scale xi approximately a(nu), below which strong disorder and critical percolation characterize the current path.

Effect of disorder strength on optimal paths in complex networks

We study the transition between the strong and weak disorder regimes in the scaling properties of the average optimal path l(opt) in a disordered Erdos-Rényi (ER) random network and scale-free (SF) network. Each link i is associated with a weight tau(i) identical withexp (a r(i) ) , where r(i) is a random number taken from a uniform distribution between 0 and 1 and the parameter a controls the strength of the disorder. We find that for any finite a , there is a crossover network size N* (a) at which the transition occurs. For N<<N* (a) the scaling behavior of l(opt) is in the strong disorder regime, with l(opt) approximately N(1/3) for ER networks and for SF networks with lambda>/=4 , and l(opt) approximately N (lambda-3) (/ (lambda-1) ) for SF networks with 3<lambda<4 . For N>>N* (a) the scaling behavior is in the weak disorder regime, with l(opt) approximately ln N for ER networks and SF networks with lambda>3 . In order to study the transition we propose a measure which indicates how close or far the disordered network is from the limit of strong disorder. We propose a scaling ansatz for this measure and demonstrate its validity. We proceed to derive the scaling relation between N* (a) and a . We find that N* (a) approximately a(3) for ER networks and for SF networks with lambda>/=4 , and N* (a) approximately a (lambda-1) (/ (lambda-3) ) for SF networks with 3<lambda<4 .

Universality of the optimal path in the strong disorder limit

We study numerically the optimal paths in two and three dimensions on various disordered lattices in the limit of strong disorder. We find that the length l of the optimal path scales with geometric distance r , as l approximately r (d(opt) ) with d(opt) =1.22+/-0.01 for d=2 and 1.44+/-0.02 for d=3 , independent of whether the optimization is on a path of weighted bonds or sites, and independent of the lattice or its coordination number. Our finding suggests that the exponent d(opt) is universal, depending only on the dimension of the system.

Percolation transition in a two-dimensional system of Ni granular ferromagnets

We model magnetotransport features of the quenched condensed granular Ni thin films by a random two-dimensional resistor network in order to test the condition where a single bond dominates the system. The hopping conductivity is assumed to depend on the distance between neighboring ferromagnetic grains and the mutual orientation of the magnetic moments of these grains. We find that the quantity characterizing the transition from weak disorder (not sensitive to a change of a single bond resistivity) to strong disorder (very sensitive to such changes) scales as kappa/L(1/1.3), where L is the size of the system and kappa is a measure of disorder.

Universality classes for self-avoiding walks in a strongly disordered system

We study the behavior of self-avoiding walks (SAWs) on square and cubic lattices in the presence of strong disorder. We simulate the disorder by assigning random energy epsilon taken from a probability distribution P(epsilon) to each site (or bond) of the lattice. We study the strong disorder limit for an extremely broad range of energies with P(epsilon) is proportional to 1/epsilon. For each configuration of disorder, we find by exact enumeration the optimal SAW of fixed length N and fixed origin that minimizes the sum of the energies of the visited sites (or bonds). We find the fractal dimension of the optimal path to be d(opt)=1.52+/-0.10 in two dimensions (2D) and d(opt)=1.82+/-0.08 in 3D. Our results imply that SAWs in strong disorder with fixed N are much more compact than SAWs in disordered media with a uniform distribution of energies, optimal paths in strong disorder with fixed end-to-end distance R, and SAWs on a percolation cluster. Our results are also consistent with the possibility that SAWs in strong disorder belong to the same universality class as the maximal SAW on a percolation cluster at criticality, for which we calculate the fractal dimension d(max)=1.64+/-0.02 for 2D and d(max)=1.87+/-0.05 for 3D, values very close to the fractal dimensions of the percolation backbone in 2D and 3D.

Minimum spanning trees on random networks

We show that the geometry of minimum spanning trees (MST) on random graphs is universal. Because of this geometric universality, we are able to characterize the energy of MST using a scaling distribution [P(epsilon)] found using uniform disorder. We show that the MST energy for other disorder distributions is simply related to P(epsilon). We discuss the relationship to invasion percolation, to the directed polymer in a random media, to uniform spanning trees, and also the implications for the broader issue of universality in disordered systems.