The isomorphic version of Brualdi’s and Sanderson’s nestedness. (English) Zbl 1462.05212

Summary: The discrepancy BR for an \(m \times n\) \(0, 1\)-matrix from R. A. Brualdi and J. G. Sanderson [“Nested species subsets, gaps, and discrepancy”, Oecologia 119, 256–264 (1998; 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 W. Atmar and 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%.


05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05A05 Permutations, words, matrices
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
05E10 Combinatorial aspects of representation theory
15B34 Boolean and Hadamard matrices
Full Text: DOI arXiv


[1] Hultén, E.; ; Outline of the History of Arctic and Boreal Biota During the Quaternary Periods: Stockholm, Sweden 1937; .
[2] Ulrich, W.; Almeida-Neto, M.; Gotelli, N.J.; A consumer’s guide to nestedness analysis; Oikos: 2009; Volume 118 ,3-17.
[3] Bascompte, J.; Jordano, P.; Melián, C.J.; Olesen, J.M.; The nested assembly of plant-animal mutualistic networks; Proc. Natl. Acad. Sci. USA: 2003; Volume 100 ,9383-9387.
[4] Okuyama, T.; Holland, J.N.; Network structural properties mediate the stability of mutualistic communities; Ecol. Lett.: 2008; Volume 11 ,208-216.
[5] Bastolla, U.; Fortuna, M.A.; Pascual-Garcia, A.; Ferrera, A.; Luque, B.; Bascompte, J.; The architecture of mutualistic networks minimizes competition and increases biodiversity; Nature: 2009; Volume 458 ,1018-1020.
[6] Thébault, E.; Fontaine, C.; Stability of Ecological Communities and the Architecture of Mutualistic and Trophic Networks; Science: 2010; Volume 329 ,853-856.
[7] Sylvester, J.J.; Franklin, F.; A Constructive Theory of Partitions, Arranged in Three Acts, an Interact and an Exodion; Am. J. Math.: 1882; Volume 5 ,251-330. · JFM 15.0129.02
[8] Ryser, H.J.; Combinatorial Properties of Matrices of Zeros and Ones; Classic Papers in Combinatorics: Bosten, MA, USA 1987; ,269-275.
[9] Brualdi, R.A.; ; Combinatorial Matrix Classes: Cambridge, UK 2006; . · Zbl 1106.05001
[10] Mahadev, N.V.R.; Peled, U.N.; ; Threshold Graphs and Related Topics: Amsterdam, The Netherlands 1995; . · Zbl 0852.05001
[11] Brualdi, R.A.; Shen, J.; Discrepancy of matrices of zeros ond ones; Electron. J. Comb.: 1999; Volume 6 ,1-12. · Zbl 0918.05029
[12] Lovász, L.; Plummer, M.D.; ; Matching Theory: New York, NY, USA 2009; Volume Volume 367 .
[13] Gabow, H.; Implementation of Algorithms for Maximum Matching on Nonbipartite Graph; Ph.D. Thesis: Stanford, CA, USA 1974; .
[14] Yannakakis, M.; Computing the Minimum Fill-In is NP-Complete; SIAM J. Algebraic Discret. Methods: 1981; Volume 2 ,77-79. · Zbl 0496.68033
[15] Garey, M.R.; Johnson, D.S.; ; Computers and Intractability; A Guide to the Theory of NP-Completeness: New York, NY, USA 1990; . · Zbl 0411.68039
[16] Junttila, E.; Patterns in permuted binary matrices; Ph.D. Thesis: Helsinki, Finland 2011; .
[17] Brualdi, A.R.; Sanderson, G.J.; Nested species subsets, gaps, and discrepancy; Oecologia: 1998; Volume 119 ,256-264.
[18] Atmar, W.; Patterson, B.D.; ; The Nestedness Temperature Calculator: A Visual Basic Program, Including 294 Presence-Absence Matrices: Chicago, IL, USA 1995; .
[19] Nested; ; . · Zbl 0919.62083
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.