Discrepancy is a way to measure the nestedness of a matrix. In a comparative study, Ulrich & Gotelli (2007) showed discrepancy to outperform all other measures and hence recommend its use (together with a fixed-columns, fixed-rows null model, such as implemented in simulate.nullmodel
in vegan, see example).
This function follows the logic laid out by Brualdi & Sanderson (1999), although, admittedly, I find their mathematical description highly confusing. Another implementation is given by the function nesteddisc
in vegan. The reason to write a new function is simple: I wasn't aware of nesteddisc
! (I was sitting on a train and I wanted to use this measure later on, so I put it into a function consulting only the orignal paper. When looking for the swap algorithm to create null models, which I somehow knew to exist in vegan, I stumbled across nesteddisc
. If you are interested in the swap algorithm and come across this help page, let me re-direct you to oecosimu
in vegan.)
Now that this function exists, too, I found it to differ in output from nesteddisc
. Jari Oksanen was quick to point out, that our two implementations differ in the way they handle ties in column totals. This function is, I think, closer to the results given in Brualdi & Sanderson. Jari also went on to implement different strategies to deal with ties, so my guess is that his version may be (slightly) superior to this one. Having said that, values don't differ much between the two implementations.
So what does it do: The matrix is sorted by marginal totals, yielding a matrix A. Then, all 1s in A are “pushed” to the left to maximally compact the matrix, yielding P. Discrepancy is now simply the number of disagreements between A and P, divided by two (to correct for the fact that every “wrong” 1 will necessarily generate a “wrong” 0).