# Probability Distribution of the Shortest Path on the Percolation Cluster, its Backbone and Skeleton

## Abstract

We consider the mean distribution functions $`\mathrm{\Phi }(r|\mathrm{})`$, $`\mathrm{\Phi }_\mathrm{B}(r|\mathrm{})`$, and $`\mathrm{\Phi }_\mathrm{S}(r|\mathrm{})`$, giving the probability that two sites on the incipient percolation cluster, on its backbone and on its skeleton, respectively, connected by a shortest path of length $`\mathrm{}`$ are separated by an Euclidean distance $`r`$. Following a scaling argument due to de Gennes for self-avoiding walks, we derive analytical expressions for the exponents $`g_1=d_f+d_{\mathrm{min}}d`$ and $`g_1^\mathrm{B}=g_1^\mathrm{S}=3d_{\mathrm{min}}d`$, which determine the scaling behavior of the distribution functions in the limit $`xr/\mathrm{}^{\stackrel{~}{\nu }}1`$, i.e. $`\mathrm{\Phi }(r|\mathrm{})\mathrm{}^{\stackrel{~}{\nu }d}x^{g_1}`$, $`\mathrm{\Phi }_\mathrm{B}(r|\mathrm{})\mathrm{}^{\stackrel{~}{\nu }d}x^{g_1^\mathrm{B}}`$, and $`\mathrm{\Phi }_\mathrm{S}(r|\mathrm{})\mathrm{}^{\stackrel{~}{\nu }d}x^{g_1^\mathrm{S}}`$, with $`\stackrel{~}{\nu }1/d_{\mathrm{min}}`$, where $`d_f`$ and $`d_{\mathrm{min}}`$ are the fractal dimensions of the percolation cluster and the shortest path, respectively. The theoretical predictions for $`g_1`$, $`g_1^\mathrm{B}`$ and $`g_1^\mathrm{S}`$ are in very good agreement with our numerical results.

Percolation constitutes a useful model for a variety of disordered systems in many fields of science displaying both structural disorder and self-similarity (i.e. fractal behavior) within some range of length scales . In many circumstances, the knowledge of the internal structure of percolation clusters is required, as for instance in the study of transport processes near the percolation threshold $`p_\mathrm{c}`$, where the complex topology of the available conducting paths play a crucial role .

It is known that at the percolation threshold $`p_\mathrm{c}`$, the incipient infinite cluster displays fractal behavior over all length scales, i.e. its mass $`s`$ contained within a distance $`r`$ from a given cluster site chosen as the origin, averaged over many origins, scales as $`sr^{d_f}`$, where $`d_f=91/48`$ in two dimensions, $`d_f=2.524\pm 0.008`$ in three dimensions, and $`d_f=4`$ above the critical dimension, i.e. when $`dd_\mathrm{c}=6`$ . A second, useful metric is the “chemical” distance $`\mathrm{}`$ between two cluster sites , defined as the length of the shortest path connecting them. It is found that the mean distance $`r`$ between two cluster sites, averaged over many pairs of sites, behaves as a function of $`\mathrm{}`$ as $`r\mathrm{}^{1/d_{\mathrm{min}}}`$, where $`d_{\mathrm{min}}=1.130\pm 0.004`$ in $`d=2`$ , $`d_{\mathrm{min}}=1.374\pm 0.004`$ in $`d=3`$ , and $`d_{\mathrm{min}}=2`$ when $`dd_\mathrm{c}`$, is the so-called fractal dimension of the shortest path. From the above scaling relations follow that in “chemical” space, the mass of the cluster scales with distance $`\mathrm{}`$ as $`s\mathrm{}^d_{\mathrm{}}`$, where $`d_{\mathrm{}}=d_f/d_{\mathrm{min}}`$, with $`d_{\mathrm{}}=2`$ when $`dd_\mathrm{c}`$ .

The incipient infinite cluster exhibits a variety of substructures that are self-similar as well . A prominent example is the backbone of the cluster, defined as the subset of cluster sites that can carry a current when a potential difference is applied between two sites (see  and references therein). Thus, the structure of the backbone alone determines the conductivity of the whole percolation network between two sites. The structural and dynamical properties of the backbone of the incipient cluster have been studied recently . A second cluster substructure, denoted as the skeleton (a subset of the backbone, also called the “elastic” backbone) is defined as the union of all shortest paths between the two cluster sites.

