fastball: A fast algorithm to sample bipartite graphs with fixed degree sequences

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, running in O(n log n) time, and has been proven to sample uniformly at random. In this paper, we introduce the fastball algorithm, which adopts a similar approach but runs in O(n) time. We show that fastball randomly samples large bipartite graphs with fixed degrees more than four times faster than curveball, and illustrate the value of this faster algorithm in the context of the fixed degree sequence model for backbone extraction.