Source-linked AI summary
Configuring Random Graph Models with Fixed Degree Sequences
Bailey K. Fosdick, Daniel B. Larremore, Joel Nishimura, Johan Ugander
TL;DR
Configuration models are widely used as fixed-degree-sequence null models, but studies often fail to specify the graph space over which uniformity is defined. The paper reviews graph-space choices, develops sampling approaches, and demonstrates that labeling choices can change conclusions for non-simple graphs. It concludes that stub-labeled and vertex-labeled spaces are not interchangeable in such analyses, while they are equivalent for simple graphs.
Problem
Researchers often study “the configuration model” without specifying the graph space defining its uniform distribution, despite applications across network science and other fields.
Method
The paper reviews eight graph spaces, organizes their selection around self-loops, multiedges, and labeling, and studies sampling primarily through correctly specified Markov chains.
Results
Stub-labeled and vertex-labeled spaces are not interchangeable: substituting one for the other inverted degree-correlation hypothesis-test conclusions and changed the community-detection optimization landscape.
Takeaways & Limitations
Configuration-model analyses should select graph spaces using network context, especially when self-loops or multiedges are possible.
Takeaways & Limitations
The paper focuses on undirected static networks, while mixing-time results for non-simple graphs remain poorly developed.
Abstract
from arXiv · showhide
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 family of 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 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 vignettes, analyzing 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.
1 Introduction
Configuration models are uniform distributions over graphs with a fixed degree sequence, but their graph space must be specified because different choices can produce different analyses. This paper reviews eight graph spaces and provides questions for selecting an appropriate model.
- Configuration models: Configuration models preserve an empirical graph’s degree sequence while randomizing other structure for null-model comparisons.They are also used to sample realistic graphs for studying algorithms, dynamical models, and optimization routines.
- Why graph-space choices matter: Researchers often discuss one configuration model without specifying the graph space underlying its uniform distribution, creating misunderstandings across fields.The paper distinguishes eight commonly arising graph spaces and their corresponding uniform distributions.
- Finite-network scope: Asymptotic similarities between some graph spaces do not resolve finite-network analyses, because many practical graphs are too small or dense for those conditions.The paper notes that not all differences become asymptotically small, even when some do under restricted degree sequences.
- Choosing a null model: For non-simple graphs, choosing the labeling can materially change the null model, so the paper recommends answering three graph-space questions using network context.The first two questions determine graph type; the third distinguishes vertex-labeled from stub-labeled spaces when self-loops or multiedges are possible.
- Graph-space dimensions: Graph spaces differ by whether they allow self-loops or multiedges and whether vertices or stubs carry labels.A vertex-labeled graph has distinct vertex labels, whereas a stub-labeled graph gives distinct labels to every half-edge.
- Labeling choices: For simple graphs, vertex- and stub-labeled spaces yield equivalent uniform distributions because every vertex-labeled graph corresponds to the same number of stub-labeled graphs.This equivalence depends on the fixed degree sequence and does not extend generally to graphs with self-loops or multiedges.
2 Markov chain Monte Carlo Sampling
The paper develops MCMC methods for uniformly sampling fixed-degree graph spaces, distinguishing stub-labeled from vertex-labeled models and accounting for loops and multiedges. Appropriate transition probabilities and connectivity results yield uniform sampling, while vertex-labeling and non-simple structures introduce important mixing-time and model-specific complications.
- Sampling framework: The authors design MCMC chains whose stationary distribution is uniform over graph spaces with a fixed degree sequence.The approach treats stub-labeled and vertex-labeled spaces separately and establishes the conditions needed for valid sampling.
- Stub-labeled spaces: Regularity, aperiodicity, and connectivity together establish ergodic chains that sample every possible graph uniformly.Connectivity is essential for reaching all graphs, while aperiodicity supports reliable subsampling of chains.
- Labeling choices: For simple graphs, vertex-labeled and stub-labeled sampling are equivalent because each vertex-labeled graph corresponds to the same number of stub-labeled graphs.For non-simple graphs, this proportionality fails, so vertex-labeled chains require adapted transition rules.
- Vertex-labeled spaces: Vertex-labeled chains restore uniformity by modifying or rejecting swaps so transition mass is balanced in both directions.The resulting chains have doubly stochastic transition matrices and uniform stationary distributions, including spaces with loops and multiedges.
- Mixing times: Algorithm 3 accelerates mixing by down-sampling higher-probability swaps, but non-simple-graph mixing times remain poorly understood.The algorithm mixes substantially faster empirically on degree sequences with higher degrees, while rejection sampling may still produce large mixing times when loops and multiedges are common.
3 Other sampling methods and other null models
The paper reviews direct and Markov-chain methods for sampling configuration-model graph spaces, emphasizing that specialized spaces may require modified swaps or additional constraints. It also identifies settings where suitable null models remain difficult to define.
- Sampling methods: Direct methods construct graphs independently, whereas edge-swap Markov chains manipulate an initial graph toward a uniform stationary distribution.Uniform sampling is closely related to counting graphs in the target space.
- Sampling methods: Rejection sampling adapts stub matching for restricted spaces such as simple graphs by discarding samples containing forbidden self-loops or multiedges.The supplied passage introduces this adaptation as the simplest approach for restricted graph spaces.
- Sampling methods: 4M is sufficient for approximate uniform sampling when kmax = O(M1/4−τ) for some τ > 0, but this asymptotic result gives no clear guarantee for a fixed empirical graph.The condition is asymptotic and may not directly certify sampling quality for a particular observed network.
- Markov chains for other spaces: Connected, loopy, and directed graph spaces require alternatives or extensions to the double-edge swap because the ordinary chain may fail to connect the full target space.Examples include k-Flipper swaps for connected graphs, triangle-loop swaps for some loopy graphs, and directed triangle reversals.
- Other null models: As networks become richer, configuration models become less evidently appropriate null models and may require modeling a hypothesized generative process.Directed citation networks are given as an example where causality constraints matter.
- Weighted graphs: For weighted graphs without natural edge-multiplicity interpretations, preserving degrees and total weights while randomizing edges and weights remains an open problem.Randomly assigning weights can break vertex total weights, while coupling weights to edge existence requires assumptions about relationships.
4 Graph enumeration
Graph enumeration explains how labeled graph spaces differ and how samples can theoretically be reweighted between them. These conversions can be computationally impractical, especially for multigraphs, self-loops, and unlabeled spaces.
- Labeled graph spaces: A vertex-labeled graph can correspond to multiple stub-labeled graphs, allowing enumeration to expose differences between the two graph spaces.The correspondence is illustrated through isomorphism-class sizes.
- Sampling conversion: Reweighting can theoretically convert a uniform sample from one graph space into a uniform sample from another, but large distributional differences can make the approach impractical.Graphs common under one distribution may be extremely rare under the other, requiring unreasonably large sample sizes.
- Labeled graph spaces: For simple graphs, each vertex-labeled graph with a fixed degree sequence has the same number of corresponding stub-labeled graphs, so the two spaces have matching relative isomorphism-class sizes.The count depends only on the degree sequence, not other properties of the graph.
- Labeled graph spaces: For multigraphs or graphs with self-loops, correspondence multiplicities depend on edge multiplicities and loop structure rather than only on the degree sequence.The counting factors adjust for identical configurations involving multiedges and self-loops.
- Unlabeled graph spaces: Uniform sampling or enumeration for unlabeled graph spaces is computationally difficult because it is tied to graph isomorphism and automorphism counts.The paper states that polynomial-time direct or rapidly mixing Markov-chain samplers are unlikely under standard complexity assumptions.
5 Applications
Three applications show that configuration-model graph-space choices can substantially alter null distributions, hypothesis-test conclusions, and community-detection results. The appropriate model depends on the network’s structure and the scientific question, including whether simplification, self-loops, or multiedges are justified.
- 5.1 Degree assortativity in a collaboration network: Configuration-model graph spaces produce substantially different null distributions for degree assortativity in the geometers collaboration network.Including or excluding self-loops and multiedges changes the distributions, while stub- and vertex-labeling can yield nearly disjoint correlation ranges.
- 5.1 Degree assortativity in a collaboration network: The degree-assortativity null model can reverse study conclusions, from strong assortativity under stub-labeled models to tempered or slightly disassortative interpretations under vertex-labeled alternatives.The paper identifies the vertex-labeled multigraph model as appropriate for the collaboration network.
- 5.2 Trait assortativity in a barn swallow interaction network: Color-assortativity tests for barn swallows yield p = 0.001 under simple graphs but p = 0.852 under the selected vertex-labeled multigraph model.The former supports significant correlation between interaction presence and plumage color, whereas the latter finds no evidence that interaction counts are significantly correlated with color.
- 5.2 Trait assortativity in a barn swallow interaction network: The configuration model changes the baseline for interpreting assortativity, so comparison with zero can be incorrect when the null distribution is centered elsewhere.This affects both the hypothesis being tested and the conclusion drawn from the observed correlation.
- 5.3 Community detection in a South Indian village social support network: Different configuration-model null matrices change modularity landscapes and produce different community partitions from identical initial states in most tested cases.The vertex-labeled multigraph model favors grouping connected vertices with differing degrees more than the stub-labeled loopy multigraph model.
- 5.3 Community detection in a South Indian village social support network: Despite differing agglomerative choices, both modularity models produced the same optimal 10-community partition, with identical partitions at only 43% of agglomerative steps.The network contains 782 vertices, and the models’ agreement was substantially higher only for the final optimum than across intermediate partitions.
- 5.3 Community detection in a South Indian village social support network: The paper recommends choosing the configuration-model graph space from which the observed network is plausibly drawn to preserve modularity results’ interpretability.The default stub-labeled loopy multigraph null model is not necessarily appropriate for real-world networks, especially when analyzing simple graphs.
6 Conclusions
The paper distinguishes eight configuration-model graph spaces using choices about self-loops, multiedges, and stub labels. These choices can alter empirical conclusions, while the proposed MCMC algorithms uniformly sample the selected spaces.
- 6 Conclusions: Eight overlapping graph spaces arise from three choices: allowing self-loops, allowing multiedges, and labeling stubs.These questions, combined with knowledge of the real-world network, guide selection of an appropriate graph space.
- 6 Conclusions: Stub-labeled and vertex-labeled configuration models are not interchangeable: substituting one for the other inverted degree-correlation tests and changed community-detection optimization.
- 6 Conclusions: Three MCMC algorithms were presented and proved capable of uniformly sampling the eight discussed graph spaces.Pseudocode and Python implementations were provided and used in three applications.
- 6 Conclusions: Rigorous mixing-time bounds for the MCMC approaches remain unestablished.The paper identifies mixing-time analysis as a direction for future investigation.
- 6 Conclusions: The paper synthesizes a scattered literature in which repeated discoveries and inconsistent naming have complicated the study of configuration models.Its summaries aim to clarify graph spaces, sampling techniques, and applications.
Supplementary Materials: Algorithm 3
Algorithm 3 is a vertex-labeled MCMC sampler for fixed-degree graph spaces. It improves efficiency over Algorithm 2 by balancing forward and reverse double-edge-swap probabilities.
- Supplementary Materials: Algorithm 3: Algorithm 3 samples vertex-labeled graph spaces using a Markov chain Monte Carlo procedure.The algorithm is identified as “vertex-labeled MCMC.”
- Supplementary Materials: Algorithm 3: For vertex-labeled spaces, Algorithm 3 computes forward and reverse probabilities for each double-edge swap, then down-samples the higher-probability swap to match the lower probability.This probability adjustment accelerates mixing relative to Algorithm 2.
- Supplementary Materials: Algorithm 3: The procedure starts from an initial graph and produces a sequence of sampled graphs while preserving the selected graph-space constraints.It repeatedly chooses two edges, randomizes endpoint orientation, and rejects swaps that leave the graph space.