Fast sequential algorithm for generating directed random graphs with a given degree sequence
Femke van Ieperen, Ivan Kryven · arXiv (Cornell University) · 2021
We propose a near-linear complexity algorithm for generating simple directed random graphs with a given degree sequence and show that this algorithm provides a means of uniform sampling for large graphs. The algorithm is applicable when the maximum degree, $d_\text{max},$ is asymptotically dominated by $m^{1/4}$ with $m$ being the number of edges and admits an implementation with the expected running time of the order of $m d_\text{max}$.