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

The DOI matches its Crossref record; 124 of the 127 references it cites were found in a registry or an index.

Configuring Random Graph Models with Fixed Degree Sequences

Open access
Fosdick, Bailey K., Larremore, Daniel B., Nishimura, Joel, Ugander, Johan·2018·SIAM Review
DOI 10.1137/16m1087175
Open this paper in CoChat — free accountOpen PDF

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.

Overview

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.

Verification

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?

Citations

Cites

Flagged first, then by citations

Show all 127 references

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

Research works printed but not linked: 32

  1. Airoldi E. M., 2008, J. Mach. Learn. Res., 9, 1981
  2. Babai L., 2016, ACM, 684
  3. Békéssy A., 1972, Stud. Sci. Math. Hungar, 7, 343
  4. C. J. Carstens, A. Berger, and G. Strona, Curveball: A New Generation of Sampling Algorithms for Graphs with Fixed Degree Sequence , preprint,https://arxiv.org/abs/1609.05137, 2016. · arXiv
  5. Carstens C. J., 2017, J. Complex Networks, 5, 337
  6. A. G. Chandrasekhar and M. O. Jackson, Tractable and Consistent Random Graph Models , Tech. report, National Bureau of Economic Research, 2014. · DOI
  7. Diaconis P., 1995, New York, 15
  8. Eggleton R. B., 1973, Infinite and Finite Sets, 1, 385
  9. R. B. Eggleton and D. A. Holton, The Graph of Type $(0,\infty,\infty)$ Realizations of a Graphic Sequence , Springer, 1979. · DOI
  10. Feder T., 2006, IEEE, 69
  11. Gail M., 1977, J. Amer. Statist. Assoc., 72, 859
  12. Gallai T., 1960, Mat. Lapok, 11, 264
  13. A. Gelman, J. B. Carlin, H. S. Stern, D. B. Dunson, A. Vehtari, and D. B. Rubin, Bayesian Data Analysis , 3rd ed., CRC Press, 2014. · DOI · Paper page
  14. Gkantsidis C., 2003, Philadelphia, 16
  15. Greenhill C., 2015, Philadelphia, 1564
  16. Havel V. J., 1955, Casopis Pest. Mat, 80, 1253
  17. G. C. Homans, The Human Group , Routledge and Kegan Paul, London, 1950.
  18. LaMar M. D., 2011, Proceedings of the Winter Simulation Conference, 3353
  19. Mahlmann P., 2005, ACM, 155
  20. R. Milo, N. Kashtan, S. Itzkovitz, M. E. Newman, and U. Alon, On the Uniform Generation of Random Graphs with Prescribed Degree Sequences , preprint,https://arxiv.org/abs/cond-mat/0312028, 2003. · arXiv
  21. J. L. Moreno and H. H. Jennings, Statistics of social configurations , Sociometry, (1938), pp. 342-374. · DOI
  22. M. E. Newman, Networks: An Introduction , Oxford University Press, Oxford, 2010.
  23. J. Nishimura, Uniformly Sampling Graphs with Self-Loops and a Given Degree Sequence , preprint,https://arxiv.org/abs/1701.04888v1, 2017. · arXiv
  24. M. Patefield, Algorithm AS159:An efficient method of generating random r$\times$c tables with given row and column totals , Applied Statistics, 30 (1981), pp. 91-97. · DOI
  25. Peixoto T. P., 2014, Phys. Rev. X, 4, 011047
  26. E. A. Power, Religious Practice and Social Support in Rural South India , Ph.D. thesis, Stanford University,https://searchworks.stanford.edu/view/11381251, 2015.
  27. Rao A. R., 1996, Sankhyā Ser. A, 58, 225
  28. Snijders T. A., 2002, J. Social Structure, 3, 1
  29. Sundararajan A., 2007, B. E. J. Theor. Econ., 7, 46
  30. Ugander J., 2013, ACM, 1307
  31. Ugander J., 2013, ACM, 329
  32. Viger F., 2005, Springer, 440

Cited by

Sorted by citations

Items 201–246 of 246

Related

See all

Metadata

Authors
Fosdick, B. K., Larremore, D. B., Nishimura, J., & Ugander, J.
Affiliations
  • Colorado State University (US)
  • Santa Fe Institute (US)
  • Stanford University (US)
ORCID
Venue
SIAM Review
Publisher
Society for Industrial & Applied Mathematics (SIAM)
Published
2018-01
Volume
60
Issue
2
Pages
315-355
ISSN
  • 0036-1445 (ISSN-L)
  • 1095-7200
DOI
10.1137/16m1087175
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
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 › Computational Theory and Mathematics › Graph Theory and Algorithms
  • Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › 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