In this Rapid Communication, we extend our previous studies of the structural properties of the incipient infinite cluster  and its backbone  in two and three dimensions. We consider the structural distribution function $`\mathrm{\Phi }(r|\mathrm{})`$ for the incipient infinite cluster, where $`\mathrm{\Phi }(r|\mathrm{})\mathrm{d}r`$ is the probability that two cluster sites connected by a shortest path of length $`\mathrm{}`$ are at Euclidean distance between $`r`$ and $`r+\mathrm{d}r`$ from each other in space. The probability distribution $`\mathrm{\Phi }(r|\mathrm{})`$ is normalized according to $`r^{d1}\mathrm{\Phi }(r|\mathrm{})dr=1`$, and is found to obey an scaling behavior with the variable $`xr/\mathrm{}^{\stackrel{~}{\nu }}`$ of the form $`\mathrm{\Phi }(r|\mathrm{})=\mathrm{}^{\stackrel{~}{\nu }d}f(x)`$ (see e.g. ), where $`\stackrel{~}{\nu }1/d_{\mathrm{min}}`$. Here, we draw our attention to the limit $`x1`$, where the scaling function $`f(x)`$ follows a simple power law, $`f(x)x^{g_1}`$, i.e.

$$\mathrm{\Phi }(r|\mathrm{})\frac{1}{\mathrm{}^{\stackrel{~}{\nu }d}}\left(\frac{r}{\mathrm{}^{\stackrel{~}{\nu }}}\right)^{g_1},\text{for }r/\mathrm{}^{\stackrel{~}{\nu }}1.$$
(1)   
Similar scaling forms for the substructural distribution functions as a function of $`xr/\mathrm{}^{\stackrel{~}{\nu }}`$, $`\mathrm{\Phi }_\mathrm{B}(r|\mathrm{})=\mathrm{}^{\stackrel{~}{\nu }d}f_\mathrm{B}(x)`$ for the backbone and $`\mathrm{\Phi }_\mathrm{S}(r|\mathrm{})=\mathrm{}^{\stackrel{~}{\nu }d}f_\mathrm{S}(x)`$ for the skeleton, are expected . In the case $`x1`$, the corresponding scaling functions, $`f_\mathrm{B}(x)`$ and $`f_\mathrm{S}(x)`$, are found to behave as $`f_\mathrm{B}(x)x^{g_1^\mathrm{B}}`$ and $`f_\mathrm{S}(x)x^{g_1^\mathrm{S}}`$, respectively, yielding

$$\mathrm{\Phi }_\mathrm{B}(r|\mathrm{})\frac{1}{\mathrm{}^{\stackrel{~}{\nu }d}}\left(\frac{r}{\mathrm{}^{\stackrel{~}{\nu }}}\right)^{g_1^\mathrm{B}}\text{and}\mathrm{\Phi }_\mathrm{S}(r|\mathrm{})\frac{1}{\mathrm{}^{\stackrel{~}{\nu }d}}\left(\frac{r}{\mathrm{}^{\stackrel{~}{\nu }}}\right)^{g_1^\mathrm{S}},\text{for }r/\mathrm{}^{\stackrel{~}{\nu }}1.$$
(2)   
Numerical results (see Refs.  and below) indicate that $`g_1<g_1^\mathrm{B}g_1^\mathrm{S}`$ in both two and three dimensions. For $`dd_\mathrm{c}`$, one expects the mean field (MF) values $`g_1=g_1^\mathrm{B}=g_1^\mathrm{S}=0`$, since percolation clusters behave similarly to simple random walks above the critical dimension $`d_\mathrm{c}`$ .

We first study the above defined distribution functions numerically, both in two and three dimensions. To this end, we generate large percolation cluster at $`p_\mathrm{c}`$ on square and s.c. lattices, respectively, using the well-known Leath algorithm . To identify the backbone and skeleton of the cluster, we apply an improved version  of the well-known burning algorithm . We perform averages over more than $`10^5`$ clusters, which are grown until they reach a maximum of chemical shells $`\mathrm{}_{\mathrm{max}}=2000`$ in $`d=2`$ and $`\mathrm{}_{\mathrm{max}}=1000`$ in $`d=3`$. The results for $`\mathrm{\Phi }(r|\mathrm{})`$, $`\mathrm{\Phi }_\mathrm{B}(r|\mathrm{})`$, and $`\mathrm{\Phi }_\mathrm{S}(r|\mathrm{})`$ are shown in Figs. 1, 2, and 3, respectively. For the incipient infinite cluster we obtain $`g_1=1.04\pm 0.05`$ in $`d=2`$ and $`g_1=0.88\pm 0.05`$ in $`d=3`$ (see also ). For the backbone, we find $`g_1^\mathrm{B}=1.34\pm 0.10`$ in $`d=2`$ and $`g_1^\mathrm{B}=1.08\pm 0.10`$ in $`d=3`$ (see also ). In addition, our results suggest that $`\mathrm{\Phi }_\mathrm{B}(r|\mathrm{})`$ and $`\mathrm{\Phi }_\mathrm{S}(r|\mathrm{})`$ coincide, within the accuracy of the present data, and as a result, the values of $`g_1^\mathrm{S}`$ for the skeleton are indistinguishable from those of the backbone, i.e. $`g_1^\mathrm{S}g_1^\mathrm{B}`$. These results are summarized in Table I.

