Generating Simple Random Graphs with Prescribed Degree Distribution

By Tom Britton, Maria Deijfen, Anders Martin-Löf. 2006

333 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/1ca605afa1a7eddd583ffab6622314b1967261b7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

Universality for first passage percolation on sparse random graphs (2012, background): “bability 1 − e−λ/n. Thus, this model is a natural generalization of the classical random graph model. Related models are the generalized random graph introduced by Britton, Deijfen and Martin-Lo¨f in [16], for which pij = wiwj ℓn +wiwj , (1.29) and the random graph with given prescribed degrees or C”
Recent advances in percolation theory and its applications (2015, background): “However, in order to adapt the random graph to complex networks, we can make these degrees scale-free in a generalized random graph by taking the parameter λ to be a random variable with a power-law distribution [163].”
Random Graphs and Complex Networks (2016, background): “For example, in the generalized random graph [65], the probability that edge between vertices s and t, which we denote by st, is occupied, conditionally on the weights {Wi}i=1, is equal to pst = WsWt WsWt + Ln , (1.”
Scale-free percolation (2011, neutral): “We mention also the expected degree model by Chung and Lu [13, 14] and the related generalized random graph [12], which are in the same universality class as the Poissonian random graph model.”
A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees (2011, background): “Britton, Deijfen and Martin-Löf [15] give several algorithms which they show asymptotically produce random graphs with a given degree distribution.”
The phase transition in inhomogeneous random graphs (2005, neutral): “…(κ n ) n≥1 of kernels on (S, µ) is graphical on V with limit κ if, for a.e. (y, z) ∈ S 2 , y n → y and z n → z imply that κ n (y n , z n ) → κ(y, z), (2.7) B ´ ELA BOLLOB´AS , SVANTE JANSON, AND OLIVER RIORDAN κ satisfies conditions (i) and (ii) of Definition 2.7, and 1 n E e(G V (n, κ n )) → 1 2 S”
Directed Random Graphs with given Degree Distributions (2012, methodology): “N , D propose This feature makes the bi-degree-sequence ( ) we an approximate equivalent of the i.i.d. degree sequence considered in [1, 8, 24] for undirected graphs.”
Novel scaling limits for critical inhomogeneous random graphs (2009, methodology): “A further adaptation is the generalized random graph introduced by Britton, Deijfen and Martin-Löf in [12], for which pij = wiwj n + wiwj .”
The component sizes of a critical random graph with given degree sequence (2010, methodology): “We refer to Britton, Deijfen and Martin-Löf [11] for an understanding of the link between inhomogeneous random graphs and SGn.”