The Chung-Lu model is useful for generating random graphs with fixed expected degrees. This function implements both the original model of Chung and Lu, as well as some additional variants with useful properties.
Arguments
- out.weights
A vector of non-negative vertex weights (or out-weights). In sparse graphs, these will be approximately equal to the expected (out-)degrees.
- in.weights
A vector of non-negative in-weights, approximately equal to the expected in-degrees in sparse graphs. May be set to
NULL
, in which case undirected graphs are generated.- ...
These dots are for future extensions and must be empty.
- loops
Logical, whether to allow the creation of self-loops. Since vertex pairs are connected independently, setting this to
FALSE
is equivalent to simply discarding self-loops from an existing loopy Chung-Lu graph.- variant
The model variant to sample from, with different definitions of the connection probability between vertices \(i\) and \(j\). Given \(q_{ij} = \frac{w_i w_j}{S}\), the following formulations are available:
- “original”
the original Chung-Lu model, \(p_{ij} = \min(q_{ij}, 1)\).
- “maxent”
maximum entropy model with fixed expected degrees, \(p_{ij} = \frac{q_{ij}}{1 + q_{ij}}\).
- “nr”
Norros and Reittu's model, \(p_{ij} = 1 - \exp(-q_{ij})\).
Details
In the original Chung-Lu model, each pair of vertices \(i\) and \(j\) is connected with independent probability $$p_{ij} = \frac{w_i w_j}{S},$$ where \(w_i\) is a weight associated with vertex \(i\) and $$S = \sum_k w_k$$ is the sum of weights. In the directed variant, vertices have both out-weights, \(w^\text{out}\), and in-weights, \(w^\text{in}\), with equal sums, $$S = \sum_k w^\text{out}_k = \sum_k w^\text{in}_k.$$ The connection probability between \(i\) and \(j\) is $$p_{ij} = \frac{w^\text{out}_i w^\text{in}_j.}{S}$$
This model is commonly used to create random graphs with a fixed expected degree sequence. The expected degree of vertex \(i\) is approximately equal to the weight \(w_i\). Specifically, if the graph is directed and self-loops are allowed, then the expected out- and in-degrees are precisely \(w^\text{out}\) and \(w^\text{in}\). If self-loops are disallowed, then the expected out- and in-degrees are \(\frac{w^\text{out} (S - w^\text{in})}{S}\) and \(\frac{w^\text{in} (S - w^\text{out})}{S}\), respectively. If the graph is undirected, then the expected degrees with and without self-loops are \(\frac{w (S + w)}{S}\) and \(\frac{w (S - w)}{S}\), respectively.
A limitation of the original Chung-Lu model is that when some of the weights are large, the formula for \(p_{ij}\) yields values larger than 1. Chung and Lu's original paper excludes the use of such weights. When \(p_{ij} > 1\), this function simply issues a warning and creates a connection between \(i\) and \(j\). However, in this case the expected degrees will no longer relate to the weights in the manner stated above. Thus, the original Chung-Lu model cannot produce certain (large) expected degrees.
To overcome this limitation, this function implements additional variants of
the model, with modified expressions for the connection probability
\(p_{ij}\) between vertices \(i\) and \(j\). Let
\(q_{ij} = \frac{w_i w_j}{S}\), or
\(q_{ij} = \frac{w^\text{out}_i w^\text{in}_j}{S}\)
in the directed case. All model variants become equivalent in the limit of sparse
graphs where \(q_{ij}\) approaches zero. In the original Chung-Lu model,
selectable by setting variant
to “original”, \(p_{ij} =
\min(q_{ij}, 1)\). The “maxent” variant,
sometimes referred to as the generalized random graph, uses \(p_{ij} =
\frac{q_{ij}}{1 + q_{ij}}\), and is equivalent to a
maximum entropy model (i.e., exponential random graph model) with a
constraint on expected degrees;
see Park and Newman (2004), Section B, setting \(\exp(-\Theta_{ij}) =
\frac{w_i w_j}{S}\). This model is also discussed
by Britton, Deijfen, and Martin-Löf (2006). By virtue of being a
degree-constrained maximum entropy model, it generates graphs with the same
degree sequence with the same probability. A third variant can be requested
with “nr”, and uses \(p_{ij} = 1 - \exp(-q_{ij})\). This is the underlying simple graph of a multigraph model
introduced by Norros and Reittu (2006). For a discussion of these three model
variants, see Section 16.4 of Bollobás, Janson, Riordan (2007), as well as
Van Der Hofstad (2013).
References
Chung, F., and Lu, L. (2002). Connected components in a random graph with given degree sequences. Annals of Combinatorics, 6, 125-145. doi:10.1007/PL00012580
Miller, J. C., and Hagberg, A. (2011). Efficient Generation of Networks with Given Expected Degrees. doi:10.1007/978-3-642-21286-4_10
Park, J., and Newman, M. E. J. (2004). Statistical mechanics of networks. Physical Review E, 70, 066117. doi:10.1103/PhysRevE.70.066117
Britton, T., Deijfen, M., and Martin-Löf, A. (2006). Generating Simple Random Graphs with Prescribed Degree Distribution. Journal of Statistical Physics, 124, 1377-1397. doi:10.1007/s10955-006-9168-x
Norros, I., and Reittu, H. (2006). On a conditionally Poissonian graph process. Advances in Applied Probability, 38, 59-75. doi:10.1239/aap/1143936140
Bollobás, B., Janson, S., and Riordan, O. (2007). The phase transition in inhomogeneous random graphs. Random Structures & Algorithms, 31, 3-122. doi:10.1002/rsa.20168
Van Der Hofstad, R. (2013). Critical behavior in inhomogeneous random graphs. Random Structures & Algorithms, 42, 480-508. doi:10.1002/rsa.20450
See also
sample_fitness()
implements a similar model with a sharp
constraint on the number of edges. sample_degseq()
samples random graphs
with sharply specified degrees. sample_gnp()
creates random graphs with a
fixed connection probability \(p\) between all vertex pairs.
Random graph models (games)
erdos.renyi.game()
,
sample_()
,
sample_bipartite()
,
sample_correlated_gnp()
,
sample_correlated_gnp_pair()
,
sample_degseq()
,
sample_dot_product()
,
sample_fitness()
,
sample_fitness_pl()
,
sample_forestfire()
,
sample_gnm()
,
sample_gnp()
,
sample_grg()
,
sample_growing()
,
sample_hierarchical_sbm()
,
sample_islands()
,
sample_k_regular()
,
sample_last_cit()
,
sample_pa()
,
sample_pa_age()
,
sample_pref()
,
sample_sbm()
,
sample_smallworld()
,
sample_traits_callaway()
,
sample_tree()
Examples
g <- sample_chung_lu(c(3, 3, 2, 2, 2, 1, 1))
rowMeans(replicate(
100,
degree(sample_chung_lu(c(1, 3, 2, 1), c(2, 1, 2, 2)), mode = "out")
))
#> [1] 1.17 2.94 1.96 0.89
rowMeans(replicate(
100,
degree(sample_chung_lu(c(1, 3, 2, 1), c(2, 1, 2, 2), variant = "maxent"), mode='out')
))
#> [1] 0.90 1.71 1.32 0.84