Chaotic Percolation

“When a structure changes from a collection of many disconnected parts into basically one big conglomerate, we say that percolation occurs” (Pg 463, Fractals and Chaos).

Introduction

Percolation is the study of lattices in dimensions of 2 or higher with regards to the pathways through such lattices. Take the example of a sponge that is divided up onto a square shaped grid. We can refer to such a grid as a lattice. For this example, consider any 2-dimensional cross section of this grid. If this lattice is divided up in an equal manner, then the study of different values for the probability of any location on this lattice being an open space will tell us what the largest percentage of open space in the sponge can be before the sponge stops holding water. The exact probability value at which the sponge under goes a phase transition from being able to hold water to being unable to hold water is called the threshold probability value p_c. The closer the probability p gets to p_c, the more liquid the sponge can hold, however, crossing the threshold will mean that chances are greater that the sponge can hold an infinite amount (as water flows straight through the sponge without being captured at all). When water can flow from one end of the sponge, right through and out another side, we say that percolation has occurred. Looking at figure 1, we can see that a group or cluster of sites that together give a path through the lattice is called a spanning cluster, and a group that does not is called a non-spanning cluster.

Figure 1

When studying percolation, three different aspects are (especially) of special mathematical interest to us:

1. The Maximal Cluster Size of a lattice of size L, M(L),
2. The Percolation Threshold P_c,
3. The Incipient Percolation Cluster.

The use of studying percolation is significant because it is widely applied in the modeling of physical computer networks, natural phenomena such as the formation of gold films on substrates, as well as on larger scales such as the study of galaxy and cluster formations in astrophysics. For the modeling of computer networks, the study revolves around ensuring data can flow between two points. The lattice is a large set of network nodes, and the arcs between these nodes represent the physical network connections. Finding the percolation threshold in this case is analogous to determining the minimal number of network connections which need to be active at any moment to ensure two points remain connected. For these networks, empirically determined values of p_c is approximately 0.5.

Maximal Cluster Size

When discussing percolation, it is usually the flow of one medium through another which interests us. Consider the flow of water through a rock that has been cut cleanly in two and had the resulting smooth surface mapped to a grid. Then let p denote the probability that any site on this grid is an open space. The maximal cluster size would then be the total area of the largest “hole” on this grid. Consider a grid or lattice of width L. If we let M(L) denote the size of the maximal cluster, and let P_L(p) be the probability that any particular lattice site is a member of the maximal cluster then, through empirical study several interesting results can be found.

The values of P_L(p) for any particular lattice is given by the relation , which represents the relative size of the maximal cluster to the entire lattice. The general value of P_L(p) can be approximated by taking the average value of this relation over several randomly generated lattices with the same values of p and L. Interestingly, the link between the lattice size and the value of P_L(p) has been found to disappear as the values of L increase. Ultimately, the value of P has been found to behave according to the following relation:

This means that the value of P ultimately depends just on the value of p, rather than on the value of L. This finding simplifies the analysis as it allows the study of the effect of L on percolation to be separated from the effects of values of p. Consider the example of a forest lattice, where p is the probability that any site on the lattice has a tree. Obviously, the forest would suffer the most damage if a random fire was set in a site which was part of the maximal cluster, so studying is important in determining if a fire, randomly set in the forest would occur in such a cluster of trees.

How about the effects that p has on the duration of the forest fire? Consider a simplistic model in which fires can only spread in 4 directions, can’t jump across open sites, and is not affected by wind/weather/etc… In this experiment we constructing a forest with density p, and then light all the trees on one side of this forest on fire. For each iteration of this model, we allow the trees that are on fire to burn out totally, and set all trees that adjacent to the originally burning trees on fire. If the site next to a previously burning tree is empty (ie, it has no tree) then the fire cannot spread to it. This setup studies a fire as it percolates through the forest lattice.

Figure 2 - Duration of the Forest for values of L = 50 (Blue), L = 150 (Red), and L = 300 (Black).

