EUVIMEDEUVIMED entdecken
Crossref

A method for generating connected Erdős–Rényi random graphs

Boris Chinyaev

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →