The isomorphic version of Brualdi's and Sanderson's nestedness (Q1657023)

Summary: The discrepancy BR for an \(m \times n\) \(0, 1\)-matrix from \textit{R. A. Brualdi} and \textit{J. G. Sanderson} [``Nested species subsets, gaps, and discrepancy'', Oecologia 119, 256--264 (1998; \url{doi:10.1007/s004420050784})] is defined as the minimum number of 1 s that need to be shifted in each row to the left to achieve its Ferrers matrix, i.e., each row consists of consecutive 1 s followed by consecutive 0 s. For ecological bipartite networks, BR describes a nested set of relationships. Since two different labelled networks can be isomorphic, but possess different discrepancies due to different adjacency matrices, we define a metric determining the minimum discrepancy in an isomorphic class. We give a reduction to \(k \leq n\) minimum weighted perfect matching problems. We show on 289 ecological matrices (given as a benchmark by \textit{W. Atmar} and \textit{B. D. Patterson} [``The nestedness temperature calculator: a visual basic program, Including 294 presence-absence matrices'', Chicago, IL: AICS Research, Inc. (1995)]) that classical discrepancy can underestimate the nestedness by up to 30\%.