Efficient and exact sampling of simple graphs with given arbitrary degree sequence

Abstract

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.

8 pages, 3 figures

References in corpus (10)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Random graphs with arbitrary degree distributions and their applications
• The Web of Human Sexual Contacts
• Generation of uncorrelated random scale-free networks
• Generating simple random graphs with prescribed degree distribution
• Cut-offs and finite size effects in scale-free networks
• The entropy of network ensembles
• Uncorrelated Random Networks
• Entropies of complex networks with hierarchically constrained topologies

Cited by in corpus (60)

• The structure and dynamics of multilayer networks
• Emergence of network features from multiplexity
• The Statistical Physics of Real-World Networks
• The Physics of Financial Networks
• Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes
• Quantifying randomness in real networks
• Scale-free Networks Well Done
• All scale-free networks are sparse
• Evolving networks in the human epileptic brain
• Threshold-limited spreading in social networks with multiple initiators
• Unbiased sampling of network ensembles
• Assortative mixing in functional brain networks during epileptic seizures
• Minimum Dominating Sets in Scale-Free Network Ensembles
• Unraveling Spurious Properties of Interaction Networks with Tailored Random Networks
• Constructing and sampling directed graphs with given degree sequences
• Multiple phase transitions of the susceptible-infected-susceptible epidemic model on complex networks
• Degree correlations in directed scale-free networks
• Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints
• A note on dynamical models on random graphs and Fokker-Planck equations
• Network community detection using modularity density measures
• Entropy distribution and condensation in random networks with a given degree distribution
• Exact sampling of graphs with prescribed degree correlations
• Fast and accurate determination of modularity and its effect size
• Clustering of random scale-free networks
• Finding network communities using modularity density
• Reducing Degeneracy in Maximum Entropy Models of Networks
• On Realizations of a Joint Degree Matrix
• Correlations between weights and overlap in ensembles of weighted multiplex networks
• Constrained Randomisation of Weighted Networks
• Surrogate-assisted analysis of weighted functional brain networks
• Bias in generation of random graphs
• Optimized evolution of networks for principal eigenvector localization
• Origin and implications of zero degeneracy in networks spectra
• Clustering Spectrum of scale-free networks
• Endemic infections are always possible on regular networks
• Dense networks with scale-free feature
• Large-scale network motif analysis using compression
• Lower bound of assortativity coefficient in scale-free networks
• Duality between equilibrium and growing networks
• Entropy rate of non-equilibrium growing networks
• A decomposition based proof for fast mixing of a Markov chain over balanced realizations of a joint degree matrix
• Phase transitions for scaling of structural correlations in directed networks
• Grand canonical ensembles of sparse networks and Bayesian inference
• Connectedness matters: Construction and exact random sampling of connected graphs
• Entropy of microcanonical finite-graph ensembles
• Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes
• New classes of degree sequences with fast mixing swap Markov chain sampling
• Deciding football sequences
• Exactly scale-free scale-free networks
• Eigenvalue spectral tails and localization properties of asymmetric networks
• Higher-order null models as a lens for social systems
• Distinct Degrees and Their Distribution in Complex Networks
• Relaxation dynamics of maximally clustered networks
• 2.5K-Graphs: from Sampling to Generation
• Degree switching and partitioning for enumerating graphs to arbitrary orders of accuracy
• Problems with classification, hypothesis testing, and estimator convergence in the analysis of degree distributions in networks
• Construction of Directed 2K Graphs
• Upper bounds for number of removed edges in the Erased Configuration Model
• Consistent Approximation of Epidemic Dynamics on Degree-heterogeneous Clustered Networks
• Mapping structural diversity in networks sharing a given degree distribution and global clustering: Adaptive resolution grid search evolution with Diophantine equation-based mutations