A Study on Numerical Calculation Method of Small Cluster Density in Percolation Model

Show more

1. Introduction

There are a large number of random small pathways in porous media. Whether the fluid can percolate the media or not depends on the state of these small pathways. Percolation model, first introduced by Simon Broadbent and John Hammersley in 1957, is a mathematics model to stimulate whether fluids can penetrate porous media, such as lava [1]. There is a large cluster in the system, and the cluster can get through the two boundary of these grid points. We call this flow state. Percolation model is a probabilistic model of critical phenomena. Because of its research methods and results, the percolation model is easy to be generalized to other random media and has a lot of public problems which are easy to describe but difficult to deal with.

There is a long history of the study about calculating the cluster density, such as C M Newman and L S Schulman [2], C Hongler and S Smirnov [3], in this article, we also study about the calculation of cluster density, but we only focus on the examples of the calculation of small clusters and compare the exact and numerical methods of the calculation. We only consider about the small clusters with area 1, 2, and 3.

Before the method of calculating the density, we introduce the construction of the percolation model.

2. Ease of Use

The space structure of the percolation model is a regular grid structure, and the percolation model of the two dimensional square lattice is discussed in this paper [4].

There are two kinds of percolation model, which are the bond percolation model and the site percolation model. The bond percolation model is concerned with the edge of the grid, called the bond. Each bond on the grid may be open with probability p, or closed with probability 1 − p, and they are assumed to be independent. The open bond is represented in black, while closed bond is represented in white. Figure 1 is an example of P = 0.25, Figure 2 is an example of P = 0.75. Obviously, the greater the value of P, the greater the density of the bond. The black bonds are connected with each other and form a cluster. There exists a maximal cluster which is connected with the left and right boundary of the medium, which forms the penetration of the medium. This model is also known as bond percolation.

Another way of percolation model is site percolation, which is concerned with whether the grid (called site) is occupied, rather than the edge of the opening or not. Assuming that each lattice point is occupied independently with probability P, the probability 1 − P is not occupied [5]. If the occupied grid points are adjacent to each other, then they form a cluster. The adjacent judgment rule is consistent with the cellular automaton, which uses the von Neumann (Neumann Von.) model, which is the upper, lower, left and right adjacent four cells of a cell [6]. In Figure 3, a total of 5 clusters, from top to bottom, from left to right, the 5 cluster area were 2, 7, 1, 4, 1 units. The area of the largest clusters was 7.

In this paper, we use a stochastic method to generate an example of site percolation.

Figure 1.Bond percolation, P = 0.25.

Figure 2. Bond percolation, P = 0.75.

Figure 3. Example of site percolation.

3. Prepare Your Paper before Styling

In the following, the small cluster density in the percolation model is calculated by the exact method and the numerical method. Here only consider the area of 1, 2, 3 of small clusters.

3.1. Cluster Number Density-Excat Method

According to paper [5], the exact expression for the number densities of small clusters in two dimensional percolation model is Formula (1).

(1)

In Formula (1), g(s, t) represents the number of all clusters with size s and perimeter t. Even though there is no special relationship between the cluster size s and its perimeter t, as it is not on the Bethe lattice, we can enumerate g(s, t) by hand for small cluster sizes. Through this method, we get the following formula.

(2)

These are the exact expression of the number density of clusters up to size five. Table 1 lists all patterns for small clusters with the area four or smaller. Figure 4 shows three of them: S = 2, S = 3 & t = 7, S = 4 & t = 8. We found that there are three patterns when S = 4, t = 8.

Then we calculate the density of small clusters following Formula (2). The results are shown in Figure 5. The horizontal value is P and the vertical value is density. From Figure 5, we can get the conclusion that the density of all three kinds of small clusters reaches the highest value between P = 0.1 and 0.2.

3.2. Cluster Number Density-Numerical Method

Now we will use the numerical method to calculate the density of clusters. Taking S = 1 as an example, the calculation method is as follows: generate the percolation model taking different P (conduction ratio) and different L (the length of the side), then calculate the number of S = 1 using the von Neumann (Neumann Von.) type neighbor, then get the density by using the number divided by the area. In the real calculation, we take combinations of P = 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, L = 50, 100, 200, 500, 2000 and calculate 20 times for each combination and get the average. Table 2 shows the data of one example.

