sample_chung_lu: Random graph with given expected degrees

In igraph: Network Analysis and Visualization

Random graph with given expected degrees

Description

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.

Usage

sample_chung_lu(
  out.weights,
  in.weights = NULL,
  ...,
  loops = TRUE,
  variant = c("original", "maxent", "nr")
)

chung_lu(
  out.weights,
  in.weights = NULL,
  ...,
  loops = TRUE,
  variant = c("original", "maxent", "nr")
)

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).

Value

An igraph graph.

Related documentation in the C library

igraph_chung_lu_game().

References

Chung, F., and Lu, L. (2002). Connected components in a random graph with given degree sequences. Annals of Combinatorics, 6, 125-145. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1007/PL00012580")}

Miller, J. C., and Hagberg, A. (2011). Efficient Generation of Networks with Given Expected Degrees. \Sexpr[results=rd]{tools:::Rd_expr_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. \Sexpr[results=rd]{tools:::Rd_expr_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. \Sexpr[results=rd]{tools:::Rd_expr_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. \Sexpr[results=rd]{tools:::Rd_expr_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. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1002/rsa.20168")}

Van Der Hofstad, R. (2013). Critical behavior in inhomogeneous random graphs. Random Structures & Algorithms, 42, 480-508. \Sexpr[results=rd]{tools:::Rd_expr_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")
))

rowMeans(replicate(
  100,
  degree(sample_chung_lu(c(1, 3, 2, 1), c(2, 1, 2, 2), variant = "maxent"), mode='out')
))

igraph documentation built on Oct. 20, 2024, 1:06 a.m.