To estimate values for the exponents $`g_1`$, $`g_1^\mathrm{B}`$ and $`g_1^\mathrm{S}`$ analytically, we follow a method similar to the one discussed by de Gennes  for determining the structure of self-avoiding walks (SAW) of $`N`$ steps. The latter is described by the probability distribution function $`P_{\mathrm{SAW}}(r|N)=N^{\nu d}f_{\mathrm{SAW}}(y)`$, with $`yr/N^\nu `$, where $`P_{\mathrm{SAW}}(r|N)\mathrm{d}r`$ gives the probability that the two end points of a SAW of fixed length $`N`$ (i.e. the first and the $`N+1`$ monomers) are at a distance between $`r`$ and $`r+\mathrm{d}r`$. Here, $`\nu `$ is the Flory exponent, $`\nu (d+2)/3`$ for $`d4`$ and $`\nu =\nu _{\mathrm{MF}}=\frac{1}{2}`$ for $`d4`$, and $`f_{\mathrm{SAW}}(y)`$ is the scaling function, with $`f_{\mathrm{SAW}}(y)y^g`$ when $`y1`$. For SAW defined on the lattice, de Gennes argues that the behavior of $`f_{\mathrm{SAW}}(y)`$ for $`y1`$ can be obtained by considering the probability $`P_{\mathrm{SAW}}(r1|N)`$ that a SAW of $`N1`$ steps returns close to its starting point (origin), which can be written as

$$P_{\mathrm{SAW}}(r1|N)\frac{N_{\mathrm{SAW}}^{r1}(N)}{N_{\mathrm{SAW}}(N)},\text{for }N1,$$
(3)   
where $`N_{\mathrm{SAW}}^{r1}(N)N^{\nu d}\overline{z}^N`$ is the number of SAW of length $`N`$ returning close to the origin and $`N_{\mathrm{SAW}}(N)N^{\gamma 1}\overline{z}^N`$ is the total number of SAW of length $`N`$. Here, $`\overline{z}`$ is the effective coordination number of the lattice, and $`\gamma `$ is the enhancement exponent, with $`\gamma =\gamma _{\mathrm{MF}}=1`$ for $`d4`$.

As noted by de Gennes , the enhancement factor $`N^{\gamma 1}`$ occurs only in the denominator of the ratio $`N_{\mathrm{SAW}}^{r1}(N)/N_{\mathrm{SAW}}(N)`$, but not in the numerator, indicating the “difficulty” for a SAW to return near to its starting point. Note that this missing enhancement factor in the numerator can be viewed as corresponding to its mean-field value, $`N^{\gamma _{\mathrm{MF}}1}1`$, and one can write equivalently

$$P_{\mathrm{SAW}}(r1|N)\frac{1}{N^{\nu d}}\frac{N^{\gamma _{\mathrm{MF}}1}}{N^{\gamma 1}},\text{for }N1,$$
(4)   
corresponding to the behavior $`f_{\mathrm{SAW}}(y)y^g`$, with $`g=(\gamma 1)/\nu `$. This observation suggested us a procedure for describing the structural function of the incipient percolation cluster and its substructures analytically, in the case $`r/\mathrm{}^{\stackrel{~}{\nu }}1`$. We consider the incipient percolation cluster first.

Let us generalize Eq. (4) to percolation clusters by writing the distribution function $`\mathrm{\Phi }(r|\mathrm{})`$, for a chemical distance $`\mathrm{}1`$ and Euclidean distance $`r1`$, as