Notice from figure 2 that the plots of the different lattice sizes yield approximately the same shape, except for values of p around 0.60. This general result is exactly as we expected, since our values of L are increasing, if it follows the relation expressed above, then it should follow that the durations should approach the same approximate function. What about the area in which the results differ, the values of p ≈ 0.60? This value is known as the percolation threshold p_c and will be discussed in more detail presently.

The Percolation Threshold

Looking at the number of steps which it take a forest to burn down, we can see that the duration peaks at p_c and actually decreases as p increases beyond p_c. Consider another aspect of the forest fire, namely the percentage of the forest burned down.

Figure 3 - Percentage of trees in forests with L = 50 (Blue), L = 150 (Red), and L = 300 (Black) which are consumed by the forest fires.

From figure 3 we can see that as we increase the values of p, the percentage of the trees burned down increases steadily until it approaches p_c, at which point it sharply increases and quickly approaches 100% in an asymptotic manner. This sharp increase marks the phase transition in the lattice. The value at which this transition occurs is known as the percolation threshold, and we have been denoting its value by p_c in this discussion. For values of p > p_c, and values of p close to p_c, the probability is given by the power law:

, where

Notice that the percentage of trees burned down is the same as the probability that any tree picked at random is burned down. Relating this back to our previous discussion of the maximal cluster size, notice that for larger lattice sizes, that the probability that a tree is burned down shares a direct correlation with the probability that the tree is a member of the maximal cluster.

Getting back to the duration of the forest fire, we can explain the decrease after the peak as due to the fact that as the probability increases, the density becomes so high that the lattice becomes one big cluster and the fire no longer has to “follow paths” of tree around the lattice, but can just expand outwards as there are few open spaces to block its path. Notice however that the peak appears to become more pronounced as the Lattice size actually increases.

The Incipient Percolation Cluster

Notice the following regarding the observations that have been made regarding the size of the maximal cluster: As we values of p increases, the rate at which the duration of the forest fire increases sharply increases around the critical value p_c. Furthermore, when comparing the values for L = 50, 150 and 300, we notice that the increase is more pronounced for larger values of L. This feature, the sharp increase in slope as p approaches pc and progressive leveling off as the values of p move away from pc, is known as phase transition. Phase transition occurs in other branches of sciences as well, most prominently in physics when studying the transition of elements such as water as they move from a liquid state to a gaseous state.

For values of p > p_c, the probability > 0 implies that the proportion of trees burnt down grows asymptotically and this implies that the cluster size scales directly with regards to L².

On the other hand, for p ≤ p_c we may hypothesize that a power law holds so that the size is proportional to L^D with D < 2, which would indicate a fractal structure of the maximal cluster. However, it has been found that this result actually only holds true for one special value of p, which occurs exactly at the percolation threshold p = p_c. The maximal cluster of lattices formed with values of p = p_c are commonly denoted as the incipient percolation cluster, and has a fractal dimension that has been empirically measured to be D ≈ 1.89. Recall that we previously stated that for values of p greater than or near p_c that the cluster size scales with regards to the power law, for values of p less than p_c, it has been found that the maximal cluster size scales only as log(L).

Other Lattice Configurations

The discussion thus far has been limited to a single 2-dimensional lattice with a maximum of 4 possible arcs per site. Consider the differences that varying the number of arcs per site has on our values of p_c, D and . By increasing the maximum number of arcs per site from 4 to 8, we can analyze the critical values of an octagonal lattice. Figures 4 and 5 show the results from such an experiment.

Figure 4 - Duration of forest fires on octal lattices with L = 50 (Blue), and L = 150 (Red).

