PaperlayerView exact revision on arXiv

Source-linked AI summary

A Sequential Algorithm for Generating Random Graphs

Mohsen Bayati, Jeong Han Kim, Amin saberi

arXiv:cs/0702124v5cs.CCcs.DM

TL;DR

The paper seeks fast, rigorous generation and counting of simple graphs with a prescribed degree sequence. It proposes sequential edge sampling with importance weighting and proves near-linear asymptotic generation guarantees, FPRAS bounds, and a broader regular-graph degree range.

  • Problem

    Existing graph-generation methods can be too slow for large networks, while earlier sequential-importance-sampling approaches were mostly empirical or could be slow in some cases.

  • Method

    The method sequentially adds eligible edges using probabilities weighted by remaining degrees and a correction factor, then applies sequential importance sampling for approximation.

  • Results

    For d_max = O(m^(1/4−τ)), generation runs in O(m d_max) time with asymptotically uniform output, while the FPRAS counting runtime is O(m d_max ε^−2 log(1/δ)).

  • Takeaways & Limitations

    The approach extends asymptotically uniform regular-graph generation to d = O(n^(1/2−τ)) and supplies rigorous approximation guarantees for counting and generation.

  • Takeaways & Limitations

    The direct output distribution is asymptotically close to uniform only for sufficiently large m, and exact accept/reject correction is unavailable because the output probability is unknown.

Abstract

from arXiv · show

We present a nearly-linear time algorithm for counting and randomly generating simple graphs with a given degree sequence in a certain range. For degree sequence $(d_i)_{i=1}^n$ with maximum degree $d_{\max}=O(m^{1/4-τ})$, our algorithm generates almost uniform random graphs with that degree sequence in time $O(m\,d_{\max})$ where $m=\f{1}{2}\sum_id_i$ is the number of edges in the graph and $τ$ is any positive constant. The fastest known algorithm for uniform generation of these graphs McKay Wormald (1990) has a running time of $O(m^2d_{\max}^2)$. Our method also gives an independent proof of McKay's estimate McKay (1985) for the number of such graphs. We also use sequential importance sampling to derive fully Polynomial-time Randomized Approximation Schemes (FPRAS) for counting and uniformly generating random graphs for the same range of $d_{\max}=O(m^{1/4-τ})$. Moreover, we show that for $d = O(n^{1/2-τ})$, our algorithm can generate an asymptotically uniform $d$-regular graph. Our results improve the previous bound of $d = O(n^{1/3-τ})$ due to Kim and Vu (2004) for regular graphs.

1 Introduction

The paper addresses fast, principled generation of simple graphs with a prescribed degree sequence, where existing methods are slow or lack rigorous guarantees. It develops a sequential-importance-sampling approach with improved guarantees for general and regular graphs.

  • Motivation: The paper targets nearly-linear-time generation of simple graphs with a given degree sequence, motivated by applications and the practical limits of slower exact methods.The paper notes applications in biological-network motif detection and Internet-topology simulation, while slow algorithms have encouraged non-rigorous heuristics.
  • Main algorithm and guarantees: For non-regular degree sequences, the method sequentially adds edges with probabilities based on remaining degrees and a correction factor, achieving asymptotically uniform generation in O(m d_max) time when d_max = O(m^(1/4−τ)).The edge-selection probability is proportional to d̂_i d̂_j(1−d_i d_j/4m) over eligible non-adjacent pairs.
  • Motivation: Sequential importance sampling is used to turn a simple sequential graph-generation procedure into a fully polynomial randomized approximation scheme.Earlier SIS results were largely empirical, whereas this work supplies rigorous approximation guarantees.
  • Technical contributions: The algorithm independently proves McKay’s estimate through a combinatorial argument controlling its failure probability.Earlier analyses relied on McKay’s estimate; this paper replaces that dependence with a new proof.
  • Technical contributions: For d-regular graphs, the concentration analysis extends asymptotically uniform generation to d = O(n^(1/2−τ)), beyond the prior d = O(n^(1/3−τ)) range.The extension uses combinatorial structure and a martingale tail inequality where previous polynomial inequalities do not work.
  • Other applications and extensions: The analysis also suggests correcting expected-degree random-graph models with a factor 1−d_i d_j/(2m), and related ideas have been applied to graphs with large girth.The paper connects these extensions to applications such as high-performance LDPC-code design.

2 Our Algorithm

