Skip to contents

It is often useful to create a graph with given vertex degrees. This function creates such a graph in a randomized manner.

Usage

sample_degseq(
  out.deg,
  in.deg = NULL,
  method = c("simple", "vl", "simple.no.multiple", "simple.no.multiple.uniform")
)

degseq(..., deterministic = FALSE)

Arguments

out.deg

Numeric vector, the sequence of degrees (for undirected graphs) or out-degrees (for directed graphs). For undirected graphs its sum should be even. For directed graphs its sum should be the same as the sum of in.deg.

in.deg

For directed graph, the in-degree sequence. By default this is NULL and an undirected graph is created.

method

Character, the method for generating the graph. Right now the “simple”, “simple.no.multiple” and “vl” methods are implemented.

...

Passed to realize_degseq() if ‘deterministic’ is true, or to sample_degseq() otherwise.

deterministic

Whether the construction should be deterministic

Value

The new graph object.

Details

The “simple” method connects the out-stubs of the edges (undirected graphs) or the out-stubs and in-stubs (directed graphs) together. This way loop edges and also multiple edges may be generated. This method is not adequate if one needs to generate simple graphs with a given degree sequence. The multiple and loop edges can be deleted, but then the degree sequence is distorted and there is nothing to ensure that the graphs are sampled uniformly.

The “simple.no.multiple” method is similar to “simple”, but tries to avoid multiple and loop edges and restarts the generation from scratch if it gets stuck. It is not guaranteed to sample uniformly from the space of all possible graphs with the given sequence, but it is relatively fast and it will eventually succeed if the provided degree sequence is graphical, but there is no upper bound on the number of iterations.

The “simple.no.multiple.uniform” method is a variant of “simple.no.multiple” with the added benefit of sampling uniformly from the set of all possible simple graphs with the given degree sequence. Ensuring uniformity has some performance implications, though.

The “vl” method is a more sophisticated generator. The algorithm and the implementation was done by Fabien Viger and Matthieu Latapy. This generator always generates undirected, connected simple graphs, it is an error to pass the in.deg argument to it. The algorithm relies on first creating an initial (possibly unconnected) simple undirected graph with the given degree sequence (if this is possible at all). Then some rewiring is done to make the graph connected. Finally a Monte-Carlo algorithm is used to randomize the graph. The “vl” samples from the undirected, connected simple graphs uniformly.

Author

Gabor Csardi csardi.gabor@gmail.com

Examples


## The simple generator
undirected_graph <- sample_degseq(rep(2, 100))
degree(undirected_graph)
#>   [1] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
#>  [38] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
#>  [75] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
is_simple(undirected_graph) # sometimes TRUE, but can be FALSE
#> [1] TRUE


directed_graph <- sample_degseq(1:10, 10:1)
degree(directed_graph, mode = "out")
#>  [1]  1  2  3  4  5  6  7  8  9 10
degree(directed_graph, mode = "in")
#>  [1] 10  9  8  7  6  5  4  3  2  1

## The vl generator
vl_graph <- sample_degseq(rep(2, 100), method = "vl")
degree(vl_graph)
#>   [1] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
#>  [38] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
#>  [75] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
is_simple(vl_graph) # always TRUE
#> [1] TRUE

## Exponential degree distribution
## We fix the seed as there's no guarantee
##  that randomly picked integers will form a graphical degree sequence
## (i.e. that there's a graph with these degrees)
## withr::with_seed(42, {
## exponential_degrees <- sample(1:100, 100, replace = TRUE, prob = exp(-0.5 * (1:100)))
## })
exponential_degrees <- c(
  5L, 6L, 1L, 4L, 3L, 2L, 3L, 1L, 3L, 3L, 2L, 3L, 6L, 1L, 2L,
  6L, 8L, 1L, 2L, 2L, 5L, 1L, 10L, 6L, 1L, 2L, 1L, 5L, 2L, 4L,
  3L, 4L, 1L, 3L, 1L, 4L, 1L, 1L, 5L, 2L, 1L, 2L, 1L, 8L, 2L, 7L,
  5L, 3L, 8L, 2L, 1L, 1L, 2L, 4L, 1L, 3L, 3L, 1L, 1L, 2L, 3L, 9L,
  3L, 2L, 4L, 1L, 1L, 4L, 3L, 1L, 1L, 1L, 1L, 2L, 1L, 3L, 1L, 1L,
  2L, 1L, 2L, 1L, 1L, 3L, 3L, 2L, 1L, 1L, 1L, 1L, 3L, 1L, 1L, 6L,
  6L, 3L, 1L, 2L, 3L, 2L
)
## Note, that we'd have to correct the degree sequence if its sum is odd
is_exponential_degrees_sum_odd <- (sum(exponential_degrees) %% 2 != 0)
if (is_exponential_degrees_sum_odd) {
  exponential_degrees[1] <- exponential_degrees[1] + 1
}
exp_vl_graph <- sample_degseq(exponential_degrees, method = "vl")
all(degree(exp_vl_graph) == exponential_degrees)
#> [1] TRUE