As we can see, the forest fires seem to last on average the longest around p = 0.5. Looking at figure 5, which gives the proportion of forest which was burned down, we can see that the phase transition occurs around p = 0.45. To narrow the value of p_c down even closer, we would have to repeat this experiment with higher degrees of resolution. Unfortunately, these empirical measurements are the only means of determining the percolation threshold values, and fractal dimensions of the incipient percolation clusters. Finding an analytical method of determining these numbers is still one of the open problems in percolation theory. Getting back to the data presented in figures 4 and 5, we could postulate that the percolation threshold varies inversely with regards to the number of connections per site (since for 8 connections, p_c appears to lie in the 0.45 – 0.5 range and p_c ≈ 0.5928 for 4 connections), but that actually isn’t the case. Numerical estimates currently place the percolation threshold p_c for 3 connections per site to be approximately p_c ≈ 0.5. Interestingly, although the percolation threshold varies depending on the number of connections per site, very little variation has been found in the fractal dimension D of the incipient percolation cluster. This values has been measured as D ≈ 1.896 for triangular lattices, where as the square lattices have D ≈ 1.89. It has been conjectured that this D ≈ 1.896 is the correct dimension of the incipient percolation cluster in all two-dimensional lattices.

Figure 5 - Percentage of Forest Lost on an octal lattice with L = 50 (Blue), and L = 150 (Red).

Raw Data

Duration

L = 50
		Run #
		1	2	3	4	5	Avg
Density	0.1	2	2	2	4	3	2.6
	0.2	2	4	4	4	4	3.6
	0.3	6	6	6	4	8	6
	0.4	17	15	10	17	12	14.2
	0.5	17	16	27	16	40	23.2
	0.51	42	14	36	46	17	31
	0.52	17	17	45	26	39	28.8
	0.53	45	53	39	62	28	45.4
	0.54	45	16	56	14	53	36.8
	0.55	30	62	39	90	59	56
	0.56	16	63	60	40	27	41.2
	0.57	87	99	110	20	96	82.4
	0.58	78	47	12	114	40	58.2
	0.59	76	75	112	118	64	89
	0.6	89	129	101	76	106	100.2
	0.61	103	108	191	121	161	136.8
	0.62	109	81	98	106	145	107.8
	0.63	93	98	85	109	136	104.2
	0.64	84	111	88	95	83	92.2
	0.65	83	73	83	96	77	82.4
	0.66	38	94	102	91	83	81.6
	0.67	96	100	92	71	79	87.6
	0.68	73	101	92	79	81	85.2
	0.69	77	81	79	73	71	76.2
	0.7	77	75	73	81	84	78
	0.8	65	69	63	69	67	66.6
	0.9	58	59	57	57	56	57.4
L = 150
		Run #
		1	2	3	4	5	Avg
Density	0.1	4	4	2	3	3	3.2
	0.2	5	4	5	5	6	5
	0.3	6	10	6	12	8	8.4
	0.4	8	17	16	13	14	13.6
	0.5	19	47	27	33	25	30.2
	0.51	25	75	21	35	27	36.6
	0.52	28	48	71	62	36	49
	0.53	51	48	15	60	29	40.6
	0.54	90	83	50	40	54	63.4
	0.55	86	73	70	76	55	72
	0.56	91	69	42	294	173	133.8
	0.57	117	119	321	192	228	195.4
	0.58	193	79	125	304	142	168.6
	0.59	370	382	389	510	315	393.2
	0.6	379	383	449	363	169	348.6
	0.61	327	346	403	373	374	364.6
	0.62	301	494	379	289	317	356
	0.63	301	253	277	306	263	280
	0.64	261	245	288	262	282	267.6
	0.65	251	230	242	284	247	250.8
	0.66	233	243	256	238	224	238.8
	0.67	228	222	218	222	232	224.4
	0.68	223	212	229	212	235	222.2
	0.69	240	241	214	218	203	223.2
	0.7	233	206	220	217	211	217.4
	0.8	182	182	178	181	180	180.6
	0.9	166	166	166	165	167	166
L = 300
		Run #
		1	2	3	4	5	Avg