The algorithm sequentially constructs a simple graph by selecting eligible vertex pairs according to weighted remaining degrees, then provides asymptotic-uniformity and FPRAS guarantees. Its scope includes general degree sequences, regular graphs, bipartite graphs, and approximate counting.

  • Procedure A: The procedure initializes an empty graph and repeatedly selects a non-adjacent pair with probability proportional to d̂_i d̂_j(1−d_i d_j/(4m)), reducing both remaining degrees after each edge.Here d̂_i denotes the remaining degree of vertex i.
  • General degree sequences: For d_max = O(m^(1/4−τ)), Procedure A succeeds with probability 1−o(1), runs in expected O(m d_max) time, and generates each graph within a 1±o(1) factor of uniform probability.This is the main asymptotic guarantee for arbitrary graphical degree sequences.
  • Regular graphs: For d = O(n^(1/2−τ)), Procedure A converges in total variation to the uniform distribution over d-regular graphs, apart from an o(|L(n,d)|) exceptional subset.The result is stated for arbitrary positive τ as n tends to infinity.
  • FPRAS results: Theorem 3 gives an FPRAS for counting with expected time O(m d_max ε^−2 log(1/δ)) and for random generation with expected time O(m d_max ε^−2).The guarantees apply for d_max = O(m^(1/4−τ)) and any ε,δ > 0.
  • Extensions and approximation: The same theorem framework extends to bipartite graphs by restricting selected pairs to vertices in different parts, while the asymptotic results are desirable to supplement with FPRAS guarantees for finite n.The paper defines FPRAS guarantees in terms of polynomial dependence on m, 1/ε, and log(1/δ).

3 Definitions and the Main Idea

The paper replaces uniform selection in the configuration model with weighted sequential choices and uses sequential importance sampling to estimate graph counts and generation probabilities.

  • 3.1 Weighted configuration model: Non-regular degree sequences require non-uniform selection because uniform suitable-pair sampling can bias graph probabilities exponentially.Procedure A weights a suitable pair from vertices i and j proportionally to 1 − d_i d_j/(4m).
  • 3.1 Weighted configuration model: The weighted procedure sequentially constructs valid partial matchings while correcting degree-dependent bias toward edges joining larger-degree vertices.The correction factor 1 − d_i d_j/(4m) approximates the exponential bias-canceling factor described in the paper.
  • 3.2.1 FPRAS for Counting via SIS: Sequential importance sampling estimates the number of graphs by averaging inverse-probability variables from k independent runs of Procedure A.The resulting estimator is an (ε,δ)-estimate when k = O(ε^-2 log(1/δ)).
  • 3.2.2 Approximating PA(G) with SIS: For a fixed graph, SIS estimates its Procedure A probability by uniformly sampling edge orderings and averaging their generation probabilities.The estimate is unbiased after multiplying the average by m!, and uses ℓ = O(ε^-2 log(1/δ)) samples for an (ε,δ)-estimate.
  • 3.2.2 Approximating PA(G) with SIS: Combining estimates of the total graph count and PA(G) yields an FPRAS for randomly generating graphs with the prescribed degree sequence.The paper presents GenerateGraph after establishing estimates for both quantities.

4 Analysis

The analysis shows that the weighted sequential procedure is asymptotically uniform, succeeds with high probability, and runs in expected time O(m d_max) in the stated maximum-degree range.

  • 4 Analysis: For d_max = O(m^(1/4−τ)), Procedure A generates every graph with the degree sequence with asymptotically equal probability.This is established through concentration of the weighted unsuitable-pair quantity around an ordering-independent value.
  • 4 Analysis: Procedure A fails with probability o(1) when d_max = O(m^(1/4−τ)).Together with asymptotic equality of output probabilities, this gives the main sampling guarantee.
  • 4 Analysis: The asymptotically uniform output distribution also provides an independent proof of McKay’s formula for the number of graphs.The paper derives this consequence by combining uniform generation with its configuration-model analysis.
  • 4 Analysis: The expected running time is O(m d_max) for d_max = O(m^(1/4−τ)).The running-time bound is stated for an implementation of Procedure A.
  • 4 Analysis: Algorithm CountGraphs is an FPRAS for estimating the number of graphs with the degree sequence.For any ε,δ > 0, k = O(ε^-2 log(1/δ)) samples suffice for an (ε,δ)-estimate.

1. Therefore similar to the discussion given in [10], the inequality