## An example that does not work
if (FALSE) { # rlang::is_interactive()
## withr::with_seed(11, {
## exponential_degrees <- sample(1:100, 100, replace = TRUE, prob = exp(-0.5 * (1:100)))
## })
exponential_degrees <- c(
  1L, 1L, 2L, 1L, 1L, 7L, 1L, 1L, 5L, 1L, 1L, 2L, 5L, 4L, 3L,
  2L, 2L, 1L, 1L, 2L, 1L, 3L, 1L, 1L, 1L, 2L, 2L, 1L, 1L, 2L, 2L,
  1L, 2L, 1L, 4L, 3L, 1L, 1L, 1L, 1L, 1L, 1L, 2L, 3L, 1L, 4L, 3L,
  1L, 2L, 4L, 2L, 2L, 2L, 1L, 1L, 2L, 2L, 4L, 1L, 2L, 1L, 3L, 1L,
  2L, 3L, 1L, 1L, 2L, 1L, 2L, 3L, 2L, 2L, 1L, 6L, 2L, 1L, 1L, 1L,
  1L, 1L, 2L, 2L, 1L, 4L, 2L, 1L, 3L, 4L, 1L, 1L, 3L, 1L, 2L, 4L,
  1L, 3L, 1L, 2L, 1L
)
## Note, that we'd have to correct the degree sequence if its sum is odd
is_exponential_degrees_sum_odd <- (sum(exponential_degrees) %% 2 != 0)
if (is_exponential_degrees_sum_odd) {
  exponential_degrees[1] <- exponential_degrees[1] + 1
}
exp_vl_graph <- sample_degseq(exponential_degrees, method = "vl")
}
## Power-law degree distribution
## We fix the seed as there's no guarantee
##  that randomly picked integers will form a graphical degree sequence
## (i.e. that there's a graph with these degrees)
## withr::with_seed(1, {
##  powerlaw_degrees <- sample(1:100, 100, replace = TRUE, prob = (1:100)^-2)
## })
powerlaw_degrees <- c(
  1L, 1L, 1L, 6L, 1L, 6L, 10L, 2L, 2L, 1L, 1L, 1L, 2L, 1L, 3L,
  1L, 2L, 43L, 1L, 3L, 9L, 1L, 2L, 1L, 1L, 1L, 1L, 1L, 4L, 1L,
  1L, 1L, 1L, 1L, 3L, 2L, 3L, 1L, 2L, 1L, 3L, 2L, 3L, 1L, 1L, 3L,
  1L, 1L, 2L, 2L, 1L, 4L, 1L, 1L, 1L, 1L, 1L, 1L, 2L, 1L, 7L, 1L,
  1L, 1L, 2L, 1L, 1L, 3L, 1L, 5L, 1L, 4L, 1L, 1L, 1L, 5L, 4L, 1L,
  3L, 13L, 1L, 2L, 1L, 1L, 2L, 1L, 2L, 1L, 1L, 1L, 1L, 1L, 2L,
  5L, 3L, 3L, 1L, 1L, 3L, 1L
)
## Note, that we correct the degree sequence if its sum is odd
is_exponential_degrees_sum_odd <- (sum(powerlaw_degrees) %% 2 != 0)
if (is_exponential_degrees_sum_odd) {
  powerlaw_degrees[1] <- powerlaw_degrees[1] + 1
}
powerlaw_vl_graph <- sample_degseq(powerlaw_degrees, method = "vl")
all(degree(powerlaw_vl_graph) == powerlaw_degrees)
#> [1] TRUE

## An example that does not work
if (FALSE) { # rlang::is_interactive()
## withr::with_seed(2, {
##  powerlaw_degrees <- sample(1:100, 100, replace = TRUE, prob = (1:100)^-2)
## })
powerlaw_degrees <- c(
  1L, 2L, 1L, 1L, 10L, 10L, 1L, 4L, 1L, 1L, 1L, 1L, 2L, 1L, 1L,
  4L, 21L, 1L, 1L, 1L, 2L, 1L, 4L, 1L, 1L, 1L, 1L, 1L, 14L, 1L,
  1L, 1L, 3L, 4L, 1L, 2L, 4L, 1L, 2L, 1L, 25L, 1L, 1L, 1L, 10L,
  3L, 19L, 1L, 1L, 3L, 1L, 1L, 2L, 8L, 1L, 3L, 3L, 36L, 2L, 2L,
  3L, 5L, 2L, 1L, 4L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 2L,
  1L, 4L, 1L, 1L, 1L, 2L, 1L, 1L, 1L, 4L, 18L, 1L, 2L, 1L, 21L,
  1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L
)
## Note, that we correct the degree sequence if its sum is odd
is_exponential_degrees_sum_odd <- (sum(powerlaw_degrees) %% 2 != 0)
if (is_exponential_degrees_sum_odd) {
  powerlaw_degrees[1] <- powerlaw_degrees[1] + 1
}
powerlaw_vl_graph <- sample_degseq(powerlaw_degrees, method = "vl")
all(degree(powerlaw_vl_graph) == powerlaw_degrees)
}