Density	0.1	3	3	5	3	4	3.6
	0.2	5	5	5	5	11	6.2
	0.3	11	11	7	11	9	9.8
	0.4	13	15	19	18	17	16.4
	0.5	58	54	43	27	64	49.2
	0.51	33	47	49	42	46	43.4
	0.52	54	38	57	48	34	46.2
	0.53	61	33	104	44	85	65.4
	0.54	178	133	107	127	41	117.2
	0.55	73	141	103	131	91	107.8
	0.56	203	78	147	67	224	143.8
	0.57	332	286	140	192	145	219
	0.58	469	187	244	714	122	347.2
	0.59	354	431	488	433	206	382.4
	0.6	896	713	196	425	599	565.8
	0.61	574	640	535	960	650	671.8
	0.62	613	544	567	560	627	582.2
	0.63	551	519	499	471	554	518.8
	0.64	494	507	521	506	540	513.6
	0.65	454	475	463	490	482	472.8
	0.66	448	465	443	460	443	451.8
	0.67	468	445	485	457	435	458
	0.68	440	462	416	428	427	434.6
	0.69	426	425	422	420	413	421.2
	0.7	400	412	405	406	412	407
	0.8	353	355	355	353	354	354
	0.9	327	326	326	326	326	326.2

% Burned Down

L = 50
		Run #
		1	2	3	4	5	Avg
Density	0.1	0.00776	0.01627	0.02917	0.03788	0.00794	0.019804
	0.2	0.01578	0.02967	0.03313	0.02532	0.04033	0.028846
	0.3	0.02711	0.03334	0.03458	0.0315	0.04012	0.03333
	0.4	0.06113	0.08232	0.05123	0.07633	0.05906	0.066014
	0.5	0.14735	0.10143	0.13245	0.04934	0.15434	0.116982
	0.51	0.22892	0.09588	0.19501	0.17508	0.10556	0.16009
	0.52	0.13377	0.07853	0.23593	0.15257	0.20708	0.161576
	0.53	0.21072	0.19911	0.25589	0.3029	0.09207	0.212138
	0.54	0.19971	0.08213	0.26627	0.1011	0.41804	0.21345
	0.55	0.12053	0.22165	0.25236	0.48114	0.321	0.279336
	0.56	0.08006	0.30966	0.34678	0.28491	0.20145	0.244572
	0.57	0.61185	0.65784	0.73594	0.12235	0.67742	0.56108
	0.58	0.4778	0.29899	0.1015	0.82015	0.22534	0.384756
	0.59	0.7644	0.39511	0.79891	0.52647	0.4617	0.589318
	0.6	0.69073	0.77017	0.87216	0.48377	0.82529	0.728424
	0.61	0.66887	0.71318	0.823	0.73987	0.7803	0.745044
	0.62	0.88278	0.86638	0.81014	0.87637	0.91715	0.870564
	0.63	0.91793	0.88723	0.86136	0.87101	0.86611	0.880728
	0.64	0.9274	0.95112	0.9131	0.9102	0.92191	0.924746
	0.65	0.95887	0.86461	0.61095	0.92983	0.98052	0.868956
	0.66	0.29945	0.9509	0.93411	0.94715	0.83794	0.79391
	0.67	0.96716	0.9463	0.98172	0.93487	0.95458	0.956926
	0.68	0.94753	0.93104	0.94345	0.97254	0.98014	0.95494
	0.69	0.98154	0.98332	0.97769	0.97189	0.96851	0.97659
	0.7	0.98486	0.97292	0.98669	0.97862	0.94656	0.97393
	0.8	0.99755	0.99696	0.99704	0.99849	0.99605	0.997218
	0.9	1	1	1	1	1	1
L = 150
		Run #
		1	2	3	4	5	Avg
