X
Home Math Sciences People pbalistr/knn

k-nearest neighbor percolation

This page is designed to give more information on the derivation of the results in [1]. In particular, the C source files for the programs used to obtain the results stated there. For notation and mathematical details, see [1].

Rigorous Bounds

Documentation is included with the source file. The test to perform and parameters used are #define'd in the first few lines. (All parameters are hard-coded in the source file.) The following parameters need to be set before compiling the code:

  • X = one of 'U', 'O', 'I', 'B', defining the type of percolation. Note that there is no 'S' option.
  • KMIN = minimum value of k.
  • KMAX = maximum value of k.
  • ACC = an accuracy parameter. Increase to make bounds tighter (but program slower).

The program calculates the bounds in Table 1 of the paper for a range of k values. The results (for suitable values of the parameters) should be exactly as given in the paper. Success (proof of percolation) is achieved if the bound given is at most (1 - 0.8639)/2 = 0.06805.

The running time of program is O(ACC^4) while the accuracy of the bound is O(ACC^{-2}).

C source   Output

High Confidence Results

Documentation is included with the source file. The test to perform and parameters used are #define'd in the first few lines. (All parameters are hard-coded in the source file.) The following parameters need to be set before compiling the code:

  • K = k is the number of nearest neighbors.
  • X = one of 'U', 'O', 'I', 'B', defining the type of percolation. Note that there is no 'S' option.
  • BND = either 'L' for the lower bound proof (showing percolation fails for this value of k), or 'U' for the upper bound proof (showing percolation succeeds for this value of k).
  • R = r is the radius of the central disk in Figure 2 of the paper.
  • S = s is the distance between the central disk and the boundary of the rectangle in Figure 2 of the paper.
  • ITER = the number of trials that will be performed.

Values of these parameters and the results obtained are given in [1]. The random number seed (SEED) can be changed to give independent tests, otherwise the results (for the same parameters) should be exactly as given in [1].

C source

Reference

[1] Paul Balister, Béla Bollobás. Percolation in the k-nearest neighbor graph. In Recent Results in Designs and Graphs: a Tribute to Lucia Gionfriddo, Quaderni di Matematica, Volume 28. Editors: Marco Buratti, Curt Lindner, Francesco Mazzocca, and Nicola Melone, (2013), 83–100.