$$\mathrm{\Phi }(r1|\mathrm{})\frac{1}{\mathrm{}^{\stackrel{~}{\nu }d}}\frac{\mathrm{\Pi }_{\mathrm{MF}}(\mathrm{})}{\mathrm{\Pi }(\mathrm{})},\text{for }\mathrm{}1,$$
(5)   
where $`\mathrm{\Pi }(\mathrm{})`$ plays the role of the function $`N^{\gamma 1}`$ in Eq. (4), and $`\mathrm{\Pi }_{\mathrm{MF}}(\mathrm{})`$ denotes its mean field value. Here we argue that, to a first approximation, $`\mathrm{\Pi }(\mathrm{})`$ is given by the probability that the two chosen sites are on a cluster of chemical size $`\mathrm{}`$. Therefore we relate $`\mathrm{\Pi }(\mathrm{})`$ to the probability distribution of cluster sizes $`sn(s)`$, which is known to behave as $`sn(s)s^{(\tau 1)}`$, with $`\tau =1+d/d_f`$ for $`dd_\mathrm{c}`$, and $`\tau _{\mathrm{MF}}=5/2`$ . Hence, $`\mathrm{\Pi }(\mathrm{})`$ is given by $`\mathrm{\Pi }(\mathrm{})sn(s)\mathrm{d}s/\mathrm{d}\mathrm{}`$, and noting that $`s\mathrm{}^d_{\mathrm{}}`$, we find $`\mathrm{\Pi }(\mathrm{})\mathrm{}^{d_{\mathrm{}}(\tau 2)1}`$ for $`dd_\mathrm{c}`$, and $`\mathrm{\Pi }_{\mathrm{MF}}(\mathrm{})\mathrm{}^2`$. Thus, Eq. (5) becomes

$$\mathrm{\Phi }(r1|\mathrm{})\frac{1}{\mathrm{}^{\stackrel{~}{\nu }d}}\frac{\mathrm{}^2}{\mathrm{}^{d_{\mathrm{}}(\tau 2)1}}\frac{1}{\mathrm{}^{\stackrel{~}{\nu }d}}\mathrm{}^{d_{\mathrm{}}(\tau 2)1},\text{for }\mathrm{}1.$$
(6)   
Comparing this result with the one obtained from Eq. (1) in the limit $`r1`$, yields $`\stackrel{~}{\nu }g_1=d_{\mathrm{}}(\tau 2)1`$, i.e.

$$g_1=d_f+d_{\mathrm{min}}d,$$
(7)   
which predicts $`g_1=1.026\pm 0.004`$ for $`d=2`$ and $`g_1=0.898\pm 0.008`$ for $`d=3`$. These theoretical values for $`g_1`$ are in very good agreement with our numerical results (cf. Fig. 1 and Table I). Note that Eq. (7) yields by construction $`g_1=0`$ for $`dd_\mathrm{c}`$, as required.

The above argument can be applied straightforwardly to the backbone and the skeleton of the incipient cluster, where now analogous equations to Eq. (5) can be written for $`\mathrm{\Phi }_\mathrm{B}(r1|\mathrm{})`$ and $`\mathrm{\Phi }_\mathrm{S}(r1|\mathrm{})`$, with $`\mathrm{\Pi }(\mathrm{})`$ replaced by $`\mathrm{\Pi }_\mathrm{B}(\mathrm{})`$ and $`\mathrm{\Pi }_\mathrm{S}(\mathrm{})`$, respectively. In the case of the backbone, we argue that $`\mathrm{\Pi }_\mathrm{B}(\mathrm{})n(s)\mathrm{d}s/\mathrm{d}\mathrm{}`$, with $`n(s)s^\tau `$, and $`s\mathrm{}^d_{\mathrm{}}`$ as for the incipient cluster. Note the absence of the factor $`s`$ in the expression for $`\mathrm{\Pi }_\mathrm{B}(\mathrm{})`$, reflecting the fact that the backbone represents a subset of the incipient cluster having a vanishing measure when $`s\mathrm{}`$ . Since the same argument applies to the skeleton, we have that $`\mathrm{\Pi }_\mathrm{S}(\mathrm{})\mathrm{\Pi }_\mathrm{B}(\mathrm{})`$, yielding

$$\mathrm{\Phi }_\mathrm{S}(r1|\mathrm{})\mathrm{\Phi }_\mathrm{B}(r1|\mathrm{}),\text{for }\mathrm{}1,$$
(8)   
in agreement with the numerical results shown in Figs. 2 and 3. In terms of $`\mathrm{\Pi }_\mathrm{B}(\mathrm{})`$, $`\mathrm{\Phi }_\mathrm{B}(r|\mathrm{})`$ in the limit $`r1`$ is given by