Density	0.1	0.00371	0.00668	0.00742	0.00829	0.00902	0.007024
	0.2	0.01003	0.00739	0.00759	0.00819	0.01262	0.009164
	0.3	0.01188	0.0128	0.00908	0.01721	0.01513	0.01322
	0.4	0.01397	0.02198	0.01424	0.02065	0.01596	0.01736
	0.5	0.02683	0.06179	0.02621	0.03399	0.03385	0.036534
	0.51	0.03354	0.07169	0.02717	0.03306	0.03574	0.04024
	0.52	0.0472	0.06516	0.05418	0.05795	0.05363	0.055624
	0.53	0.06511	0.05654	0.02458	0.04305	0.04088	0.046032
	0.54	0.07242	0.08974	0.06174	0.04272	0.05447	0.064218
	0.55	0.08303	0.05938	0.07078	0.11179	0.04015	0.073026
	0.56	0.13449	0.11596	0.08674	0.28846	0.15674	0.156478
	0.57	0.15562	0.1352	0.36528	0.18372	0.27238	0.22244
	0.58	0.16704	0.11313	0.13408	0.50659	0.2225	0.228668
	0.59	0.57266	0.34496	0.68319	0.61563	0.37782	0.518852
	0.6	0.61667	0.78682	0.72487	0.51443	0.40454	0.609466
	0.61	0.68196	0.69082	0.81308	0.77503	0.86226	0.76463
	0.62	0.88111	0.88687	0.80012	0.87858	0.86929	0.863194
	0.63	0.88424	0.84573	0.90431	0.89154	0.90361	0.885886
	0.64	0.87945	0.91085	0.92782	0.92715	0.9233	0.913714
	0.65	0.95026	0.93551	0.93771	0.95078	0.93854	0.94256
	0.66	0.95978	0.95874	0.95604	0.93993	0.9594	0.954778
	0.67	0.96905	0.96577	0.96795	0.96692	0.95401	0.96474
	0.68	0.96897	0.95059	0.97115	0.96572	0.96619	0.964524
	0.69	0.96087	0.97929	0.9765	0.97054	0.98177	0.973794
	0.7	0.98212	0.97518	0.97906	0.98281	0.98291	0.980416
	0.8	0.9985	0.99845	0.99879	0.99823	0.99717	0.998228
	0.9	0.99996	0.99991	0.99986	0.99976	0.99981	0.99986
L = 300
		Run #
		1	2	3	4	5	Avg
Density	0.1	0.00356	0.00415	0.00334	0.00291	0.00383	0.003558
	0.2	0.00525	0.00473	0.00389	0.00478	0.00522	0.004774
	0.3	0.0068	0.00604	0.00558	0.00681	0.00527	0.0061
	0.4	0.00759	0.00883	0.00884	0.01138	0.00892	0.009112
	0.5	0.02608	0.01995	0.02077	0.01482	0.02326	0.020976
	0.51	0.0193	0.01529	0.02253	0.02112	0.01795	0.019238
	0.52	0.02975	0.02192	0.02518	0.02266	0.01757	0.023416
	0.53	0.02953	0.02153	0.03539	0.02637	0.04526	0.031616
	0.54	0.0713	0.06076	0.06334	0.04319	0.02262	0.052242
	0.55	0.04118	0.05082	0.03758	0.04308	0.05209	0.04495
	0.56	0.12327	0.04587	0.07535	0.04127	0.0763	0.072412
	0.57	0.17885	0.16827	0.10076	0.11323	0.07609	0.12744
	0.58	0.27091	0.11674	0.13586	0.36044	0.08518	0.193826
	0.59	0.23393	0.33414	0.29204	0.27003	0.10183	0.246394
	0.6	0.77743	0.75051	0.1876	0.37462	0.65826	0.549684
	0.61	0.74853	0.84935	0.68922	0.78292	0.83886	0.781776
	0.62	0.85742	0.86535	0.85407	0.87384	0.88281	0.866698
	0.63	0.90888	0.91269	0.8929	0.9086	0.9233	0.909274
	0.64	0.94073	0.93298	0.93127	0.92576	0.93851	0.93385
	0.65	0.9384	0.95572	0.944	0.93907	0.94757	0.944952
	0.66	0.96137	0.96005	0.95786	0.94532	0.95695	0.95631
	0.67	0.96176	0.96685	0.96433	0.96681	0.96286	0.964522
	0.68	0.97129	0.96976	0.97264	0.97122	0.97289	0.97156
	0.69	0.97559	0.9785	0.97426	0.97775	0.97463	0.976146
	0.7	0.98531	0.98314	0.98309	0.98091	0.98305	0.9831
	0.8	0.99782	0.99781	0.99738	0.99739	0.99776	0.997632
	0.9	0.99991	0.99987	0.99977	0.99987	0.99989	0.999862

