Generating simple random graphs with prescribed degree distribution
arXiv:1509.06985 · doi:10.1007/s10955-006-9168-x
Abstract
Let be a probability distribution with support on the non-negative integers. Four methods for generating a simple undirected graph with (approximate) degree distribution 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 and also using different order of operations.
References in corpus (5)
Cited by in corpus (90)
- The phase transition in inhomogeneous random graphs
- Recent advances in percolation theory and its applications
- Edge-Based Compartmental Modeling for Infectious Disease Spread Part I: An Overview
- Sparse graphs using exchangeable random measures
- Efficient and exact sampling of simple graphs with given arbitrary degree sequence
- Scale-free Networks Well Done
- Earthquake Phase Association with Graph Neural Networks
- Minimum Dominating Sets in Scale-Free Network Ensembles
- 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
- Constructing and sampling directed graphs with given degree sequences
- Novel scaling limits for critical inhomogeneous random graphs
- A preferential attachment model with random initial degrees
- A note on dynamical models on random graphs and Fokker-Planck equations
- Edge-based compartmental modeling for epidemic spread Part II: Model Selection and Hierarchies
- 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
- Bias in generation of random graphs
- Growing networks with preferential addition and deletion of edges
- Clustering Spectrum of scale-free networks
- Generating Simple Directed Social Network Graphs for Information Spreading
- Degree-based network models
- A connection between MAX -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
- First Passage Percolation on Inhomogeneous Random Graphs
- Weighted hypersoft configuration model
- Random Simplicial Complexes: Models and Phenomena
- Random intersection graphs with communities
- Limits of multiplicative inhomogeneous random graphs and Lévy trees: Limit theorems
- Snowboot: Bootstrap Methods for Network Inference
- Subgraphs in preferential attachment models
- Revisiting Degree Distribution Models for Social Graph Analysis
- Percolation in invariant Poisson graphs with i.i.d. degrees
- Cliques in rank-1 random graphs: the role of inhomogeneity
- 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
- Universality for the distance in finite variance random graphs: Extended version
- On rate of convergence to the Poisson law of the number of cycles in the generalized random graphs
- 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
- Large deviations for the annealed Ising model on inhomogeneous random graphs: spins and degrees
- Robustness of behaviourally-induced oscillations in epidemic models under a low rate of imported cases
- Degree correlations in scale-free null models
- Exactly scale-free scale-free networks
- Why do simple algorithms for triangle enumeration work in the real world?
- The size of the largest component below phase transition in inhomogeneous random graphs
- Replica theory for learning curves for Gaussian processes on random graphs
- Distinguishing power-law uniform random graphs from inhomogeneous random graphs through small subgraphs
- The Configuration Model for Partially Directed Graphs
- The tail does not determine the size of the giant
- Critical Percolation on Random Networks with Prescribed Degrees
- Detecting a planted community in an inhomogeneous random graph
- Quantum Motif Clustering
- Analysis of Networks via the Sparse -Model
- On a general class of inhomogeneous random digraphs
- Random walk kernels and learning curves for Gaussian process regression on random graphs
- Degree Distributions in General Random Intersection Graphs
- Continuum limit of critical inhomogeneous random graphs
- Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
- Limit theorems for number of edges in the generalized random graphs with random vertex weights
- Asymptotics for cliques in scale-free random graphs
- 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
- Increasing risk behavior can outweigh the benefits of anti-retroviral drug treatment on the HIV incidence among men-having-sex-with-men in Amsterdam
- Finding induced subgraphs in scale-free inhomogeneous random graphs
- The phase transition in the multi-type binomial random graph
- Interpretable Network Representation Learning with Principal Component Analysis
- Poisson approximation for cycles in the generalised random graph
- Multiscale genesis of a tiny giant for percolation on scale-free random graphs
- Robust subgraph counting with distribution-free random graph analysis
- A simple method for improving the accuracy of Chung-Lu random graph generation
- Fast generation of simple directed social network graphs with reciprocal edges and high clustering
- Upper bounds for number of removed edges in the Erased Configuration Model
- Scale-free percolation
- Systemic Cascades On Inhomogeneous Random Financial Networks
- Stationary random graphs on with prescribed iid degrees and finite mean connections
- Distributed Maximal Independent Set on Scale-Free Networks
- Global clustering coefficient in scale-free weighted and unweighted networks
- Evolution of a modified binomial random graph by agglomeration