On the uniform generation of random graphs with prescribed degree sequences
Open accessAbstract
Random graphs with prescribed degree sequences have been widely used as a model of complex networks. Comparing an observed network to an ensemble of such graphs allows one to detect deviations from randomness in network properties. Here we briefly review two existing methods for the generation of random graphs with arbitrary degree sequences, which we call the ``switching'' and ``matching'' methods, and present a new method based on the ``go with the winners'' Monte Carlo method. The matching method may suffer from nonuniform sampling, while the switching method has no general theoretical bound on its mixing time. The ``go with the winners'' method has neither of these drawbacks, but is slow. It can however be used to evaluate the reliability of the other two methods and, by doing this, we demonstrate that the deviations of the switching and matching algorithms under realistic conditions are small compared to the ``go with the winners'' algorithm. Because of its combination of speed and accuracy we recommend the use of the switching method for most calculations.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The CFG model is mathematically equivalent to the Maslov-Sneppen edge-swapping null model.
“With these conditions, this CFG model is mathematically equivalent to the Maslov–Sneppen edge-swapping null model66–68.”
From Network statistics of the whole-brain connectome of Drosophila (2024) · cites this paper as [67]
No citation lists for this paper
No citation lists for this paper yet — checked again daily.
References 20 · Cited by 281
- Authors
- Milo, R., Kashtan, N., Itzkovitz, S., Newman, M. E. J., & Alon, U.
- Affiliations
- Weizmann Institute of Science (IL)
- University of Michigan (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2003
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- cond-mat/0312028
- OpenAlex
- W1499476884
- Cited by
- 281
- References
- 20
- Citations by year
- 2026: 1 · 2025: 2 · 2024: 1 · 2023: 5 · 2022: 6 · 2021: 21 · 2020: 12 · 2019: 22 · 2018: 15 · 2017: 20 · 2016: 27 · 2015: 23 · 2014: 17 · 2013: 18 · 2012: 10
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Graph Theory and Algorithms
- Social Sciences › Economics, Econometrics and Finance › Economics and Econometrics › Complex Systems and Time Series Analysis
- Keywords
- random graphs, degree sequences, graph generation, switching method, matching methods, Monte Carlo sampling, mixing time, non-uniform sampling, complex networks, network randomness
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
