Generating simple random graphs with prescribed degree distribution

DOI10.1007/S10955-006-9168-XzbMATH Open1106.05086arXiv1509.06985OpenAlexW2083750870MaRDI QIDQ858034FDOQ858034

T. Britton, Maria Deijfen, Anders Martin-Löf

Publication date: 5 January 2007

Published in: Journal of Statistical Physics (Search for Journal in Brave)

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 ErdH{o}s-R'{e}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.

Full work available at URL: https://arxiv.org/abs/1509.06985

Recommendations

• Efficient and simple generation of random simple connected graphs with prescribed degree sequence
• Computing and Combinatorics
• scientific article; zbMATH DE number 15335
• Generating Random Networks and Graphs
• An algorithm generating random graphs with power law degree distributions
• scientific article; zbMATH DE number 3924802
• Generating random graphs with large girth
• Uniform generation of random graphs with power-law degree sequences
• Generating random regular graphs

zbMATH Keywords

probability distributionconfiguration modelgenerating algorithms

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Cites Work

• Emergence of Scaling in Random Networks
• Title not available (Why is that?)
• The Structure and Function of Complex Networks
• Title not available (Why is that?)
• A critical point for random graphs with a given degree sequence
• Title not available (Why is that?)
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Connected components in random graphs with given expected degree sequences
• Title not available (Why is that?)
• The average distances in random graphs with given expected degrees
• Title not available (Why is that?)
• The asymptotic number of labeled graphs with given degree sequences
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• Title not available (Why is that?)
• Uniform generation of random regular graphs of moderate degree
• Title not available (Why is that?)

Cited In (only showing first 100 items - show all)

• Global Clustering Coefficient in Scale-Free Weighted and Unweighted Networks
• The structure of typical clusters in large sparse random configurations
• Percolation in invariant Poisson graphs with i.i.d. degrees
• The Phase Transition in Multitype Binomial Random Graphs
• Universality for critical heavy-tailed network models: metric structure of maximal components
• Triadic closure in configuration models with unbounded degree fluctuations
• Limit laws in the generalized random graphs with random vertex weights
• Universality for distances in power-law random graphs
• Novel scaling limits for critical inhomogeneous random graphs
• A preferential attachment model with random initial degrees
• Limits of multiplicative inhomogeneous random graphs and Lévy trees: the continuum graphs
• First Passage Percolation on Inhomogeneous Random Graphs
• Generating stationary random graphs on ℤ with prescribed independent, identically distributed degrees
• Asymptotic normality in random graphs with given vertex degrees
• Large deviations for power-law thinned Lévy processes
• Large deviations in generalized random graphs with node weights
• The tail does not determine the size of the giant
• Diffusion in Random Networks: Impact of Degree Distribution
• Exactly scale-free scale-free networks
• Minimum vertex cover in generalized random graphs with power law degree distribution
• Cluster tails for critical power-law inhomogeneous random graphs
• Coupling of Two SIR Epidemic Models with Variable Susceptibilities and Infectivities
• An algorithm generating random graphs with power law degree distributions
• Modelling sexually transmitted infections: the effect of partnership activity and number of partners on \(R_0\)
• Counting cliques and cycles in scale-free inhomogeneous random graphs
• MAX \(\kappa\)-cut and the inhomogeneous Potts spin Glass
• Asymptotic in undirected random graph models with a noisy degree sequence
• Exact sampling of graphs with prescribed degree correlations
• Directed random graphs with given degree distributions
• Evolution of a modified binomial random graph by agglomeration
• Inhomogeneous long-range percolation on the hierarchical lattice
• Systemic cascades on inhomogeneous random financial networks
• Non-Hyperbolicity of Random Graphs with Given Expected Degrees
• Constructing and sampling graphs with a prescribed joint degree distribution
• The component sizes of a critical random graph with given degree sequence
• Random intersection graphs with communities
• Critical behavior in inhomogeneous random graphs
• Central limit type theorems in the generalized random graphs with random vertex weights
• Universality for the distance in finite variance random graphs
• Bounding basic characteristics of spatial epidemics with a new percolation model
• Asymptotic equivalence and contiguity of some random graphs
• Computing and Combinatorics
• Constructing and sampling directed graphs with given degree sequences
• Networks, epidemics and vaccination through contact tracing
• A note on the derivation of epidemic final sizes
• RANDOM INTERSECTION GRAPHS WITH TUNABLE DEGREE DISTRIBUTION AND CLUSTERING
• A novel fault diagnosis mechanism for wireless sensor networks
• Counting triangles in power-law uniform random graphs
• Large deviations for the annealed Ising model on inhomogeneous random graphs: spins and degrees
• Asymptotics for cliques in scale-free random graphs
• Scale-free network clustering in hyperbolic and other random graphs
• Component structure of the configuration model: Barely supercritical case
• Sparse Graphs Using Exchangeable Random Measures
• Scale-free percolation
• Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
• Respondent-driven sampling on directed networks
• Model hierarchies in edge-based compartmental modeling for infectious disease spread
• The largest component in a subcritical random graph with a power law degree distribution
• Graphs with specified degree distributions, simple epidemics, and local vaccination strategies
• A new approach to the giant component problem
• Degree correlations in scale-free random graph models
• Recent advances in percolation theory and its applications
• Large deviations for empirical measures of generalized random graphs
• Large Cliques in a Power-Law Random Graph
• The configuration model for partially directed graphs
• Asymptotic distribution in directed finite weighted random graphs with an increasing bi-degree sequence
• The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs
• Continuum limit of critical inhomogeneous random graphs
• A note on dynamical models on random graphs and Fokker-Planck equations
• General results on preferential attachment and clustering coefficient
• Ising critical exponents on random trees and graphs
• Why Do Simple Algorithms for Triangle Enumeration Work in the Real World?
• PageRank on inhomogeneous random digraphs
• Subgraphs in preferential attachment models
• Phase transition in random intersection graphs with communities
• Spectral based hypothesis testing for community detection in complex networks
• Distinguishing power-law uniform random graphs from inhomogeneous random graphs through small subgraphs
• Asymptotic in the ordered networks with a noisy degree sequence
• A new coupled disease-awareness spreading model with mass media on multiplex networks
• Optimal subgraph structures in scale-free configuration models
• Limit laws for the number of triangles in the generalized random graphs with random node weights
• On the Rényi index of random graphs
• Affiliation weighted networks with a differentially private degree sequence
• Random Simplicial Complexes: Models and Phenomena
• The Largest Component in Subcritical Inhomogeneous Random Graphs
• Heavy-Traffic Analysis Through Uniform Acceleration of Queues with Diminishing Populations
• Robustness of clustering coefficients
• Limit laws for self-loops and multiple edges in the configuration model
• Modelling the spread of diseases in clustered networks
• Finding Induced Subgraphs in Scale-Free Inhomogeneous Random Graphs
• Asymptotic coarse Ricci curvature of inhomogeneous random graph
• Rate of Convergence to the Poisson Law of the Numbers of Cycles in the Generalized Random Graphs
• Connectivity of random graphs after centrality-based vertex removal
• Stochastic recursions on directed random graphs
• Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
• Number of edges in inhomogeneous random graphs
• Effects of null model choice on modularity maximization
• Detecting a planted community in an inhomogeneous random graph
• Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes
• The calculation and simulation of the price of anarchy for network formation games

This page was built for publication: Generating simple random graphs with prescribed degree distribution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q858034)