From the data in Table 2, as L is increasing, the densities for each P are almost the same. We use the same method for S = 1, 2, 3.

4. Discussion

Now we list the results of the two methods in table 3. The numerical values are the ones we get when L = 2000.

Figure 4. Graphs of the three patterns.

Figure 5. Density of small clusters.

Table 1. Patterns and g(s, t) for small clusters, s ≤ 4.

Table 2. The density in models of different P and L (S = 1).

According to Table 3, the results of these two methods are close. Now we discuss the advantages and disadvantages of each method.

The advantage of exact method is that the calculation is really fast while the formulas are complex, especially when S gets larger. In fact, we now only have the foemula for clusters up to size 40. We cannot construct a theory of percolation based onclusters up to size s = 40-we must consider clusters of all sizes. Therefore, we must recognize that we cannot work out the exact solutions of the cluster number density for all cluster sizes. Since exact solutions are not available for large cluster sizes, we resort to the numerical approach to obtain the general form of the cluster number density n(s,p) for any s and p.

The disadvantage of numerical method is that it is relatively slow, especially when L gets larger. Figure 6 show the relationship between the cluster size and the time taken. The horizontal value is L = 500, 1000, 2000, 5000. The vertical value shows the time in seconds. The time is measured for calculating 20 times. Our test environment is Intel Core i5CPU @1.70 Ghz 2.40 Ghz, 8 GRAM, Windows 7 64bits, python3.5.

In Figure 6, the abscissa said the side length of the square model, the vertical axis represents the calculation time. From Figure 6, the time taken is a most of square (2.0151) relationship of L. The correlation coefficient is 0.99. It takes about 543 seconds to calculate the cluster number density (S = 1) when L = 5000. However, the programs are the same, we barely changed the programs even if S gets large, so it is convenient.

5. Conclusions

Firstly, this paper introduces the percolation model, the bond percolation model and the site percolation model, and introduces how to construct the percolation model.

Figure 6. The relationship between the model size and the time taken.

Table 3. The comparison of the results of exact and numerical method (S = 1, 2, 3).

On this basis, the density of small clusters (2, 3, 1) in the percolation model are calculated respectively by using the exact method and numerical method, and the results of the two methods are very close.

We find that the cluster density of all three kinds of small clusters reaches the highest value when the occupation probability is between 0.1 and 0.2.

Finally, we discuss the advantages and disadvantages of the two methods, and the advantages of the exact method is that the calculation speed is fast, but the disadvantage is that the formula of the input is very cumbersome, especially when the S is very large.

The disadvantage of the numerical method is that the computation speed is slow, especially when the L is large. However, the numerical method has the advantage of code general, when S is very large, we almost do not have to rewrite the code, it is very convenient. It is very difficult to get the analytical formula for the exact method, such as S = 50, which is very difficult to get the analytical formula for the exact method.

References

[1] Broadbent, S. and Hammersley, J. (1957) Percolation Processes I. Crystals and Mazes. Proceedings of the Cambridge Philosophical Society, 53, 629-641.

[2] Newman, C.M. and Schulmang, L.S. (1981) Number and Density of Percolating Clusters. J. Phys. A: Math. Gen., 14, 1735-1743.

[3] Hongler, C. and Smirnov, S. (2009) Critical Percolation: The Expected Number of Clusters in a Rectangle. Probability Theory & Related Fields, 151, 735-756.

[4] Xiao, L.Q. and Zhou, S.P. (2014) Stochastic Simulation Method and Its Application. Peking University Press, 246-249.

[5] Christensen, K. and Moloney, N.R. (2005) Complexity and Criticality. 35-36.

[6] Burks, A.W. Essay on Cellular Automata. University of Illinois Press, Urbana.
Yoshio Yuge, H. (1978) Renormalization-Group Approach for Critical Percolation Behavior in Two Dimesions. Phys Rev (B), 18, 1514-1517.