fastball: A fast algorithm to sample bipartite graphs with fixed degree sequences
arXiv:2112.04017 · doi:10.1093/comnet/cnac049
Abstract
Many applications require randomly sampling bipartite graphs with fixed degrees, or randomly sampling incidence matrices with fixed row and column sums. Although several sampling algorithms exist, the ``curveball'' algorithm is the most efficient with an asymptotic time complexity of O(n log n), and has been proven to sample uniformly at random. In this paper, we introduce the ``fastball'' algorithm, which adopts a similar approach but has an asymptotic time complexity of O(n). We show that a C++ implementation of fastball randomly samples large bipartite graphs with fixed degrees faster than curveball, and illustrate the value of this faster algorithm in the context of the fixed degree sequence model for backbone extraction.
Journal of Complex Networks (2022)
References in corpus (6)
- The Babe Ruth Algorithm: a fast, unbiased procedure to randomize presence-absence data matrices with fixed row and column totals
- Equivalence and nonequivalence of ensembles: Thermodynamic, macrostate, and measure levels
- Sequential importance sampling for multiway tables
- backbone: An R package to extract network backbones
- Comparing Alternatives to the Fixed Degree Sequence Model for Extracting the Backbone of Bipartite Projections
- Ensemble inequivalence in random graphs