A method for generating connected Erdős–Rényi random graphs
Journal of Complex Networks · 05.05.2026 · 14 (3)
DOI: 10.1093/comnet/cnag015 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Complex Networks, online erschienen am 21.05.2026. Verfasst von Boris Chinyaev. Die Arbeit nennt 22 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
APA
Chinyaev, B. (2026). A method for generating connected Erdős–Rényi random graphs. Journal of Complex Networks, 14(3). https://doi.org/10.1093/comnet/cnag015
Vancouver
Chinyaev B. A method for generating connected Erdős–Rényi random graphs. Journal of Complex Networks. 2026;14(3). doi:10.1093/comnet/cnag015
BibTeX
@article{Chinyaev2026,
author = {Chinyaev, Boris},
title = {A method for generating connected Erdős–Rényi random graphs},
journal = {Journal of Complex Networks},
year = {2026},
volume = {14},
number = {3},
doi = {10.1093/comnet/cnag015}
}
EUVIMED