Generating simple random graphs with prescribed degree distribution

Abstract

Let $F$ be a probability distribution with support on the non-negative integers. Four methods for generating a simple undirected graph with (approximate) degree distribution $F$ are described and compared. Two methods are based on the so called configuration model with modifications ensuring a simple graph, one method is an extension of the classical Erdős-Rényi graph where the edge probabilities are random variables, and the last method starts with a directed random graph which is then modified to a simple undirected graph. All methods are shown to give the correct distribution in the limit of large graph size, but under different assumptions on the degree distribution $F$ and also using different order of operations.

Cited by in corpus (70)

• Recent advances in percolation theory and its applications
• Efficient and exact sampling of simple graphs with given arbitrary degree sequence
• Scale-free Networks Well Done
• Earthquake Phase Association with Graph Neural Networks
• The Impact of Heterogeneous Thresholds on Social Contagion with Multiple Initiators
• The largest component in a subcritical random graph with a power law degree distribution
• A note on dynamical models on random graphs and Fokker-Planck equations
• Counting cliques and cycles in scale-free inhomogeneous random graphs
• Explosion in weighted Hyperbolic Random Graphs and Geometric Inhomogeneous Random Graphs
• Exact sampling of graphs with prescribed degree correlations
• Local clustering in scale-free networks with hidden variables
• Building Damage-Resilient Dominating Sets in Complex Networks against Random and Targeted Attacks
• Generation of swine movement network and analysis of efficient mitigation strategies for African swine fever virus
• Universality for critical heavy-tailed network models: Metric structure of maximal components
• Growing networks with preferential addition and deletion of edges
• Clustering Spectrum of scale-free networks
• Generating Simple Directed Social Network Graphs for Information Spreading
• A connection between MAX $\kappa$-CUT and the inhomogeneous Potts spin glass in the large degree limit
• Dominating Scale-Free Networks Using Generalized Probabilistic Methods
• The structure of typical clusters in large sparse random configurations
• Triadic closure in configuration models with unbounded degree fluctuations
• Weighted hypersoft configuration model
• Limits of multiplicative inhomogeneous random graphs and Lévy trees: Limit theorems
• Random intersection graphs with communities
• Random Simplicial Complexes: Models and Phenomena
• Snowboot: Bootstrap Methods for Network Inference
• Cliques in rank-1 random graphs: the role of inhomogeneity
• Subgraphs in preferential attachment models
• Counting triangles in power-law uniform random graphs
• Scale-free network clustering in hyperbolic and other random graphs
• Creating and controlling overlap in two-layer networks. Application to a mean-field SIS epidemic model with awareness dissemination
• On rate of convergence to the Poisson law of the number of cycles in the generalized random graphs
• Universality for the distance in finite variance random graphs: Extended version
• An Agent-Based Model of Message Propagation in the Facebook Electronic Social Network
• PageRank's behavior under degree-degree correlations
• The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs
• The size of the largest component below phase transition in inhomogeneous random graphs
• Robustness of behaviourally-induced oscillations in epidemic models under a low rate of imported cases
• Large deviations for the annealed Ising model on inhomogeneous random graphs: spins and degrees
• Degree correlations in scale-free null models
• Why do simple algorithms for triangle enumeration work in the real world?
• The Configuration Model for Partially Directed Graphs
• Distinguishing power-law uniform random graphs from inhomogeneous random graphs through small subgraphs
• The tail does not determine the size of the giant
• Detecting a planted community in an inhomogeneous random graph
• Critical Percolation on Random Networks with Prescribed Degrees
• Analysis of Networks via the Sparse $\beta$-Model
• Limit theorems for number of edges in the generalized random graphs with random vertex weights
• Quantum Motif Clustering
• On a general class of inhomogeneous random digraphs
• Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
• Phase transition in a power-law uniform hypergraph
• Connectivity of random graphs after centrality-based vertex removal
• Connected components in networks with higher-order interactions
• Emergence of Multivariate Extremes in Multilayer Inhomogeneous Random Graphs
• Asymptotics for cliques in scale-free random graphs
• Distributed Maximal Independent Set on Scale-Free Networks
• Poisson approximation for cycles in the generalised random graph
• Increasing risk behavior can outweigh the benefits of anti-retroviral drug treatment on the HIV incidence among men-having-sex-with-men in Amsterdam
• Interpretable Network Representation Learning with Principal Component Analysis
• Multiscale genesis of a tiny giant for percolation on scale-free random graphs
• Scale-free percolation
• Stationary random graphs on $\mathbb{Z}$ with prescribed iid degrees and finite mean connections
• Robust subgraph counting with distribution-free random graph analysis
• A simple method for improving the accuracy of Chung-Lu random graph generation
• Upper bounds for number of removed edges in the Erased Configuration Model
• Systemic Cascades On Inhomogeneous Random Financial Networks
• Global clustering coefficient in scale-free weighted and unweighted networks
• Finding induced subgraphs in scale-free inhomogeneous random graphs
• Fast generation of simple directed social network graphs with reciprocal edges and high clustering