Source-linked AI summary
Efficient and exact sampling of simple graphs with given arbitrary degree sequence
Charo I. Del Genio, Hyunju Kim, Zoltan Toroczkai, Kevin E. Bassler
TL;DR
Sampling graphs with a prescribed degree sequence is difficult when full connectivity is unavailable and existing methods have uncontrolled mixing or rejection behavior. The paper presents an exact polynomial-time construction that generates independent weighted samples, enabling unbiased or distribution-specific observables. The method is rejection-free and applies to arbitrary graphical degree sequences, with sample-weight behavior studied across several degree-sequence families.
Problem
Graph sampling from all realizations of an arbitrary degree sequence is needed for network modeling, but existing methods have uncontrolled mixing or rejection behavior.
Method
The paper sequentially constructs simple graph realizations by choosing graphicality-preserving hub connections and assigning each sample an explicit weight.
Results
O(N 3) steps: the algorithm produces an independent sample, while explicit weights permit unbiased measurements and arbitrary target distributions.
Takeaways & Limitations
The rejection-free construction provides a practical way to sample degree-sequence graph ensembles without backtracking or restarting.
Abstract
from arXiv · showhide
Uniform sampling from graphical realizations of a given degree sequence is a fundamental component in simulation-based measurements of network observables, with applications ranging from epidemics, through social networks to Internet modeling. Existing graph sampling methods are either link-swap based (Markov-Chain Monte Carlo algorithms) or stub-matching based (the Configuration Model). Both types are ill-controlled, with typically unknown mixing times for link-swap methods and uncontrolled rejections for the Configuration Model. Here we propose an efficient, polynomial time algorithm that generates statistically independent graph samples with a given, arbitrary, degree sequence. The algorithm provides a weight associated with each sample, allowing the observable to be measured either uniformly over the graph ensemble, or, alternatively, with a desired distribution. Unlike other algorithms, this method always produces a sample, without back-tracking or rejections. Using a central limit theorem-based reasoning, we argue, that for large N, and for degree sequences admitting many realizations, the sample weights are expected to have a lognormal distribution. As examples, we apply our algorithm to generate networks with degree sequences drawn from power-law distributions and from binomial distributions.
I. INTRODUCTION
The paper frames degree-sequence graph sampling as important for network modeling when full connectivity data is unavailable. It introduces an exact, rejection-free approach that produces weighted samples for unbiased or distribution-specific observables.
- Motivation: Degree sequences are often the only available network information, requiring construction of representative graphs for modeling.The paper gives epidemiological contact networks as an example where partner counts are known but identities are not.
- Motivation: Sampling all realizations becomes necessary because the number of graphs realizing a degree sequence grows rapidly with network size.Systematic construction is practical mainly for short sequences.
- Limitations of prior methods: Existing link-swap MCMC methods are largely heuristic and have poorly characterized sampling behavior.The passage notes that only special sequences have better-understood behavior.
- Contribution: The proposed algorithm exactly samples arbitrary graphical degree sequences in polynomial time without rejection or backtracking.It always finishes with a simple graph realization.
- Contribution: Although generated samples are non-uniform, explicit sample weights enable uniform observables or observables under any desired distribution.The weights correct the sampling bias during measurement.
II. MATHEMATICAL FOUNDATIONS
The mathematical foundations provide tests and structural results for deciding graphicality under ordinary or star-shaped link constraints. These results support the algorithm's sequential construction of valid graph realizations.
- Graphicality: The Erdős-Gallai theorem gives a necessary and sufficient test for whether a non-increasing degree sequence is graphical.The conditions include an even degree sum and inequalities for all relevant k.
- Graphicality: Star-constrained graphicality reduces avoidance of forbidden links at one node to connecting that node to its leftmost adjacency set.The leftmost set contains the highest-degree eligible nodes.
- Graphicality: The Havel-Hakimi consequence guarantees a realization containing a link from the first node to any chosen node.This applies to unconstrained non-increasing graphical sequences.
- Transformations: Reducing the degree of a higher-degree node while increasing that of a lower-degree node preserves graphicality under the same star constraint.The lemma requires the two nodes to be distinct, eligible, and different from the constrained node.
- Residual sequences: If connecting a constrained node to a higher-degree candidate yields a non-graphical residual sequence, connecting it to a lower-degree candidate also cannot restore graphicality.The theorem is stated for eligible candidates with ordered degrees.
III. BIASED SAMPLING
The method deliberately generates graphs with bias but computes weights that recover unbiased observables. Appropriate weights can also target any chosen distribution over graph realizations.
- Biased sampling: Every simple graph with the given finite degree sequence has non-zero generation probability, but samples are not uniform.The sampling procedure is ergodic yet biased.
- Biased sampling: Weighted averages using inverse relative generation probabilities provide unbiased estimates of network observables.The sample-specific weight and a normalization denominator define the estimator.
- Biased sampling: Choosing appropriate sample weights permits sampling according to any arbitrary distribution over the realization set.Uniform sampling is one special case.
IV. THE ALGORITHM
The algorithm constructs a graph sequentially by choosing eligible neighbors for hub nodes while preserving graphicality. It records the branching choices to calculate each sample's correction weight.
- Graph construction: At each stage, the algorithm selects a hub and builds an allowed set of nodes whose connection preserves graphicality.An eligible node is chosen uniformly and linked to the hub.
- Graph construction: After each link, residual degrees and forbidden nodes are updated before the next allowed set is constructed.The process repeats hub by hub until all links are made.
- Sample weights: The sample weight multiplies the sizes of all allowed sets and divides by the factorials of the hubs' residual degrees.The hubs are indexed by their residual degrees when selected.
- Sample weights: The weight reflects both the number of available choices at each hub and equivalent orderings of its residual stubs.A single-realization sequence has weight 1.
A. Building the allowed set
The algorithm constructs the allowed set A by identifying a maximum fail-degree: nodes above it can be included, while nodes at or below it cannot. This procedure uses graphicality tests on a temporary residual sequence and recomputes A after each link placement.
- The allowed set A contains non-forbidden nodes with degrees above the maximum fail-degree, plus the hub’s leftmost adjacency set and equal-degree non-forbidden nodes.If no fail-degree exists, A includes all non-forbidden nodes.
- The temporary sequence D′ assumes links from the hub to all but the lowest-degree node in its leftmost adjacency set, with those nodes marked forbidden.The resulting sequence remains graphical by the star-constrained graphicality theorem.
- For each relevant degree, it is sufficient to test the last non-forbidden node of that degree when evaluating whether the final hub link causes non-graphicality.A fail-degree is detected when the Erdős-Gallai inequality fails for the resulting sequence D′′.
- Testing only D′ identifies fail-degrees through three cases comparing L_k and R_k: equality, a one-unit gap, or a gap of at least two.The algorithm can stop after the equality case or when k reaches the specified stopping index.
- The allowed set must be reconstructed after every link because the residual degree sequence changes during sample construction.
B. Implementing the Erdős-Gallai test
The implementation accelerates Erdős-Gallai comparisons by updating L_k and R_k with recurrence relations rather than repeatedly summing many terms. Crossing-indices further limit the calculations needed across k.
- Recurrence relations replace repeated sums when calculating L_k and R_k, reducing the cost of testing long degree sequences.The direct calculation becomes especially intensive when the degree distribution decreases slowly.
- The crossing-index x_k is the first index whose degree is below k+1, with x_k = N when no such index exists.Because x_k cannot increase with k, calculations can stop after a threshold k*.
- A table of crossing-indices created while constructing D′ supports efficient sequential computation of L_k and R_k.The same recurrence-based calculation can also accelerate an Erdős-Gallai graphicality test.
- For power-law sequences with γ = 3, the fitted scaling exponents are α = 1.22042 ± 0.00007 for m and β = 0.8599 ± 0.0018 for σ.The logarithmic-scale linearity indicates power-law scaling with N.
V. SAMPLE WEIGHTS
The algorithm assigns each generated graph a weight based on allowed-set sizes and residual-degree factorials. For large sequences with many realizations, the resulting weights are expected to be lognormally distributed, consistent with power-law-sequence simulations.
- The logarithm of each sample weight combines the logarithms of allowed-set sizes with a subtraction involving factorials of hub residual degrees.The weight itself is the product of allowed-set sizes divided by the product of those factorials.
- For large degree sequences with many graphical realizations, central-limit reasoning predicts an approximately lognormal distribution of sample weights.The prediction does not extend to large sequences having only a small number of realizations.
- Power-law-sequence experiments with γ = 3 found that the distribution of log weights was well approximated by a Gaussian fit.
- The mean and standard deviation of log weights scale as powers of N for power-law sequences, with qualitatively similar behavior for binomial and bounded uniform degree sequences.The binomial sequences correspond to Erdős-Renyi graphs with pN = 4.
- Uniform degree sequences without an imposed upper degree limit do not produce lognormally distributed sample weights.
VI. COMPLEXITY
The algorithm’s complexity is bounded by O(N^3) in the densest simple-graph case, with lower bounds for sparser graphs. Estimated average complexity depends on the degree distribution and any imposed maximum-degree cutoff.
- The complexity estimate is obtained by combining a worst-case bound for a fixed degree sequence with an average-case estimate over random degrees drawn from P(d).
- The worst-case complexity is O(N^3) when the graph has O(N^2) links, while sparse graphs with O(N) links have an O(N^2) bound.
- The estimated complexity uses expected ordered degrees ˆd_j and sums through the allowed maximum degree d_max.A structural cutoff can replace the nominal maximum degree N − 1.
- For power-law sequences without a cutoff, the complexity order approaches 3 as γ → 0; imposing a structural cutoff reduces this limiting order to 2.5.
- Measured execution times for γ = 0, 2, and 3 matched or slightly undercut the estimated complexity orders.
VII. DISCUSSION
The algorithm efficiently generates independent samples for arbitrary graphical degree sequences while explicitly correcting its sampling bias. Its guaranteed progress also avoids the backtracking and uncontrolled failures associated with competing approaches.
- The algorithm produces an independent sample in at most O(N^3) steps for any graphical degree sequence or ensemble.
- Although sampling is biased, explicit relative probabilities permit unbiased measurements and re-weighting to any arbitrary distribution.
- Unlike the configuration model, the algorithm always proceeds successfully without backtracking or restarting.
- For P(d) = const. and N = 100, the configuration model produced no sample after 24 hours, whereas this algorithm produced 104 samples in 30 seconds.