Octagonal Lattice Data

Duration
L=50		Run #
		1	2	3	4	5	Avg
Density	0.1	4	3	3	5	3	3.6
	0.2	7	6	4	6	5	5.6
	0.3	10	19	10	12	17	13.6
	0.4	38	70	54	46	79	57.4
	0.45	63	83	66	32	58	60.4
	0.5	62	59	65	60	56	60.4
	0.55	54	58	58	52	53	55
	0.6	56	57	58	53	53	55.4
	0.7	51	53	52	52	51	51.8
	0.8	52	51	51	51	51	51.2
	0.9	51	51	51	51	51	51
L=150		Run #
		1	2	3	4	5	Avg
Density	0.1	7	8	4	6	4	5.8
	0.2	7	11	10	9	10	9.4
	0.3	17	16	13	19	33	19.6
	0.4	187	169	118	298	46	163.6
	0.45	183	183	207	191	191	191
	0.5	177	167	159	169	165	167.4
	0.55	159	154	155	158	158	156.8
	0.6	153	153	156	154	155	154.2
	0.7	153	154	153	154	153	153.4
	0.8	151	152	153	152	152	152
	0.9	151	152	151	151	151	151.2
% Burned
L=50		Run #
		1	2	3	4	5	Avg
Density	0.1	0.04815	0.02963	0.03175	0.04833	0.02335	0.036242
	0.2	0.0519	0.04116	0.03013	0.05209	0.03823	0.042702
	0.3	0.06787	0.12825	0.05443	0.10759	0.1827	0.108168
	0.4	0.27868	0.58007	0.3521	0.43601	0.76414	0.4822
	0.45	0.9193	0.88801	0.9619	0.38372	0.48307	0.7272
	0.5	0.9828	0.96489	0.97755	0.96741	0.9812	0.97477
	0.55	0.99349	0.98217	0.96738	0.97747	0.98834	0.98177
	0.6	0.99935	0.99935	0.9966	0.99797	0.99605	0.997864
	0.7	1	1	0.99885	0.99885	1	0.99954
	0.8	1	1	1	1	1	1
	0.9	1	1	1	1	1	1
l=150		Run #
		1	2	3	4	5	Avg
Density	0.1	0.00962	0.01686	0.01084	0.01082	0.00823	0.011274
	0.2	0.01296	0.01898	0.01894	0.01467	0.01542	0.016194
	0.3	0.02951	0.02613	0.02671	0.03714	0.03956	0.03181
	0.4	0.28577	0.36252	0.19815	0.54491	0.08169	0.294608
	0.45	0.91954	0.9368	0.92615	0.92373	0.93572	0.928388
	0.5	0.97916	0.98703	0.98601	0.98658	0.97385	0.982526
	0.55	0.99539	0.99524	0.99435	0.99275	0.99174	0.993894
	0.6	0.99786	0.99762	0.99816	0.9974	0.99838	0.997884
	0.7	1	0.99981	0.99988	0.99988	1	0.999914
	0.8	0.99995	1	1	1	0.99989	0.999968
	0.9	1	1	1	1	1	1

References

Grimmett, Geoffrey. Percolation, Second Edition. Springer, New York:1999.

Peitgen, Heinz-Otto et al. Chaos and Fractals: New Frontiers of Science. Springer-Verlag, New York:1992.

Wu, Junqiao. Introduction to Percolation Theory. http://socrates.berkeley.edu/~jqwu/paper1/node1.html