The section establishes approximation guarantees and running-time bounds for counting and generating graphs, and analyzes the concentration needed to extend regular-graph results to higher degrees.

  • O(m dmax ε^-2 log(1/δ)) expected time makes CountGraphs an FPRAS for estimating the number of graphs with degree sequence ¯d.The bound follows from O(m dmax) work per Procedure A execution and O(ε^-2 log(1/δ)) repetitions.
  • Procedure B uses ℓ = O(ε^-2 log(1/δ)) repetitions to produce an (ε, δ)-estimate for the generation probability PA(G).This estimate supports the subsequent analysis of Algorithm GenerateGraph.
  • Algorithm GenerateGraph is an FPRAS for random generation with expected running time O(m dmax ε^-2).The analysis bounds the expected number of retries and combines the costs of the component procedures.
  • 4.1 Concentration inequality for regular graphs: For regular graphs, the proof targets total variation distance o(1) between Procedure A and the uniform distribution when d = O(n^1/2−τ).The analysis uses concentration of quantities associated with unsuitable pairs and shows the desired bound for all but o(|L(n,d)|) graphs.
  • 4.1 Concentration inequality for regular graphs: The extension beyond d = O(n^1/3−τ) is difficult because the relevant summation has large variance, and an independent-edge approximation can make that variance exponentially large.The proof therefore seeks sharper concentration bounds for the fixed-edge subgraph model.

5 Probability of Failure of Procedure A

The section proves that Procedure A fails with probability o(1), by characterizing failure states and bounding their probability using graph-counting estimates.

  • Lemma 1 supplies an upper bound on the number of simple graphs with a given degree sequence independently of known formulas for |L(d̄)|.Under d_max = O(m^(1/4−τ)), this bound is used to control the probability of failure.
  • Procedure A succeeds with probability 1 − o(1), because the analysis proves that failure events have negligible total probability.The proof characterizes partial degree sequences at failure and bounds each resulting failure event.
  • Failure at step s implies that the remaining unmatched mini-vertices satisfy 2m − 2s ≤ d_max^2 + 1.This follows by comparing the total number of possible pairs with the number of unsuitable edges.
  • At failure, unfinished sets form a small collection of at most d_max sets whose vertices must already induce a clique.This structural restriction enables an upper bound on the number of graphs associated with each failure event.

6 Running Time of Procedure A

The section develops an implementation of Procedure A with O(m d_max) running time for general degree sequences in the stated maximum-degree range.

  • The new implementation samples vertex pairs, accepts them with probability 1 − d_i d_j/(4m), and repeats until a suitable pair is obtained.The expected number of repeats is bounded by a constant because 1 − d_i d_j/(4m) > 1/2.
  • The algorithm updates p_ij from one step to the next using O(d_max) operations, including neighbor summations with at most d_max terms.This incremental update avoids recomputing the quantities from scratch.
  • O(m d_max) is the resulting running time of Procedure A for general degree sequences when d_max = O(m^(1/4−τ)).The implementation updates relevant quantities incrementally, with neighbor-based calculations costing O(d_max) per step.
  • The earlier three-phase implementation has O(d_max^4) expected cost in phase 2 and phase 3, although phase 1 costs O(m d_max).Its total running time is nevertheless O(m d_max) in the stated degree range.

7 Generalizing Kim and Vu’s Analysis

The analysis generalizes Kim and Vu’s approach by comparing partial matching graphs with an independent-edge model and controlling unsuitable-edge counts and their deviations.

  • The proof studies deviations of f over uniformly ordered matchings by partitioning the ordering space and applying concentration inequalities.The partition separates large-deviation regimes before bounding the remaining cases.
  • Ψ_r is decomposed into Δ_r and Λ_r to track unsuitable pairings, including self-loops and double edges.The analysis distinguishes these contributions through additional indices and uses ψ_r as the expected value of Ψ_r.
  • The proof approximates the partial graph G_Nr by G_pr, where each edge is independently selected with probability r/m.This independent-edge model makes expectations and concentration estimates tractable.
  • Lemma 12 derives expectation identities for unsuitable edges within one set and between two sets under the independent-edge model.These identities support subsequent approximations and bounds for ψ_r.

7.2 Algebraic Proof of the Equation (4.3)

This section proves the algebraic relation by partitioning matching orderings according to unsuitable-edge counts and deviations of Ψ_r from its expectation.

  • The ordering space S(M) is divided into four subsets according to unsuitable-edge levels and deviations of Ψ_r from ψ_r.The sets are defined through S*(M), A, B, and the remainder C.
  • The analysis removes orderings with too many unsuitable edges before controlling large positive deviations of Ψ_r − ψ_r.The threshold for unsuitable edges is a fixed fraction of all available edges, while deviation thresholds use T_r(log n)^(1+δ).
  • The remaining subset C consists of orderings in S*(M) that avoid both the large-deviation set A and the near-completion set B.This subset is identified with B_0 in the later nested-chain construction.
  • The nested sets A_0 ⊆ A_1 ⊆ ··· ⊆ A_L impose progressively relaxed bounds Ψ_r − ψ_r < T_r(λ_i) across all r.The parameters λ_i double at each level, enabling the subsequent subpartition argument.
  • The threshold function T_r is defined piecewise using the remaining mini-vertices and auxiliary bounds, with a logarithmic branch near completion.Its design supports the application of Vu’s concentration inequality.

