A method for generating connected Erdős–Rényi random graphs
Abstract
Abstract We consider an exact algorithm for generating connected Erdős–Rényi random graphs $ \boldsymbol{G(n, p)} $. The method is based on coupling the graph exploration process to an inhomogeneous Poisson random walk, which yields an exact sampler that runs in $ \boldsymbol{O(n)} $ time in the sparse regime $ \boldsymbol{p\,=\,c/n} $. We also show how the method extends to the $ \boldsymbol{G(n, M)} $ model via an additional acceptance–rejection step.
Fields of Study & Subjects
Topological and Geometric Data Analysis
Random Matrices and Applications
Markov Chains and Monte Carlo Methods
Publication details
- Journal / source
- Journal of Complex Networks
- Volume
- 14
- Issue
- 3
- Publication date
- 19 April 2026
- Language
- EN