Cited by 246Complex Network Analysis TechniquesGraph Theory and AlgorithmsGraph theory and applications

Configuring Random Graph Models with Fixed Degree Sequences

Open access
Fosdick, Bailey K., Larremore, Daniel B., Nishimura, Joel, Ugander, Johan·2018·SIAM Review

Abstract

Random graph null models have found widespread application in diverse research communities analyzing network datasets, including social, information, and economic networks, as well as food webs, protein-protein interactions, and neuronal networks. The most popular random graph null models, called configuration models, are defined as uniform distributions over a space of graphs with a fixed degree sequence. Commonly, properties of an empirical network are compared to properties of an ensemble of graphs from a configuration model in order to quantify whether empirical network properties are meaningful or whether they are instead a common consequence of the particular degree sequence. In this work we study the subtle but important decisions underlying the specification of a configuration model, and we investigate the role these choices play in graph sampling procedures and a suite of applications. We place particular emphasis on the importance of specifying the appropriate graph labeling---stub-labeled or vertex-labeled---under which to consider a null model, a choice that closely connects the study of random graphs to the study of random contingency tables. We show that the choice of graph labeling is inconsequential for studies of simple graphs, but can have a significant impact on analyses of multigraphs or graphs with self-loops. The importance of these choices is demonstrated through a series of three in-depth vignettes, analyzing three different network datasets under many different configuration models and observing substantial differences in study conclusions under different models. We argue that in each case, only one of the possible configuration models is appropriate. While our work focuses on undirected static networks, it aims to guide the study of directed networks, dynamic networks, and all other network contexts that are suitably studied through the lens of random graph null models.

Integrity signals

Registry

Crossref · 10.1137/16m1087175

Cites

124 of 124 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Claims the paper makes

We couldn’t retrieve this paper’s full text, so its claims and self-check weren’t run. The registry and citation checks still apply.

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.”

Cites

Flagged first, then by citations

3 of the 127 references couldn’t be matched to a known paper.

Cited by

Sorted by citations

Authors
Fosdick, B. K., Larremore, D. B., Nishimura, J., & Ugander, J.
Affiliations
  • Colorado State University (US)
  • Santa Fe Institute (US)
  • Stanford University (US)
Venue
SIAM Review
Published
2018-01
Volume
60
Issue
2
Pages
315-355
ISSN
  • 0036-1445 (ISSN-L)
  • 1095-7200
OpenAlex
W2484404803
Cited by
246
References
127
Citations by year
2026: 30 · 2025: 32 · 2024: 23 · 2023: 20 · 2022: 26 · 2021: 40 · 2020: 31 · 2019: 22 · 2018: 13 · 2017: 9
FWCI
13.55
Type
journal article
Language
en
Open access
Locations
  • SIAM Review (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Science Foundation (SES-1461495)
  • American Mathematical Society
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
  • Physical Sciences › Mathematics › Geometry and Topology › Graph theory and applications
Keywords
configuration model, degree sequences, graph labeling, vertex-labeled graphs, multigraphs, self-loops, graph sampling, network analysis

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