Fast sequential algorithm for generating directed random graphs with a given degree sequence
Publication date
2021-04-12
Authors
Ieperen, Femke van
Kryven, I.
Editors
Advisors
Supervisors
Document Type
/dk/atira/pure/researchoutput/researchoutputtypes/workingpaper/preprint
Metadata
Show full item recordCollections
License
cc_by_nc_sa
Abstract
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, dmax, is asymptotically dominated by m1/4 with m being the number of edges and admits an implementation with the expected running time of the order of mdmax.
Keywords
math.PR, 05C80, 05C20, 68W20, 68W25, Random Graphs, Directed Graphs, Randomised Approximation Algorithms
Citation
Ieperen, F V & Kryven, I 2021 'Fast sequential algorithm for generating directed random graphs with a given degree sequence' arXiv, pp. 1-39. https://doi.org/10.48550/arXiv.2103.15958