The Babe Ruth Algorithm: a fast, unbiased procedure to randomize presence-absence data matrices with fixed row and column totals

Abstract

A well-known problem in numerical ecology is how to recombine presence-absence matrices without altering row and column totals. A few solutions have been proposed, but all of them present some issues in terms of statistical robustness (i.e. their capability to generate different matrix configurations with the same probability) and their performance (i.e. the computational effort they require to generate a null matrix). Here we introduce the 'Babe Ruth Algorithm', a new procedure that differs from existing ones in that it focuses rather on matrix information content than on matrix structure. We demonstrate that the algorithm can sample uniformly the set of all possible matrix configurations requiring a computational effort orders of magnitude lower than that required by available methods, making it possible to easily randomize matrices larger than 10^8 cells.

Manuscript under review

References in corpus (1)

• Exact sampling and counting for fixed-margin matrices

Cited by in corpus (23)

• The Physics of Financial Networks
• Nestedness in complex networks: Observation, emergence, and implications
• Randomizing bipartite networks: the case of the World Trade Web
• backbone: An R Package for extracting the backbone of bipartite projections
• Comparing Alternatives to the Fixed Degree Sequence Model for Extracting the Backbone of Bipartite Projections
• Grand canonical validation of the bipartite International Trade Network
• Meta-validation of bipartite network projections
• The ambiguity of nestedness under soft and hard constraints
• Reconstructing mesoscale network structures
• Fluctuating ecological networks: a synthesis of maximum-entropy approaches for pattern detection and process inference
• Large-scale network motif analysis using compression
• Associative nature of event participation dynamics: a network theory approach
• Pattern detection in bipartite networks: a review of terminology, applications and methods
• A unifying framework for fast randomization of ecological networks with fixed (node) degrees
• fastball: A fast algorithm to sample bipartite graphs with fixed degree sequences
• A Fast MCMC for the Uniform Sampling of Binary Matrices with Fixed Margins
• Entropy-based models to randomize real-world hypergraphs
• The connectivity of graphs of graphs with self-loops and a given degree sequence
• Parallel Global Edge Switching for the Uniform Sampling of Simple Graphs with Prescribed Degrees
• False positives using social cognitive mapping to identify childrens' peer groups
• Higher-order null models as a lens for social systems
• An impossibility result for Markov Chain Monte Carlo sampling from micro-canonical bipartite graph ensembles
• Italian Twitter semantic network during the Covid-19 epidemic