Faster calculation of the percolation correlation length on spatial networks

The divergence of the correlation length $\xi$ at criticality is an important phenomenon of percolation in two-dimensional systems. Substantial speed-ups to the calculation of the percolation threshold and component distribution have been achieved by utilizing disjoint sets, but existing algorithms of this sort cannot measure the correlation length. Here we utilize the parallel axis theorem to track the correlation length as nodes are added to the system, allowing us to utilize disjoint sets to measure $\xi$ for the entire percolation process with arbitrary precision in a single sweep. This algorithm enables direct measurement of the correlation length in lattices as well as spatial network topologies and provides an important tool for understanding critical phenomena in spatial systems.

Figure 1

Tracking inertia and radius of gyration as links are added. In the left panel, there are two clusters, with known inertia, and centers of mass marked with an “x”. In the right panel, a new link is added which joins the two clusters. Instead of calculating the inertia from scratch, it can be updated using the parallel axis theorem as shown. In this way, as links (or nodes) are added to the network we can continually track the inertia, the radius of gyration, and, by averaging the radius of gyration across clusters, the correlation length $\xi$.

Figure 2

Node renumbering in light of periodic boundary conditions. Here a $4\times 4$ lattice with periodic boundary conditions is shown, along with its replicas on all sides. The figure shows a system with cluster structure defined by the solid links, as the dashed links (a), (b), and (c) are added. Each node has two coordinates: the upper “lattice” coordinate which is based on the lattice location and not affected by the cluster structure, and a lower “relative” coordinate which is updated to maintain consistent distance measurements within clusters. Link (a) will require no renumbering because neither previous cluster (the single nodes) crosses the boundary. In this case, correction $\mathbf{C}=\left[\right(1,3)-(1,2\left)\right]-\left[\right(1,3)-(1,2\left)\right]=(0,0)$. Link (b) will cause the smaller cluster (in blue, on the left) to be renumbered to match the larger cluster (in green, on the right) which crosses a boundary. In this case the correction $\mathbf{C}=\left[\right(-2,3)-(2,2\left)\right]-\left[\right(2,3)-(2,2\left)\right]=-(4,0)$. For link (c) correction $\mathbf{C}=(-4,0)$, the same as for link (b), but because link (c) connects the cluster to itself, the renumbering is not possible, which means that now this cluster spans the system from top to bottom and, hence, must be excluded from the calculation of the correlation length.

Figure 3

The percolation correlation length $\xi$ as a function of $p_c-p$ below criticality ($p<p_c$). It is seen that both the burning and disjoint sets algorithms give similar results showing the expected scaling of $\xi \sim {(p_c-p)}^{-\nu }$ with $\nu =4/3$. The inset shows $\xi$ as function of $p$ above and below the scaling region. Simulations shown for $N={10}^6$ on a next-nearest lattice ($z=8$) averaged over 1000 realizations.

Figure 4

Running time as function of the resolution. The continuous lines represent the computational running time of the burning algorithm for a given system size, and the dashed lines represent the running time of our disjoint sets algorithm for the same system size. One can see that for resolution higher than 10, our disjoint sets algorithm is faster, and the running time remains constant while the burning algorithm running time increases polynomially.

Figure 5

Convolved results ${\xi }_p$ compared to raw results ${\xi }_n$. As expected by the theory, the slope of 4/3 is more closely matched by our numerical measurements when they are convolved with the binomial distribution. Shown here is an average of 100 runs for $L=1000$ and $z=4$, with sampling step size of 2.

Figure 6

Measurement of the correlation length in a spatial network with exponential link lengths. In contrast to previous optimizations, the algorithm presented here can efficiently measure the correlation length in networks with spatial disorder. The network model was introduced in Ref. [15] and further analyzed in Refs. [16, 17, 19].