Minimal spanning trees at the percolation threshold: A numerical calculation

The fractal dimension of minimal spanning trees on percolation clusters is estimated for dimensions $d$ up to $d=5$. A robust analysis technique is developed for correlated data, as seen in such trees. This should be a robust method suitable for analyzing a wide array of randomly generated fractal structures. The trees analyzed using these techniques are built using a combination of Prim's and Kruskal's algorithms for finding minimal spanning trees. This combination reduces memory usage and allows for simulation of larger systems than would otherwise be possible. The path length fractal dimension $d_s$ of MSTs on critical percolation clusters is found to be compatible with the predictions of the perturbation expansion developed by T. S. Jackson and N. Read [Phys. Rev. E 81, 021131 (2010)].

Figure 1

A sample iteration of Kruskal's algorithm on an eight by eight periodic square lattice ($d=2$). At a given step, the state is a forest of trees, which includes isolated sites (open circles) and larger trees (connected solid circles). During each step of the algorithm, the edge with the lowest weight is selected from the remaining unselected edges. For example, if edge $A$ is selected, the trees containing either endpoint of edge $A$ are merged into a single tree. If edge $B$ is selected, its addition would form a nonwrapping loop (forbidden cycle), so edge $B$ is not added to any tree and is removed from future consideration. If edge $C$ is selected, its addition would form a wrapping loop (allowed cycle), so the algorithm is terminated. The tree containing the endpoints of edge $C$ is then the Kruskal's MTISC, $T_K$.

Figure 2

A sample iteration of Prim's algorithm on an eight by eight periodic square lattice ($d=2$). The tree is represented by connected solid circles and lines, while unoccupied sites are shown as open circles. The diamond-shaped vertex at the bottom left of the lattice is the initial seed site $v_0$. During each step of the algorithm, the edge adjacent to the current Prim's tree with the lowest weight is selected. If edge $A$ is selected, it is added to the Prim's tree, along with the endpoint of $A$ that is not already in the Prim's tree. If edge $B$ is selected, its addition to the Prim's tree would form a nonwrapping loop (forbidden cycle), so edge $B$ is not added to the tree and is removed from future consideration. If edge $C$ has the lowest weight and is selected, its addition would cause the Prim's tree to wrap around the periodic lattice (adding an allowed cycle), so the algorithm is terminated, leaving the current Prim's tree as the Prim's MTISC, $T_P$.

Figure 3

Illustration of the two-step method. This method grows a candidate MTISC using the Prim's method and then trims the tree using Kruskal's algorithm. (a) depicts $T_P$ (plus the final wrapping edge) which is given as input to Kruskal's algorithm. During construction of this tree, only edges adjacent to the tree are tested. The potential connectivity of the unoccupied sites is explicitly shown using open circles and thin lines, and for reference the Prim's seed site $v_0$ at the bottom left of the lattice is represented by a diamond. (b) shows the state of the graph after running 23 steps of Kruskal's algorithm on $T_P$, with trees being represented by connected solid circles. If edge $B$ is selected before edge $A$, i.e., $w\left(B\right)<w\left(A\right)$, the Prim's seed site $v_0$ will not be part of $T_K$, and the disconnected portion of the graph containing the Prim's seed site $v_0$ will be trimmed off.

Figure 4

Scaling collapse for $d=2$ with $d_s=1.215$, which appears to be moderately close to the true value of $d_s$ judging by eye from the goodness of the collapse. Note that error bars are smaller than the symbol size for all points except the right-most point.

Figure 5

A sample collapse for two systems of size $L=32$ and $L=64$ in dimension $d=2$. (a) Shows the comparison of the two systems at interpolated points ${\omega }_k^0$ for a value of $d_s=1.2$. Comparing the value of ${\rho }_k(L_1=32)$ indicated by the blue (dark gray) triangles and ${\rho }_k(L_2=64)$ indicated by the green (light gray) circles at each of these points allows for the calculation of ${\chi }^2(d_s;L_1,L_2)$. (b) Shows ${\chi }^2$ compared with an expected estimate ${\chi }_p^2$ as a function of the fitting parameter $d_s$ for the same pair of systems. Though we determine final error bars by resampling, the ${\chi }^2$ model is shown for comparison.

Figure 6

Variations from the mean for a typical batch $\alpha$ of data for a system of size $L=64$ in dimension $d=2$. The difference between the mean Euclidean distances ${\delta r}_{\alpha }\left(s\right)=r_{\alpha }\left(s\right)-\overline{r\left(s\right)}$ is plotted vs. path length $s$.

Figure 7

Correlation matrix $c_{s,t}$ averaged over all data for systems of size $L=64$ in dimension $d=2$. Selected contours are shown.

Figure 8

Scaled correlation length $\ell$ vs. $\omega$ in dimension $d=2$ with $d_s=1.215$ for systems $L=16,64,256,2048$ (red solid, green dashed, blue dotted, and magenta dash-dotted lines, respectively). In this case $\ell$ was measured assuming exponential decay $c_{s,t}=\exp \left(-\left|s-t\right|/{\ell }^{\prime }\right)$ and integrating $c_{s,t}$ to obtain the unscaled correlation length ${\ell }^{\prime }$, with the relation to the scaled correlation length $\ell$ being $\ell ={\ell }^{\prime }/L^{d_s}$.

Figure 9

Scaled correlation length $\ell$ vs. $\omega$ in dimension $d=4$ with $d_s=1.65$ for systems $L=16,32,64$ (red solid, green dashed, and blue dotted lines, respectively). In this case the unscaled correlation length ${\ell }^{\prime }$ was measured using the full width at half maximum (how many “steps” in $s$ away from the diagonal before $c_{s,t}$ falls to a value of $1/2$). To obtain the scaled correlation length $\ell$, we use the relation $\ell ={\ell }^{\prime }/L^{d_s}$.

Figure 10

An illustration of a linear least squares fitting method being used to extract the value of $d_s$ in the infinite system size limit in dimension $d=2$. The fit uses the form $d_s\left(L\right)=A{L}^{-\lambda }+d_s\left(\infty \right)$ where $\lambda$ is a correction to scaling exponent and $A$ and $d_s\left(\infty \right)$ are fitting parameters. Here $\lambda =0.5$, and $L=\sqrt{L_1{L}_2}$, where $L_1$ and $L_2$ are the two system sizes used to produce a given data point. The fit found gives $d_s\left(\infty \right)=1.216\left(1\right)$.

Figure 11

A plot comparing numerical results for $d_s$ using the two-step method (blue points) against predictions from the $O\left(\epsilon \right)$ perturbation expansion theorized by Jackson and Read (red dashed line). Also included is an example of a compatible $O\left({\epsilon }^2\right)$ fit (purple dotted line), $d_s=2-\frac{\epsilon }{7}+b{\epsilon }^2$, with a best fit value $b=-0.0133$.

Figure 12

Examining the effects of the lower and upper data cutoffs on a collapse of two systems of sizes $L=512$ and $L=1024$ in dimension $d=2$. (a) and (b) display ${\chi }_p^2/{\chi }^2$ and $d_s$ as functions of the lower (small $s$) data cutoff $s_l$, while (c) and (d) show ${\chi }_p^2/{\chi }^2$ and $d_s$ as functions of the upper (large $s$) data cutoff ${\omega }_u$ for $s_l=100$. Both ${\chi }_p^2$ and ${\chi }^2$ are measured at the value of $d_s$ for which ${\chi }^2$ is minimized.