7.5 Proofs of (7.8), (7.9) and (7.10)

This section proves the bounds underlying equations (7.8)–(7.10) by partitioning orderings and applying concentration, algebraic, and combinatorial estimates. The lemmas control the relevant contributions across these partitions.

  • Lemma bounds: For every N in C, Lemma 18 gives f(N) ≤ 1 + o(1).
  • Lemma bounds: The proof derives equations (7.8), (7.9), and (7.10) from Lemmas 15–18 and the definition of K.The argument uses the relation 2K/4 ≪ log n to obtain the bound associated with (7.9).
  • Concentration framework: Vu’s concentration inequality supplies the main probabilistic tool for Lemma 15, while the other lemmas use algebraic and combinatorial bounds.The inequality is applied to polynomial functions of independent random variables and their partial derivatives.
  • Auxiliary probabilistic bounds: Lemma 21 establishes a lower bound on the probability that G^r_p has exactly r edges, with the minimum occurring around r = m/2.Stirling’s approximation is used to obtain the lower bound.
  • Auxiliary probabilistic bounds: The concentration estimates are assembled through Lemma 22, whose four cases bound the quantities needed for the preceding lemmas.The proof repeatedly represents relevant quantities as polynomials and applies Vu’s inequality to them.
  • Auxiliary probabilistic bounds: Lemmas 19 and 20 separate the analysis according to whether 2m − 2r is above or below ωλ_i.The dense case is handled through the complement graph, while the stated lemmas provide the corresponding bounds in each range.

7.6 Proof of (7.11)

This section proves equation (7.11) by controlling the contribution of orderings that satisfy the relevant bounds and showing that the remaining partition contributions are negligible. The resulting expectation is stronger than required.

  • Proof of (7.11): The products used in the argument are each 1 − o(1), based on the bound for (2m − 2r)^2 and the condition involving ωλ^3.
  • Proof of (7.11): The proof establishes the stronger statement E(f(N)1_S∗(M)) > 1 − o(1).
  • Proof of (7.11): The contributions of A_i \ A_{i−1} and B_j \ B_{j−1} are all o(1), while C contributes 1 + o(1).The contribution of A∞ is also o(1) when the constant c is sufficiently large.

7.7 Proof of (7.12)

This section proves equation (7.12) by analyzing orderings that first violate the admissibility condition near the final steps. A combinatorial bound controls the resulting exceptional contribution.

  • Exceptional orderings: The admissibility condition can be violated only when r is very close to m, so the analysis partitions orderings by the first failing step r = m − t.The relevant sets are denoted S_t(M), with t bounded by a power of d_max.
  • Exceptional orderings: Hölder’s inequality and Corollary 5 reduce the remaining estimate to bounding the contribution of the sets S_t(M).Corollary 5 supplies the factor 1 + o(1) in the product.
  • Exceptional orderings: For an ordering that first fails at r = m − t, the remaining edges force a vertex with many neighbors inside its available neighborhood.This yields constraints on the number of edges outside and inside Γ(u).
  • Exceptional orderings: The probability of these exceptional orderings is bounded using the number of suitable edge choices and the assumption t = O(d_max^2) = o(m^1/2).The argument counts suitable pairs and uses d_max = O(m^(1/4−τ)).

8 Bounding the Variance of the SIS estimate

This section bounds the variance of the sequential importance sampling estimate by transferring concentration results to a new partition and adding a combinatorial bound. The resulting second-moment control is 1 + o(1).

  • Variance reduction: The variance analysis reduces to proving E(f(N)^2) = 1 + o(1), equivalently controlling the second moment of the importance-sampling factor.The ratio formulation is E(A(N)^2)/E(A(N))^2 ≤ 1 + o(1).
  • Concentration transfer: On the well-behaved subset F_0, Lemma 24 gives g(N) ≤ 1 + o(1), while the prior concentration lemmas yield E(f(N)^2 1_C) ≤ 1 + o(1).
  • Combinatorial refinement: A new combinatorial result exploits the model’s structure to obtain a tighter bound than in Section 7.
  • Variance reduction: Combining the bounds yields E_B(P)^2 < 1 + o(1), completing the required second-moment estimate.
  • Combinatorial refinement: The exceptional near-terminal orderings are handled by counting suitable pairs among available vertices, separately for n_r ≥ 2d_max and n_r < 2d_max.This combinatorial lemma supplies the missing bound needed after the concentration estimates.
Loading cs/0702124v5…