backbone (version 2.0.0)

fastball: Randomize a binary matrix using the fastball algorithm

Description

fastball randomizes a binary matrix, preserving the row and column sums

Usage

fastball(M, R = nrow(M), C = ncol(M), trades = 5 * R)

Arguments

M

matrix: a binary matrix (or a list; see details)

R

integer: number of rows in M

C

integer: number of columns in M

trades

integer: number of trades; the default is 5R trades (approx. mixing time)

Value

matrix: A random binary matrix with same row sums and column sums as M.

Details

fastball is an optimized C++ implementation of the curveball algorithm (Strona et al.. 2014) for generating random binary matrices. There are two ways that fastball can be made even more efficient. First, be sure that M is oriented wide (more columns than rows) rather than long (more rows than columns). Second, if fastball is used in a loop to repeatedly sample from the space of all 0/1 matrices with the same row and column sums as M, supply M as an indexed list of the locations of the 1s using apply(M==1, 1, which). This indexed list should be generated just once, outside the loop. When B is supplied as an indexed list, R and C must be specified.

The fastball algorithm is the fastest known method for randomly sampling binary matrices with given row and column sums, and is used by fdsm() to extract the backbone from a bipartite projection using the fixed degree sequence model.

References

Godard, Karl and Neal, Zachary P. 2021. fastball: A fast algorithm to sample binary matrices with fixed marginals. arXiv:2112.04017

Examples

# NOT RUN {
M <- matrix(rbinom(200,1,0.5),10,20)  #A random 10x20 binary matrix
fastball(M)  #Fast generation of a random matrix
Mlist <- apply(M==1, 1, which)  #Converting M to a list
fastball(Mlist, R = 10, C = 20)  #Even faster generation of a random matrix
# }