A binary matrix is fully nested if its columns form a chain of subsets; that is, any two columns are ordered by the subset relation, where we view each column as a subset of the rows indicated by the 1-entries. A binary matrix is k-nested if its columns can be partitioned into k pairwise disjoint blocks, each of which is fully nested. Such nested patterns are encountered, for example, in presence/absence patterns of species in ecological data. We study the automated discovery of k-nestedness on synthetic data and real ecological data. First, we show that k-nestedness can be efficiently discovered in a noise-free setting using a polynomial-time algorithm. Second, we show that it is NP-hard to find a k-nested matrix that minimizes the Hamming distance to a given dataset. Thus, it is likely that in the presence of noise no efficient algorithm exists for discovering k-nestedness in the general case. Third, we develop and evaluate multiple heuristic algorithms for discovering k-nestedness on noisy synthetic data. The methods based on a combination of singular value decomposition and k-means++ give the best performance in terms of structure discovery and noise tolerance. Fourth, we develop an MDL-based model selection technique for assessing nestedness, and discover k-nested structure in (a) paleontological data, and (b) geographical occurrence data for mammal species in Europe.

A 0--1 matrix has a banded structure if both rows and columns can be permuted so that the non-zero entries exhibit a staircase pattern of overlapping rows. The concept of banded matrices has its origins in numerical analysis, where entries can be viewed as descriptions between the problem variables; the bandedness corresponds to variables that are coupled over short distances. Banded data occurs also in other applications, for example in the physical mapping problem of the human genome, in paleontological data, in network data and in the discovery of overlapping communities without cycles.