Coin-flipping, ball-dropping, and grass-hopping for generating random graphs from matrices of edge probabilities

Arjun S. Ramani, Nicole Eikmeier, David F. Gleich

Common models for random graphs, such as Erdős-Rényi and Kronecker graphs, correspond to generating random adjacency matrices where each entry is non-zero based on a large matrix o…