degree.sequence.game: Generate random graphs with a given degree sequence

Description

It is often useful to create a graph with given vertex degrees. This is exactly what degree.sequence.game does.

Usage

degree.sequence.game(out.deg, in.deg = numeric(0),
     method = c("simple", "vl"), ...)

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.

method

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

...

Additional arguments, these are used as graph attributes.

Value

The new graph object.

concept

Degree sequence
Configuration model

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 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 unformly. See http://www-rp.lip6.fr/~latapy/FV/generation.html for details.

Examples

Run this code

## The simple generator
g <- degree.sequence.game(rep(2,100))
degree(g)
is.simple(g)   # sometimes TRUE, but can be FALSE
g2 <- degree.sequence.game(1:10, 10:1)
degree(g2, mode="out")
degree(g2, mode="in")

## The vl generator
g3 <- degree.sequence.game(rep(2,100), method="vl")
degree(g3)
is.simple(g3)  # always TRUE

## Exponential degree distribution
## Note, that we correct the degree sequence if its sum is odd
degs <- sample(1:100, 100, replace=TRUE, prob=exp(-0.5*(1:100)))
if (sum(degs) %% 2 != 0) { degs[1] <- degs[1] + 1 }
g4 <- degree.sequence.game(degs, method="vl")
all(degree(g4) == degs)

## Power-law degree distribution
## Note, that we correct the degree sequence if its sum is odd
degs <- sample(1:100, 100, replace=TRUE, prob=(1:100)^-2)
if (sum(degs) %% 2 != 0) { degs[1] <- degs[1] + 1 }
g5 <- degree.sequence.game(degs, method="vl")
all(degree(g5) == degs)

Run the code above in your browser using DataLab

Get 50% off unlimited learning