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 algorithms to perform this sampling have been proposed, 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 allows the random sampling of large bipartite graphs with fixed degrees roughly five times faster than curveball.