$$\mathrm{\Phi }_\mathrm{B}(r1|\mathrm{})\frac{1}{\mathrm{}^{\stackrel{~}{\nu }d}}\frac{\mathrm{\Pi }_{\mathrm{B},\mathrm{MF}}(\mathrm{})}{\mathrm{\Pi }_\mathrm{B}(\mathrm{})},\text{for }\mathrm{}1,$$
(9)   
and with $`\mathrm{\Pi }_\mathrm{B}(\mathrm{})\mathrm{}^{d_{\mathrm{}}(\tau 1)1}`$

$$\mathrm{\Phi }_\mathrm{B}(r1|\mathrm{})\frac{1}{\mathrm{}^{\stackrel{~}{\nu }d}}\frac{\mathrm{}^4}{\mathrm{}^{d_{\mathrm{}}(\tau 1)1}}\frac{1}{\mathrm{}^{\stackrel{~}{\nu }d}}\mathrm{}^{d_{\mathrm{}}(\tau 1)3},\text{for }\mathrm{}1.$$
(10)   
Comparing this result with the scaling form for $`\mathrm{\Phi }_\mathrm{B}(r|\mathrm{})`$ given in Eq. (2) in the limit $`r1`$, yields $`\stackrel{~}{\nu }g_1^\mathrm{B}=d_{\mathrm{}}(\tau 1)3`$, i.e.

$$g_1^\mathrm{B}=3d_{\mathrm{min}}d,$$
(11)   
predicting $`g_1^\mathrm{B}=1.390\pm 0.004`$ in $`d=2`$ and $`g_1^\mathrm{B}=1.122\pm 0.004`$ in $`d=3`$, with $`g_1^\mathrm{S}=g_1^\mathrm{B}`$, in remarkable agreement with the numerical results (cf. Figs. 2 and 3, and Table I). Note also that from Eqs. (11) and (8) one obtains $`g_1^\mathrm{B}=g_1^\mathrm{S}=0`$ for $`dd_\mathrm{c}`$, as expected.

In summary, we derive the analytical expressions $`g_1=d_f+d_{\mathrm{min}}d`$ and $`g_1^\mathrm{B}=g_1^\mathrm{S}=3d_{\mathrm{min}}d`$ describing the scaling behavior of the structural distribution functions, $`\mathrm{\Phi }(r|\mathrm{})\mathrm{}^{\stackrel{~}{\nu }d}x^{g_1}`$, $`\mathrm{\Phi }_\mathrm{B}(r|\mathrm{})\mathrm{}^{\stackrel{~}{\nu }d}x^{g_1^\mathrm{B}}`$, and $`\mathrm{\Phi }_\mathrm{S}(r|\mathrm{})\mathrm{}^{\stackrel{~}{\nu }d}x^{g_1^\mathrm{S}}`$, of the incipient percolation cluster, its backbone and skeleton, respectively, at the critical concentration $`p_\mathrm{c}`$ in the limit $`xr/\mathrm{}^{\stackrel{~}{\nu }}1`$. Here, $`\stackrel{~}{\nu }1/d_{\mathrm{min}}`$, and $`d_f`$ and $`d_{\mathrm{min}}`$ are the fractal dimensions of the incipient percolation cluster and the shortest path, respectively. Note that from the above expressions for the exponents $`g_1`$, $`g_1^\mathrm{B}`$, and $`g_1^\mathrm{S}`$ follow that the corresponding distribution functions for $`\mathrm{}1`$, in the limit $`r1`$, scale as $`\mathrm{\Phi }(r1|\mathrm{})\mathrm{}^{(d_{\mathrm{}}+1)}`$ and $`\mathrm{\Phi }_\mathrm{B}(r1|\mathrm{})\mathrm{\Phi }_\mathrm{S}(r1|\mathrm{})\mathrm{}^3`$, the latter being independent of the lattice dimension $`d`$. We note that the result $`\mathrm{\Phi }(r1|\mathrm{})\mathrm{}^{(d_{\mathrm{}}+1)}`$ for $`\mathrm{}1`$, based on numerical simulations, was also suggested for two other variants of percolation, invasion percolation with as well as without trapping , and seems therefore to be more general.

We acknowledge useful discussions with I. Webman, J. Dräger and A. Ordemann. This work has been supported by the Minerva Center for the Physics of Mesoscopics, Fractals and Neural Network; the German-Israeli Foundation; the Alexander von Humboldt Foundation and the Deutsche Forschungsgemeinschaft.