Swap and fill algorithms in null model analysis: rethinking the knight's tour

Community assembly rules are often inferred from patterns in presence-absen ce matrices. A challenging problem in the analysis of presence-absence matr ices has been to devise a null model algorithm to produce random matrices w ith fixed row and column sums. Previous studies by Roberts and Stone [(1990 ) Oecologia 83:560-567] and Manly [(1995) Ecology 76:1109-1115] used a "Seq uential Swap" algorithm in which submatrices are repeatedly swapped to prod uce null matrices. Sanderson et al. [(1998) Oecologia 116:275-283] introduc ed a "Knight's Tour" algorithm that fills an empty matrix one cell at a tim e. In an analysis of the presence-absence matrix for birds of the Vanuatu i slands, Sanderson et al. obtained different results from Roberts and Stone and concluded that "results from previous studies are generally flawed". Ho wever, Sanderson et al. did not investigate the statistical properties of t heir algorithm. Using simple probability calculations, we demonstrate that their Knight's Tour is biased and does not sample all unique matrices with equal frequency. The bias in the Knight's Tour arises because the algorithm samples exhaustively at each step before retreating in sequence. We introd uce an unbiased Random Knight's Tour that tests only a small number of cell s and retreats by removing a filled cell from anywhere in the matrix. This algorithm appears to sample unique matrices with equal frequency. The Rando m Knight's Tour and Sequential Swap algorithms generate very similar result s for the large Vanuatu matrix, and for other presence-absence matrices we tested. As a further test of the Sequential Swap, we constructed a set of 1 00 random matrices derived from the Vanuatu matrix, analyzed them with the Sequential Swap, and found no evidence that the algorithm is prone to Type I errors (rejecting the null hypothesis too frequently). These results supp ort the original conclusions of Roberts and Stone and are consistent with G otelli's [(2000) Ecology 81:2606-2621] Type I and Type II error tests for t he Sequential Swap. In summary, Sanderson et al.'s Knight's Tourgenerates l arge variances and does not sample matrices equiprobably. In contrast, the Sequential Swap generates results that are very similar to those of an unbi ased Random Knight's Tour, and is not overly prone to Type I or Type II err ors. We suggest that the statistical properties of proposed null model algo rithms be examined carefully, and that their performance judged by comparis ons with artificial data sets of known structure. In this way, Type I and T ype II error frequencies can be quantified, and different algorithms and in dices can be compared meaningfully.